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:
Mechanically create TM $M_2$ which does the following on $x$:
- if $M$ accepts $w$ (via simulation from UTM): accept $x$.
- if $M$ rejects $w$: loop in a manner such that $M_2$ would not be a member of the aforementioned set.
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.