1
$\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

Improve this question
$\endgroup$
4
  • 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
    Commented Nov 11, 2016 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
    Commented Nov 11, 2016 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
    Commented Nov 11, 2016 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
    Commented Nov 11, 2016 at 12:48

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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