Uncomputable Numbers

Consider Goldbach's Conjecture ( https://en.wikipedia.org/wiki/Goldbach%27s_conjecture ), which states that every even number greater than 2 is the sum of two prime numbers.

You could write quite a short program to search for a counterexample - for each even number, check to see if it's the sum of two prime numbers. If it's not, then print it and halt, if it is then go on to the next number.

Looking at this program, you could easily understand how it works, but to know if it halts you need to solve one of the most famous open problems in mathematics.

We can often determine if a program halts or not. The halting problem is discussing solving it in the general case.

For example, you can easily prove that your hello world program will halt. In fact, any program which does not have any flow control can be proven to halt. Even if the program has flow control, you can still prove that it halts by proving that iteration is bounded by some number that is strictly decreasing.

So yes, for each program given some specific input, the program either halts or it doesn't halt. And there is always a way in which you can determine if that is the case: You simply run it until either the program halts or it goes back to an earlier state. The halting program says that there is no general solution that allows you to look at a program to determine this property.

"This sentence is wrong."

If we could decide the halting problem, we can write a program P that receives another program x as input, such that P(x) halts if x(P) doesn't halt, and otherwise loops forever. What is the value of P(P)?

> How does a simple Python program, that one cannot determine whether it halts or not, look?

The halting problem is actually theoretically decidable for real world programming languages such as Python. That's because in the real world, computers have finite memory, and the halting problem actually decidable for machines with finite memory (linear bounded automata).

Not practically decidable – if a program consumes 1MB of RAM, then (in the general case) solving the halting problem for it will take approximately 2^1048576 steps, which is much longer than the age of the universe.

There’s an important difference between Turing machines and computers: unlimited memory. For a computer with limited memory, of course you can determine whether a program halts, because if it doesn’t halt then eventually the state machine must loop back to a prior state.

I find this answer on quora to the question of why Turing machines are a good model to be insightful: https://qr.ae/pGGCmq

> How does a simple Python program, that one cannot determine whether it halts or not, look?

That's not exactly the right way to look at it. The better way to think of it is to say: for every potential solution to the halting problem, there is a program for which that solution doesn't work. So what the counterexample looks like will depend on your proposed halting problem decider.

Let's imagine your wrote a function "halts(program)" that takes a program as input and returns whether that program halts or not. Let's also for simplicity assume that the program input is just the string representation of the source code in e.g. Python. And let's ignore programs that depend on arguments for now.

Now write the following program, let's call it X:

  if halts(X):
    while true:
      pass

it might seem strange to see the value X, which is supposed to be the string value of the source of the whole program, appear within X. In fact, this seems impossible at first. However, with some clever tricks, you can actually always do that, at least in a turing complete language (including Turing Machines themselves).

now, what is the response of "halts(X)"? (remember: X is just the source code of the program above)

Well, let's first assume that X is a program that halts. Then, wenn we run X, it checks whether it itself halts. Since it does, it then goes into an infinite loop... wait, but then halts can't be right, since it told us X would halt, but it doesn't.

If we assume that X doesn't halt, then conversely, X checks itself, finds out it doesn't halt and then... halts. Another contradiction.

This proves that the function "halts" cannot actually be written, for if it could, it would immediately give the wrong answer for this program X.

The central argument is, in principle, not more complex than what I've shown. The actual complexity of the proof comes from the whole self-referentiality argument, namely that we can actually embed X within itself. This is quite non-trivial, since we have to prove it in the general case.