Ask HN: Are there programs whose halting status is undecidable? | Hacker News Reader

Ask HN: Are there programs whose halting status is undecidable?

6 pointspjungwir8 comments

Can you write a program for a Turing machine for which no human will ever know whether it will halt or not? A few rules/assumptions:

- I'm not talking about a program too long to read, because that's boring, but something whose halting status is essentially unknowable. After all what if humans solve aging, solve solar catastrophe, etc.?

- I assume Turing machines have no random number generator, so you can't write a program like "if rand() > 0.5 then halt else spin."

- I'm asking about programs that are not just undecided but undecidable. For instance you could write a computer that halts iff it finds a positive even integer that is not a sum of two primes (cf. Goldbach's conjecture), and no one knows yet whether that program will halt. But who's to say someone won't figure it out in a hundred years? Can you write a program whose halting status is demonstrably undecidable?

View on HN

I assume you're asking because the "non-constructive" proof of the halting problem's undecidability is unsatisfying and you want a concrete example.

Another way to approach the problem is to talk about the reals and the naturals: the cardinality of the reals is greater than the cardinality of the naturals. Turing machines are encoded in binary, hence the set of Turing machines is no larger than the set of natural numbers. Hence there are some reals that cannot be computed by a Turing machine.

This suggests an obvious example: write a program to compute the square root of a number with infinite precision. Then let it run. For any input, can you tell me whether it's stuck trying to compute an irrational number, or just taking a long time to compute a very large rational number?

Actually I'm asking because I'm curious whether the mind has the same limitations as a Turing machine.

I really like the simplicity of your example, but it seems like it only works if you can't see the source code. If you see the source code---which is what you'd allow to any Turing machine---why couldn't you figure this out very easily?

No, it doesn't matter how you implement square root. If you were able to tell me whether any execution of the program halts, then you would be able to tell me, for any `n`, whether or not `n` is irrational (since irrational results are exactly the results that it won't halt on).

But this isn't possible: it's an open problem whether or not `pi + e` [is irrational](http://math.stackexchange.com/questions/28243/is-there-a-pro...). So if you could always tell me when the square root program halted, you'd be able to tell me whether or not it halted for `(pi + e)^2`.

But if you were able to tell me that, you would have solved an open problem in number theory along the way -- you'd have solved a whole class of open problems about whether or not certain expressions are rational. I can't prove to you that no solution of this kind exists, but, intuitively, do you see how big the implications would be if you could solve the halting problem for your square root machine?

Ah, thanks for clarifying! I think I overlooked the "square root" part of your original response. You're right, seeing the source code is no help at all! And it's difficult to say that a human could always say if sqrt(x) is rational, for all x. Still, this seems a bit like the Goldbach conjecture example: we don't have a math proof for this now, but some day we might. I wonder if there is any program that is provably undecidable---like the way Godel's theorem proves that some statements are undecidable from their axioms.

A program that tries to find a solution to the Goldbach conjecture will eventually halt. Either it finds a solution or the numbers themselves become so large that they overflow the computers working memory. The halting problem I think is only interesting for Idealized Turing Machines. For real computers, the Second law of thermodynamics should be enough to prove that any program will halt sooner or later.

For real computers, yes, but we're talking about Turing machines. :-) By your logic there is no halting problem at all because every machine will eventually halt. A Turing machine has infinite tape and infinite time.

Yes, the halting problem in general is undecidable.

char input = Console.ReadKey();

if (input == 'y') { Console.WriteLine("Yes"); } else { Console.WriteLine("!Yes"); }

// Might never finish - what if the user never inputs a char?

Reply on news.ycombinator.com