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.

  • $\begingroup$ 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}$? $\:$ $\endgroup$
    – Ricky Demer
    May 19, 2013 at 1:35
  • $\begingroup$ @RickyDemer Not quite. I mean that "there exists a Turing Machine that can decide its existence" $\endgroup$
    – Phillip Huff
    May 19, 2013 at 2:09
  • $\begingroup$ ... "there exists a Turing Machine that" takes what as inputs to "decide its existence"? $\endgroup$
    – Ricky Demer
    May 19, 2013 at 4:56
  • $\begingroup$ @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" $\endgroup$
    – Phillip Huff
    May 19, 2013 at 5:21
  • $\begingroup$ 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? $\:$ $\endgroup$
    – Ricky Demer
    May 19, 2013 at 6:07

1 Answer 1


(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,
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$,
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]$

  • $\begingroup$ That appears to be equivalent to what I was trying to say. Thanks. $\endgroup$
    – Phillip Huff
    May 19, 2013 at 8:55

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .