Yioop - PHP Search Engine

2013-05-13

Practice Final #9, Section 1.

Originally Posted By: peterle

Use the Recursion Theorem to show HALTTM in undecidable

Proof by contradiction
Suppose H is a machine that decides HALTTM
H = { | M is a TM and M halts on w}
Consider the machine B = "on input w:

Obtain, via recursion theorem, own description
Run H on
accept if H rejects, reject if H accepts"

B accepts w iff H rejects
H rejects iff B rejects w
Contradiction - HALTTM is undecidable

Peter Le
Nicolas Seto
Jianqi Wang
Wenlong Zhang

'''Originally Posted By: peterle''' Use the Recursion Theorem to show HALTTM in undecidable Proof by contradiction Suppose H is a machine that decides HALTTM H = { | M is a TM and M halts on w} Consider the machine B = "on input w: *Obtain, via recursion theorem, own description *Run H on *accept if H rejects, reject if H accepts" B accepts w iff H rejects H rejects iff B rejects w Contradiction - HALTTM is undecidable Peter Le Nicolas Seto Jianqi Wang Wenlong Zhang