[Solved]: Undecidability of telling if a program returns true or false

Problem Detail: 

Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are allowed to give any answer (but you have to halt and give some answer on all inputs).

Is this problem undecidable? My gut says that it should be, but I can't find a reduction to the halting problem. Given a Turing machine that may or may not halt, we can set up the machine to finish with a $0$ in the case that it halts, but can't finish with anything in the non-halting case, so the oracle could just say $0$ in this case without having to figure out whether in fact the machine halts.

Note that a reduction in the other direction is simple; if you can solve the halting problem, then given a TM that either finishes with $0$ or $1$, we replace the $1$-writing step with an infinite loop to create a new TM. If the new TM halts, we say "it writes a $0$" and if it does not halt we say "it writes a $1$". This answer is guaranteed to be correct as long as the TM in fact halts with a $0$ or $1$, so we can solve the original problem.

Asked By : Mario Carneiro

Answered By : Craig Gidney

Assume you have a function like the one you described:

def haltify(f):     # Never fails to halt.     # If 'f' halts, returns f().     # If 'f' doesn't halt, anything could be returned.     ... magic ... 

But then someone comes along and does this:

def evil():     return not haltify(evil) 

See the problem?

1. If haltify(f) is guaranteed to halt for all f, then evil is also guaranteed to halt because it just calls haltify on a specific f and inverts the output.
2. Since evil halts, haltify(evil) must evaluate to the same thing as evil().
3. So not haltify(evil) simplifies to not evil() and that's what evil() returns.
4. That's a problem, because there's no x satisfying x == not x. Evil's result is contradictory.
5. Therefore one of the assumptions we used is wrong: either haltify isn't guaranteed to halt, or it isn't guaranteed to return f() when passed a halting f.

Bonus exercise: why doesn't the function def good(): return haltify(good) cause problems for haltify, despite apparently simplifying to the infinite loop def good(): return good()?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54844