# Undecidability of whether a given TM halts or only has loops which can be detected by some TM

This might be a bit of an abstruse question, but it's something I've been trying to prove.

I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all Turing Machines that either always halt, or have non-halting loops where all of which can be detected (a positive decision made on it's existence) by some Turing Mahcine.

I'm trying to do a reduction from the Entscheidungsproblem, and my proof looks something like this:

Create a Turing machine $D$ on input $<M,w>$ that does the following:

1. Mechanically create TM $M_2$ which does the following on $x$:

1. if $M$ accepts $w$ (via simulation from UTM): accept $x$.
2. if $M$ rejects $w$: loop in a manner such that $M_2$ would not be a member of the aforementioned set.
2. Run decider for above problem on $M_2$:

• if decider accepts, it should accept because if $M$ accepts $w$, $M_2$ must always halt and must be a member of the set in question.
• if decider rejects, it should reject because if $M$ does not accept $w$, $M_2$ must have a non mechanically detectable loop and is not in the set.

The above Turing Machine $D$ should therefore decide Entscheidungsproblem and shows the reduction. However, I'm not sure how to show that it possible to mechanically create a loop which cannot be mechanically detected, or whether an alternate method of proof would be adequate.

Any insight in this proof would be appreciated.

• Does "all of which can be mechanically detected" mean $\hspace{2.88 in}$ "the set of inputs that reach those is decidable"$\hspace{.01 in}$? $\:$ – Ricky Demer May 19 '13 at 1:35
• @RickyDemer Not quite. I mean that "there exists a Turing Machine that can decide its existence" – Phillip Huff May 19 '13 at 2:09
• ... "there exists a Turing Machine that" takes what as inputs to "decide its existence"? – Ricky Demer May 19 '13 at 4:56
• @RickyDemer The description a Turing Machine. To try to be clear, "or have non-halting loops where all of which can be mechanically detected" means "any non-halting loops can be detected (a decision is made upon it's existence) by a Turing Machine which takes as an input a description of the given Turing Machine" – Phillip Huff May 19 '13 at 5:21
• So, "given some Turing machine M that, on input $n$, guesses a list of loops in the $n$th Turing machine, decide whether or not the $n$th Turing machine halts, on the promise that M is correct"? If that's right, does it need to report loops that can't actually be reached, and what if there are infinitely many significantly different such loops? $\:$ – Ricky Demer May 19 '13 at 6:07

(too long for a comment)

Here's my attempt at an unambiguous version of what you are trying to get across.

Is it the case that for every total Turing machine M,
if
[
for all $\langle d,n\rangle$ in $\{0,1,2,3,...\}^2$, $\:$ if M accepts $\langle d,n\rangle$ then
$d$ describes a Turing machine that enters a loop on input $n$,
]
then
[
there is a many-one reduction from the Halting Problem
to the set of $d$ in $\{0,1,2,3,...\}$ such that
[
$\hspace{.01 in}d$ describes a total Turing machine or $\big[\big[$for all $n$ in $\{0,1,2,3,...\}$,
if $d$ enters a loop on input $n$ then M accepts $\langle d,n\rangle\big]$ and there exists such an $n\big]$
]
?

• That appears to be equivalent to what I was trying to say. Thanks. – Phillip Huff May 19 '13 at 8:55