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

https://news.ycombinator.com/item?id=9067206

by pjungwir • 11 years ago

6 8 11 years ago

news.ycombinator.com

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?

redisfaster• 11 years ago

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?

angry_octet• 11 years ago

Yes, the halting problem in general is undecidable.

capitalsigma2• 11 years ago

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?

pjungwir3• 11 years ago

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?

capitalsigma2• 11 years ago

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?

bjourne• 11 years ago

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.

pjungwir3• 11 years ago

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.