Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 8 down vote accepted

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

share|cite|improve this answer
    
Very nice. This is isomorphic to Yuval's answer, but a little less mind-bendingly concise. Re: Bonus, haltify will get to choose the result of good() and it will be self-consistent in either case, but it will still return because (by voodoo magic) haltify(good) halts, so it is not actually an infinite loop so much as a constraint on the answer. (In reality, the way to implement haltify is just to run the argument, in which case both good and evil are saved from contradiction by diverging, but then of course we are forced to allow haltify to diverge, which defeats the point.) – Mario Carneiro Mar 24 at 0:00
    
Another interesting question is whether it is possible to write an "optimizing compiler" which takes an input TM $T$ and outputs some $T'$ that calculates the same result, but faster. The answer depends a lot on the details of the machines, and is an active area of research. This result shows that for any such compiler, there are at least some infinite computations cannot be "sped up" to execute in finite time (which is a sort of infinite version of the incompressibility theorem for encoding schemes). – Mario Carneiro Mar 24 at 0:10
    
@MarioCarneiro the finite version applies here either: there are at least some turing machines that always execute in finite time yet they cannot be sped up. – Jan Dvorak Mar 24 at 4:19
    
Doesn't IEEE 754 NaN satisfy x == !x? – cat Mar 26 at 0:58
    
@tac In python, not float('nan') evaluates to false. not is also one of the operators you can't overload; it always returns a bool. (You can define a custom conversion to bool, but the interpreter checks that you actually returned a bool). Even if there is a hacky way to construct an x in python that satisfiesx == not x, the example was only intended to be pedagogically correct not pedantically correct. – Craig Gidney Mar 26 at 13:59

Suppose that $M$ is a machine solving this problem; I assume that $M$ accepts a Turing machine and an input, but you can arrange that it only accepts a Turing machine if you prefer. We construct a different machine $T$ that works as follows. On input $x$, it runs $M$ on machine $x$ and input $x$, records the output as $b$, and writes $1-b$ on the initial cell. Now run $T$ on itself to reach a contradiction.

share|cite|improve this answer
1  
Does not work. Substitute the following constraint in the original problem; the input Turing machine is guaranteed to halt. In fact this reduction is wrong also for the halting problem, but for quite unobvious reasons. – Joshua Mar 23 at 20:51
    
I don't see the problem. Perhaps you could explain it? – Yuval Filmus Mar 23 at 20:53
1  
If the input is guaranteed to halt the machine must merely execute it to find the answer and so cannot fail to do so. – Joshua Mar 23 at 20:55
1  
To each his own. – Yuval Filmus Mar 23 at 20:56
    
@Joshua: Are you saying that all input Turing machines are guaranteed to halt, or that a particular input Turing machine is guaranteed to halt? There is no guarantee that all inputs halt, and for $M$ to "merely execute" the input would require it to identify the halting inputs. – user2357112 Mar 23 at 21:53

Your reduction to the halting problem is streightforward logically. If your machine halts, it must halt in some time T based on a primitive construction of its input. If the halting problem is unsolvable, the construction must be lossy; therefore there exists a machine for which it guesses wrongly and does halt without being fully evaluated, and a long chain of XOR forces full evaluation to reach the right answer. Therefore there exists a machine for which it yields the wrong answer.

In fact any nontrivial problem that does not exclude non-halting machines as input reduces to the halting problem in this manner. Ref: https://en.wikipedia.org/wiki/Rice's_theorem

share|cite|improve this answer
1  
Your answer doesn't make much sense, unfortunately. – Yuval Filmus Mar 23 at 20:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.