patternMinor
Does Turing Machine divergence depend on the input?
Viewed 0 times
theinputdivergencedoesmachineturingdepend
Problem
If there is a Turing Machine $M_e$ (computing some partially computable function $f$), is there an algorithm to decide if $f$ diverges for all possible inputs?
Solution
No. It is very easy to reduce $A_{TM}=\{(M,w): M$ accepts $w\}$ to the complement of the problem you describe: given input $(M,w)$, output a machine $M'$ that simulates $M(w)$. If $M$ accepts $w$ then $M'$ halts and accepts. Otherwise, $M'$ goes into an infinite loop (either if $M$ loops on $w$, or manually if $M$ rejects $w$).
Now, if $M$ accepts $w$, then $M'$ does not diverge on every input, and otherwise it does.
Now, if $M$ accepts $w$, then $M'$ does not diverge on every input, and otherwise it does.
Context
StackExchange Computer Science Q#11196, answer score: 3
Revisions (0)
No revisions yet.