10
$\begingroup$

I was given a question to prove that there exists a turing machine that solves the question

Is there life beyond earth?

and is decidable. I actually don't understand how to show a turing machine decides this.

Thanks.

$\endgroup$
2
  • 5
    $\begingroup$ I'll argue that it is not decidable. Step 1: destroy all other life in the universe. Step 2: run the Turing machine. Step 3: launch an astronaut into deep space. Step 4: run the Turing machine again, from the same initial state. Since the outputs given at steps 2 and 4 were the same, and the correct answers were different, the Turing machine does not correctly solve the problem. (Trick questions deserve trick answers.) $\endgroup$ – David Jun 2 '15 at 19:58
  • $\begingroup$ The correct answer is a poor joke about a sloppy definition. A suitable definition of "decidable" would be that there is an algorithm that decides whether the given statement is true and not that there is an algorithm giving the correct result which is always the case because one algorithm produces "no" and the other "yes". Such a definition is completely useless because in this sense , almost EVERY yes-no-question is decidable. $\endgroup$ – Peter Sep 17 '18 at 8:09
24
$\begingroup$

This is a trick question, the idea being that the answer doesn't depend on the input (or rather, has no input; but Turing machines are usually assumed to have an implicit input). If the answer is YES, then the Turing machine that prints YES solves the problem. The same goes for the answer NO. Of course, we don't know which of these two Turing machine solves the problem, but we know that one of them does.

In contrast, suppose you wanted to solve the halting problem in this way. Then you would need a table where for each program you record whether it halts on the empty input or not. This table is infinite, and so this approach doesn't work.

$\endgroup$
34
  • 4
    $\begingroup$ Instead of "doesn't depend on the input" it might perhaps be more accurate to say that there isn't any input to depend on -- at least if by "input" we mean data that tell the machine which instance of the problem it's supposed to solve, because this problem has only one instance. $\endgroup$ – hmakholm left over Monica Jun 2 '15 at 14:16
  • 3
    $\begingroup$ @Dan that is what I thought first, when I thought about the question. But this is not Yuval's explanation, which is a consequence of computing a function without input. Oh and obj.alive would be hard to implement as well. $\endgroup$ – mvw Jun 2 '15 at 14:38
  • 3
    $\begingroup$ I remember this question from Sipser's book! The way I convinced myself was that, in connection with this, the term "decidable" concerns the Turing machine's ability to determine the answer, not ours. $\endgroup$ – Vandermonde Jun 2 '15 at 20:49
  • 3
    $\begingroup$ @Lee, no you've completely misunderstood Yuval's solution. It goes like this. There are two cases; either the answer is yes, or the answer is no. If the answer is yes, then the Turing machine that prints "Yes" and does nothing else solves the problem. If the answer is no, then the Turing machine that prints "No" and does nothing else solves the problem. So in either case, there exists a Turing machine that solves the problem. Therefore, there exists a Turing machine that solves the problem. $\endgroup$ – goblin GONE Jun 2 '15 at 22:59
  • 3
    $\begingroup$ The fact that we don't know which case is the correct case, does not impact the existence of a correct case, nor does it impact the existence of a machine that correctly solves the problem. It does, however, impact our ability to know which machine correctly solves the problem. $\endgroup$ – goblin GONE Jun 2 '15 at 22:59

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.