HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Does Turing Machine divergence depend on the input?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#11196, answer score: 3

Revisions (0)

No revisions yet.