COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture nine 1
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP0017 We discussed the concept of a universal
Turing machine (UTM) and constructed one.
A key idea of the UTM is that a Turing machine may take other Turing machines as input data.
We used these insights to show that there exists an undecidable problem (the Halting problem) and an unrecognisable problem (the complement of the Halting problem).
One more example
We give one more example of an undecidable problem.
The empty tape halting problem (ETH) is defined by the following language.
ETH = { x ∈ Σ* | x = code(M) and M halts on 𝜀.}
Theorem ETH is undecidable. 3
ETH is undecidable Proof We reason by contradiction. Suppose ETH was
decidable, say by a TM METH. We now show how we can use METH to construct a TM MH deciding HALT.
MH is defined as follows. On input ⟨y,x⟩:
If y ≠ code(M) for all M, reject.
If y = code(M), construct MM,x as follows:
1. MM,x enters a loop on any non-empty string.
2. On input 𝜀, write x on tape and simulate M on x.
Accept if METH accepts code(MM,x), otherwise reject. 4
ETH is undecidable We conclude the proof by verifying that MH
decides the Halting problem.
But we know that the Halting problem is undecidable, contradiction. So, the machine
METH that we used to construct MH, cannot exist,
meaning that ETH is undecidable. 5
⟨y, x ⟩ ∈ HALT
y = code(M) and M halts on x.
MM,x halts on 𝜀.
METH accepts code(MM,x).
MH accepts ⟨y, x ⟩.
A pattern emerges Last lecture we saw:
Theorem HALT − is unrecognisable.
Proof If HALT − was recognisable, HALT would be
decidable.
This lecture we saw:
Theorem ETH is undecidable.
Proof If ETH was decidable, HALT would be decidable.
A pattern emerges
In each case, we reduce the decidability/recognisability of a
problem L to the decidability of another problem (HALT). HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
Proof outline: suppose a TM M’ deciding L exists.
Then there exists a TM deciding HALT:
If y = code(M) and M halts on x.
Otherwise.
⟨y, x⟩ ∈ Σ* x Σ*
use M’ in some way
In more abstract terms In order to prove that a problem L is undecidable:
1. Start with a problem L’ that you know is undecidable. 2. Show that if you could decide L then you could
decide L’.
3. Conclude that you cannot decide L.
(The same argument works with “recognise’’ in place of decide.)
The key step is 2: showing that deciding L’ reduces to deciding L.
In the next lecture we will turn this kind of reduction argument into a proof strategy, which shows undecidability of problems much more straightforwardly.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com