COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture eight 1
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP0017
We studied in depth what Turing machines are able to do. Decide/recognise problems and languages.
Simulate diverse computational models, from register machines to programming languages.
Be universal and programmable. 2
In this lecture
We begin the study of what Turing machines cannot do.
We introduce our first undecidable problem: the halting problem.
This informs us about the limits of algorithmic computation.
Remember the Church-Turing thesis?
Any problem that can be solved by a human being though a well-defined step- by-step procedure can be solved by a Turing machine.
Implications of Church-Turing thesis
Explored last week
Solvable by a well-defined Solvable by a step-by-step procedure Turing Machine
To be explored from now on.
Unsolvable by a Unsolvable by a well-defined Turing Machine step-by-step procedure
Not by a C++/Python/… program
Not by a quantum computer Etc.
Languages and TMs: a reminder A TM M decides a language (decision problem) L if:
• When x ∈ L, then M accepts x (= halts in state Y).
• When x ∉ L, then M rejects x (= halts in state N).
A TM M recognises a language (decision problem) L if:
• When x ∈ L, then M halts on x.
When x ∉ L, then M does not halt on x. 6
Degrees of (un)solvability
Decided by a TM ~
Not decided by any TM but recognised by a TM
(There exists an algorithm answering “Yes” and “No”)
Unsolvable
(Semi-decidable: no algorithm
has all the “No” answers)
Unsolvable
(Completely undecidable: any algorithm
will miss both “Yes” and “No” answers) 7
Not even recognised by any TM
An unsolvable problem
We now show a language that is unsolvable: it is recognisable but not decidable.
An unsolvable problem First, assume an encoding code(-):
machine is an example of such encoding.
Turing machine on alphabet Σ.
String x ∈ Σ*. The translation used to define the Universal Turing
The halting problem We define the language of the halting problem:
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
Theorem The halting problem is recognisable but undecidable.
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
The easy part: HALT is recognisable.
Exercise: how would you sketch a Turing machine recognising HALT?
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
The remaining part: show that HALT is not decidable. We make a proof by contradiction.
So suppose that HALT is decidable, and call MH the TM deciding it.
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
When y = code(M) for a certain M:
If M halts on x.
If M does not halt on x.
⟨code(M), x ⟩
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.} Proof
Now we are able to define a new TM called Mʼ as follows. z ∈ Σ*
run MH on input ⟨z, z⟩.
If MH rejects.
If MH accepts.
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.} Proof
Now try to run Mʼ on input code(M’). code(M’)
run MH on input ⟨code(M’), code(M’)⟩.
If MH rejects.
If MH accepts.
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
by def of Mʼ
by def of HALT
by def of MH
⟨code(Mʼ), code(Mʼ)⟩ ∉ HALT
Contradiction. Let’s try the other option… 16
MH accepts ⟨code(Mʼ), code(M’)⟩.
Mʼ does not halt (loops) on
MH does not accept ⟨code(Mʼ), code(M’)⟩.
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
by def of Mʼ
by def of HALT
by def of MH
⟨code(Mʼ), code(Mʼ)⟩ ∈ HALT
Either cases, we reach a contradiction. 17
MH rejects ⟨code(Mʼ), code(M’)⟩.
Mʼ halts on code(Mʼ).
MH accepts ⟨code(Mʼ), code(M’)⟩.
The halting problem
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
The only assumption needed for the construction of Mʼ was that a TM MH deciding HALT existed.
So MH cannot exist, meaning that HALT is undecidable. 18
Where we are, so far
Decided by a TM ~
Not decided by any TM but recognised by a TM
Solvable (There exists an algorithm
Unsolvable
(Semi-decidable: no algorithm
has all the “No” answers)
answering “Yes” and “No”)
the Halting
Not even recognised by any TM
Unsolvable
(Completely undecidable: any algorithm
will miss both “Yes” and “No” answers) 19
Un-recognisable problems
Theorem the complement HALT − of the Halting problem is not recognised by any Turing machine.
HALT = { ⟨y, x ⟩ ∈ Σ*x Σ* | y = code(M) and M halts on x.}
HALT − = { ⟨y, x ⟩ ∈ Σ*x Σ* | y ≠ code(M) for any M or y = code(M) and M does
not halt on x.} 20
Un-recognisable problems
HALT − = { ⟨y, x ⟩ ∈ Σ*x Σ* | y ≠ code(M) for any M or y = code(M) and M does
not halt on x.}
Proof Again we make a proof by contradiction. Suppose that
HALT − is recognisable and let MH- be the TM recognising it. We define a new TM called Mʼʼ as follows.
run MH- on input ⟨z, z⟩.
If M halts.
Otherwise.
Un-recognisable problems
HALT − = { ⟨y, x ⟩ ∈ Σ*x Σ* | y ≠ code(M) for any M or y = code(M) and M does
not halt on x.} ⟨code(Mʼʼ), code(Mʼʼ)⟩
by def of HALT − by def of MH-
by def of Mʼʼ
Contradiction. Let’s try the other option… 22
MH- halts on ⟨code(Mʼʼ), code(Mʼʼ)⟩.
Mʼʼ halts on code(Mʼʼ).
MH- does not halt on ⟨code(Mʼʼ), code(Mʼʼ)⟩.
Un-recognisable problems
HALT − = { ⟨y, x ⟩ ∈ Σ*x Σ* | y ≠ code(M) for any M or y = code(M) and M does
not halt on x.} ⟨code(Mʼʼ), code(Mʼʼ)⟩
by def of HALT − by def of MH-
by def of Mʼʼ
Either cases, we reach a contradiction. 23
MH- does not halt on ⟨code(Mʼʼ), code(Mʼ’)⟩.
Mʼʼ does not halt on code(Mʼʼ).
MH- halts on ⟨code(Mʼʼ), code(Mʼʼ)⟩.
Un-recognisable problems
HALT − = { ⟨y, x ⟩ ∈ Σ*x Σ* | y ≠ code(M) for any M or y = code(M) and M does
not halt on x.}
The only assumption needed for the construction of Mʼʼ was that a TM MH- recognising HALT − existed.
So MH- cannot exist, meaning that HALT − is not recognisable.
Where we are, so far
Decided by a TM ~
Not decided by any TM but recognised by a TM
Solvable (There exists an algorithm
answering “Yes” and “No”)
the Halting
Not even recognised by any TM
Unsolvable
(Completely undecidable: any algorithm
will miss both “Yes” and “No” answers) 25
Unsolvable
(Semi-decidable: no algoritThhme
has all the “No” answCeorms)plement of the Halting
A different proof
Theorem the complement HALT − of the Halting problem is not recognised by any Turing machine.
There is a more “abstract” and indirect proof of this theorem. We can show:
Theorem If HALT − was recognisable, then HALT would be decidable.
Corollary Therefore, because HALT is undecidable, HALT − is not recognisable.
A different proof
Theorem If HALT − was recognisable, then HALT would be decidable.
We proved before that HALT is recognisable, say by a TM MHR. Suppose that HALT − is also recognisable and let MH- be the
TM recognising it.
We can now construct a TM MH deciding HALT as follows. 27
A different proof Definition of MH :
on input ⟨y, x ⟩, run MHR and MH- in parallel on ⟨y, x ⟩. If MHR halts, accept. If MH- halts, reject.
Therefore MH decides HALT.
⟨y, x ⟩ ∈ HALT ⟨y, x ⟩ ∉ HALT
MHR halts. MH halts and accepts MH- halts. MH halts and rejects
⟨y, x ⟩ ∈ HALT −
A different proof Thus we have proved:
Theorem If HALT − was recognisable, then HALT would be decidable.
Corollary Therefore, because HALT is undecidable, HALT − is not recognisable.
This triggers two observations.
Observation #1
Complement of a Recognisable Language
The proof that we gave does not use in any way that HALT is a problem about machines that may or may not halt.
It would have worked with any recognisable language.
Theorem If L and L − are recognisable, then L is decidable. Proof The same we gave for L = HALT.
Observation #1
Complement of a Recognisable Language
Theorem If L and L − are recognisable, then L is decidable.
Theorem HALT is recognisable but not decidable. We obtain:
Corollary Recognisable languages are not closed under complementation.
Proof HALT is recognisable. If its complement HALT −
was recognisable, HALT would be decidable, contradiction.
Observation #2
Reduction arguments
In giving our second proof of the fact that HALT − is not recognisable, we used an argument of the kind:
If we could recognise L, then we could decide L’.
As L’ is undecidable, then we cannot recognise L.
In the reminder of the course we will use this reduction procedure multiple times, in order to show that other interesting languages are not recognisable/decidable.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com