0
$\begingroup$

Assuming someone tries to approximate a function which decides if a turing machine halts or not. It uses only a finite amount of time. The function returns $0$ (=the turing machine halts), $1$ (=the turing machine never halts) or $2$ (=the algorithm could not decide if the turing machine ever halts). If it returns $0$ or $1$ the answer must be correct.

Of course there are (countable) infinite many calculatable functions which could be used for this. All those functions could be called $f_n(t_i)$ where $t_i$ is a turing machine.

For every $f_n$ there must be some $t_i$ for which the function is not able to decide if the turing machine halts or not. \begin{align} \forall n\in\mathbb{N}:\exists i\in\mathbb{N}:f_n(t_i)=2 \end{align}

One could then define a new $f_m$ which tries all previous defined $f_n$ and if one of the previous $f_n$ was able to decide if a turing machine halts it has the final answer. But of course this also does not work perfect, beause there are still some turing machines for which it is not possible to decide if they halt (otherwise the halting problem would be solved).

Then it is possible to say that a turing machine (or infinite many...) $t_i$ must exist for which all halting problem solver approximations $f_n$ must return $2$.

In words: A turing machine must exist for which it is not possible to decide if it ever halts or not. Is such a turing machine known? If not: why not? Or isn't it possible to find such a turing machine?

Thank you very much

$\endgroup$
  • 4
    $\begingroup$ Here are two functions: g0(j)=0, g1(j)=1. For any t_i one of these applies. So every Turing machine has a solver. Of course, there is no uniform effective way to pick which function applies. $\endgroup$ – Jim Hefferon Nov 11 '16 at 0:25
  • 1
    $\begingroup$ What Jim gave should be extended to you put 2 on inputs that are not equal to j. ​ The set of computable functions such that "If it returns 0 or 1 the answer must be correct." is not computably enumerable. ​ ​ ​ ​ $\endgroup$ – user12859 Nov 11 '16 at 0:57
  • 1
    $\begingroup$ "A turing machine must exist for which it is not possible to decide if it ever halts or not. " -- no. $\endgroup$ – Raphael Nov 11 '16 at 12:30
  • 1
    $\begingroup$ That said, there certainly are TMs for which we don't know whether they halt; see here. It's important to understand that that has nothing to do with decidability! $\endgroup$ – Raphael Nov 11 '16 at 12:48
2
$\begingroup$

A turing machine must exist for which it is not possible to decide if it ever halts or not.

This is an incorrect conclusion. For some ordering of $f$ and $t$, it could be that $f_n$ correctly solves all $t_i$ for $i < n$, i.e. every $t_m$ is solved by $f_{m+1}$. This would still not give a complete solution to the halting problem, as long as the function $n \mapsto f_n$ is not computable.

$\endgroup$

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.