8
$\begingroup$

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.

Improve this question
$\endgroup$
9
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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.) $\endgroup$
    – Mario Carneiro
    Mar 24 '16 at 0:00
  • $\begingroup$ 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). $\endgroup$
    – Mario Carneiro
    Mar 24 '16 at 0:10
  • $\begingroup$ @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. $\endgroup$
    – John Dvorak
    Mar 24 '16 at 4:19
  • $\begingroup$ Doesn't IEEE 754 NaN satisfy x == !x? $\endgroup$
    – cat
    Mar 26 '16 at 0:58
  • $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    Mar 26 '16 at 13:59
7
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joshua
    Mar 23 '16 at 20:51
  • $\begingroup$ I don't see the problem. Perhaps you could explain it? $\endgroup$
    – Yuval Filmus
    Mar 23 '16 at 20:53
  • 1
    $\begingroup$ If the input is guaranteed to halt the machine must merely execute it to find the answer and so cannot fail to do so. $\endgroup$
    – Joshua
    Mar 23 '16 at 20:55
  • 1
    $\begingroup$ To each his own. $\endgroup$
    – Yuval Filmus
    Mar 23 '16 at 20:56
  • $\begingroup$ @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. $\endgroup$
    – user2357112 supports Monica
    Mar 23 '16 at 21:53
-3
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Your answer doesn't make much sense, unfortunately. $\endgroup$
    – Yuval Filmus
    Mar 23 '16 at 20:55
  • $\begingroup$ I have no idea what your last paragraph is supposed to mean. Most problems don't reduce to the halting problem; e.g. the set of Turing machines which halt on every input is not reducible to the halting problem, but rather of strictly greater complexity $(0''>_T0')$. $\endgroup$
    – Noah Schweber
    Aug 16 '18 at 19:50
  • $\begingroup$ @NoahSchweber: It's a deep theorem of computer science. You cannot prove any nontrivial properties of all untyped recursive functions because you cannot solve the halting problem. You have to restrict your problem domain to recursive functions that halt. $\endgroup$
    – Joshua
    Aug 21 '18 at 17:47
  • $\begingroup$ @Joshua Rice's theorem isn't a "deep theorem of computer science," it's a very basic theorem of computability theory. And it does not mean what you seem to think it means - the halting problem represents a very weak level of undecidability. (Rice's theorem states the opposite of what you've written, in fact: it says that the halting problem is reducible to - that is, is of equal or lesser complexity than - any "nontrivial property of partial computable functions.") It might be worth re-examining the basics; are you familiar for example with the fact that I mentioned above ($0''>_T0'$)? $\endgroup$
    – Noah Schweber
    Aug 21 '18 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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