Uncomputable Numbers

Uncomputable Numbers(cantorsparadise.com)

29 points by jorgenveisdal 5 years ago | 12 comments

wodenokoto 5 years ago |

I find uncomputable numbers fascinating, especially that we somehow have computed a few busy beaver numbers given their supposedly uncomputability.

But conversely, I don't understand turing machines well enough to understand how inspecting one won't result in answering whether it halts or not.

Or put in another way: How does a simple Python program, that one cannot determine whether it halts or not, look?

Khoth 5 years ago | |

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.

Tainnor 5 years ago | | |

That's not directly related. The halting problem states that we cannot write a program that can decide whether arbitrary programs halt - even if we had solved every mathematical question that is still open.

Tainnor 5 years ago | |

> 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.

lurquer 5 years ago | | |

That’s a very good explanation.

When I first read about it years ago, I mistakenly assumed it was ‘deeper’ or more profound.

But, at the end of the day, it is just a variant in the old “This Sentence Is False” riddle you’d encounter as a kid.

Papers on the topic are frequently spruced up with complicated gibberish... but, unless we are both missing something fundamental, it’s really as simple as set forth in your post.

skissane 5 years ago | |

> 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.

lokedhs 5 years ago | |

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.

zeroimpl 5 years ago | |

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

ac42 5 years ago | |

"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)?