2
$\begingroup$

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.

$\endgroup$

migrated from cstheory.stackexchange.com May 19 '13 at 21:53

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\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 '13 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 '13 at 2:09
  • $\begingroup$ ... "there exists a Turing Machine that" takes what as inputs to "decide its existence"? $\endgroup$ – Ricky Demer May 19 '13 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 '13 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 '13 at 6:07
2
$\begingroup$

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

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

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.