Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Apr 10 '13 at 17:08

This question came from our site for professional and enthusiast programmers.

1 Answer 1

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.

share|improve this answer
    
@YuvalFilmus: I added the definition of A_TM to the answer, thanks. –  Shaull Apr 11 '13 at 4:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.