CODEWITHSUNDEEP
turing-machineshalting-problem
user2440665
user2440665

Reputation: 101

Explanation of the Turing Machine Halting Problem

I'm looking for a simple explanation of the halting problem for Turing machines. I know the basis of how TMs work, how they enumerate things, machine configurations, etc., but I don't have a good handle on the halting problem.

Can someone provide a good explanation of this topic?

Upvotes: 4

Views: 1210

Answers (2)

user3375537
user3375537

Reputation:

The halting problems asks that we determine whether or not a program, given an input, will halt (reach some final state). Turing proved that no algorithm exists that can determine this for any given program and input.

An algorithm could spend an arbitrarily long amount of time processing a program and its input, but for all programs and all inputs, the algorithm could never accurately determine whether or not the program would eventually halt. With each change of state, the next could be the last.

The halting problem is an early example of a decision problem.

Because no algorithm exists that can accurately answer 'yes, it will halt' or 'no, it will not halt' for the halting problem, it is undecidable.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372814

For a minute, let's ignore the world of Turing machines and just think about computer programs. This will make our reasoning less rigorous, but probably a heck of a lot easier to follow.

Consider the following task: write a program that, given a program P and an input to that program, determines whether the program will terminate when given that input. (For simplicity, we'll assume that the program doesn't ask for user input and doesn't involve randomness, so running the same program on the same input always does the same thing). Is it possible to write a program that meets this description? The answer is no. To show this, we'll use a proof by contradiction. We'll assume that, somehow, someone manages to write the program, and then show that something terrible would happen if this were the case.

Imagine that someone writes a function that looks like this:

function willHalt(program, input)

This function has the following properties:

  1. It always returns a value.
  2. If the function returns true, then the specified program eventually terminates (halts) when run on the specified input.
  3. If the function returns false, then the specified program never terminates when run on the specified input (loops).

At this point we can start to be skeptical about whoever wrote this function.

Them: "Hey! I just wrote a program that can take in any program and and input, and it will tell you whether or not the program halts on that input!"

Us: "Oh really? It can take in any program? Any program at all?"

Them: "Yeah! That's what I said."

Us: "Well, then, what about this program right here?"

And then we give them this program:

function trickyTricky(input) {
    /* Ask whether this program (named trickyTricky) is going to halt
     * on its input.
     */
    if (willHalt(trickyTricky, input)) {
        /* If so, loop infinitely! */
        while (true) { }
    } else {
        /* If not, do nothing and stop running! */
    }
}

So let's think about what this program does.

  • First, imagine that this program, when given a particular input, eventually terminates when run on that input. Trace through the program carefully and see what happens then. First, it asks willHalt whether it's going to terminate, and the answer is "yes, yes it will." That means that the if statement evaluates to true... so the program then goes into an infinite loop! Oops - the program was supposed to halt, but instead it looped infinitely!

  • Second, imagine that this program, when given a particular input, goes into an infinite loop. Trace through the program carefully to see what happens then. First, it asks willHalt whether it's going to terminate. The answer is no, so it doesn't go into the if statement, and instead immediately finishes running. But that's not good - the program was supposed to loop infinitely, but instead it terminated!

So now we have a problem. If you really truly can write a function that tells you whether a program will halt on some input, then you can use that program to build a program that does the opposite of what it's supposed to do - and that's impossible!

The halting problem is just a mathematically rigorous way of formalizing the above idea. Instead of talking about programs, we talk about Turing machines and TM encodings. Really, though, the core idea behind the math is just what's shown above.

If you're interested, for a class I taught last year, I put together a guide to self-reference and undecidability that might give you a little bit more exposition on how this style of argument works.

Upvotes: 9

Related Questions