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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.