[SOLVED] COMP0017 Computability and Complexity Theory

COMP0017 Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture eight 1

Copyright By Assignmentchef assignmentchef

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. Lets 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. Lets 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: assignmentchef QQ: 1823890830 Email: [email protected]