COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lectures four and five 1
Copyright By PowCoder代写 加微信 powcoder
The Turing machine
Decision problems encoded as formal languages Decidable problems
Recognisable problems
Previously on COMP0017
This week Church-Turing thesis
by a Turing Machine
Non- deterministic Turing Machines
Register Machines
Programming languages
The Church-Turing thesis
The Church-Turing thesis
Any problem that can be solved though a well-defined step-by-step procedure can be solved by a Turing machine.
Reflections on the Church-Turing thesis
This is a conjecture, there is no proof.
But there is a huge body of evidence supporting it.
Turing machines compute the same class of functions as
“enhanced” Turing machines (non-deterministic, multiple tapes, tape infinite in both directions…) register machines
programming languages like Python, Java, C, … classical computers
quantum computers
Reflections on the Church-Turing thesis Church-Turing’s thesis does not say anything about
efficiency nor simplicity.
In fact, these are the major flaws of Turing machines, which
make them unsuitable for practical purposes.
TMs are inherently slower than other models because
data access is sequential.
They are extremely difficult to design.
Try writing a TM to sort a list of 32-bit integers….
Reflections on the Church-Turing thesis
But Turing machines still bear conceptual significance.
1. Because they provide a firm mathematical grounding to define in a rigorous way what an algorithm is. (And what a deterministic/non- deterministic/probabilistic/quantum algorithm is.)
2. Because they are capable of simulating any computer on planet earth. Thus we can use them to do mathematical proofs on what could ever be accomplished on actual computers.
What’s coming up
Two ways of provide evidence for the Church-Turing
show that the definition of Turing machines is robust.
show that other models of computations (perhaps more similar to everyday software/hardware) are equivalent to Turing machines.
Variations of a Turing machine
Robustness of a definition
Scientists measure the robustness of a mathematical object (typically a definition) by its invariance to changes.
Robustness usually means it is a “good” definition.
Is the definition of a Turing machine robust?
Turing machines are robust
There are many variations of the concept of Turing machine that apparently empower it.
Add more tapes
Add more heads Two-ways infinite tape Non-determinism
These variations can be all shown to be equivalent to standard Turing machines.
Turing machines with multiple tapes Computation begins with the input
on tape 1 and all other tapes blank.
At each step all heads are in the same state but read symbols on different tapes and may perform different actions.
If an halting state is reached, the output is read from the first tape.
Turing machines with multiple tapes
Formally, this model is defined as tuple ⟨ Σ, Q, q0, H, 𝛿 ⟩, just like
regular Turing machines.
What is different is the type of 𝛿.
k is the number tapes
𝛿: (Q\H)xΣk → Qx(Σ⊎{→,←})k
Turing machines with multiple tapes
One can easily construct a TM with two tapes that checks if a string x = a1 a2 … am is equal to its reverse am am-1 … a1.
1.Initial stage.
by right-to-left. The comparison determines acceptance. 15
2.Write on the second tape a1 a2 … am.
3.Simultaneously read the first left-to-right and the second
… ⊳ ⊔ a1 a2 a3 qq
Turing machines with multiple tapes
Theorem Turing machines and Turing machines with multiple tapes are equivalent.
Proof sketch
One direction of the equivalence is obvious.
For the other direction: let M be a multiple-tape Turing machine. We construct a (single tape) Turing machine
Mʼ such that, given the same input x,
M does not halt ⬄ Mʼ does not halt
M halts with output y ⬄ Mʼ halts with output y 16
Turing machines with multiple tapes
Proof sketch
If M is based on alphabet Σ, Mʼ will be based on alphabet
Σ⊎{ā | a ∈ Σ}⊎{#}.
Idea: a multiple-tapes configuration of M
b⊔ ⊳baab ⊳ba is represented on the single tape of Mʼ as
⊳⊔āb⊔#baab#ba⊔b# q
Turing machines with multiple tapes
Proof sketch
In a single computation step, M reaches a new configuration on each tape.
⊳baab ⊳baab q
Turing machines with multiple tapes
Proof sketch
This single step is simulated by multiple computation steps on the tape of Mʼ.
One full scan to collect information on what symbol is being read on each “virtual” tape.
A second pass to update each virtual tape according to the transition function of M.
If a virtual tape needs more room, shift all the next ones by one position to the right.
⊳⊔āb⊔#baab#ba⊔b#
b⊔#baab⊔#bacb# Very last step: erase everything but the
output of the first virtual tape. 19
Turing machines with multiple tapes
A note about this proof (and others yet to come).
This is not a very precise proof. To be rigorous, we should define Mʼ in full.
Given time and space constraints, we content ourselves with a sketch that is convincing enough to believe that it can be turned into a full definition.
That’s typically the burden with proofs about Turing machines.
By Church-Turing thesis: if you can describe it by an algorithm, there exists a Turing machines that computes it (but in exercises you have to be convincing enough!).
TM with a two-way infinite tape
Same definition as a standard TM, but works on a tape that is also unbounded on the left.
input string starts here
TM with a two-way infinite tape
Theorem Turing machines and Turing machines with a two-way infinite tape are equivalent.
Proof sketch
Given M with a two-way infinite tape, we can construct an equivalent TM Mʼ with two (one-way
infinite) tapes and use the previous theorem. 22
TM with a two-way infinite tape
Proof sketch
Configuration in M
…abaa⊳⊔b q
Configuration in Mʼ
from ⊳ to the right.
from ⊳ to the left (in reverse).
One step in M corresponds to one step on the associated tape in Mʼ, while the other tape of Mʼ is left untouched.
Non-deterministic Turing Machine
Same definition as a standard TM, but transitions are given by a relation, not a function.
DET NON-DET
Thus configurations on a given input string do not form a
sequence, but rather a tree. Branching = non-deterministic
An input is accepted if there exists an accepting branch in such a tree.
𝛿: (Q\H)xΣ → Qx(Σ⊎{→,←})
𝛿: (Q\H)xΣ x Qx(Σ⊎{→,←})
Non-deterministic Turing Machine
A computation tree
We accept if at least one accepts.
Non-deterministic Turing Machine: example
We sketch a non-deterministic TM M deciding the language of non-prime numbers. It works on two tapes.
Tape 1 is read-only and contains the input number n.
non- deterministically write m such that 1 < m < n on tape 2.
If n mod m = 0 otherwise
Halt and accept
Halt and reject
So n is accepted if and only if there exists a number m between 2 and n-1 which divides n.
Non-deterministic Turing Machine: equivalence Theorem Turing machines and non-deterministic
Turing machines are equivalent.
Proof sketch
Exercise: depth-first or breadth-first? Why?
The idea is that Mʼ on input x explores the whole
computation tree of M on the same input x and accepts if at least one branch is found accepting.
Given a non-deterministic TM M, we construct an
equivalent (deterministic) TM Mʼ.
Non-deterministic Turing Machine: equivalence
Proof sketch
In order to do that, Mʼ uses three tapes.
⊳ ⊔ a1 a2 a3
Input tape (read-only)
⊳ ⊔ b1 b2 ⊔ Simulation tape
(explores a branch)
Lexicographic order on the nodes of the computation
tree of M. 11
⊳ 1 3 2 1 Index tape
(keeps track of which branch we are examining)
Take-home message
The definition of a Turing machine is far from being arbitrary.
Even if we try to “enhance” it in various ways, the expressive power stays the same.
Multiple tapes
Tapes infinite on the left
Non-determinism
In practice, we can take advantage of these variants when in proofs we need to design a Turing machine for a certain decision problem.
Application:
closure properties of languages
Closure properties
Now that we have more freedom in designing our Turing machines, we can easily prove some closure properties of the class of languages decided/ recognised by Turing machines.
Closure properties Languages are sets.
So, we can reason about the union, intersection and complement of languages (over the same alphabet Σ).
The complement L− of a language L over Σ is Σ* \ L. Because languages are sets of strings, there is also a
concatenation operation.
L1L2 = {yz | y ∈ L1 and z ∈ L2 } 32
Reminder: decidable languages A Turing machine M decides a language L if:
• When x ∈ L, then M accepts x (= halts in state Y).
• When x ∉ L, then M rejects x (= halts in state N).
Closure properties of decidable languages Theorem Decidable languages are closed under:
complementation union
intersection concatenation
Proof idea: swap Y and N.
Closure under union Suppose we have a TM M1 deciding L1 and a TM M2
deciding L2. The TM deciding L1 ∪ L2 has two tapes. If accepts
If rejects If accepts If rejects
(Can you detail this definition?)
run M1 on the first
tape copy of the input
(second tape is read-only)
Copy the input of the first tape also on the second tape.
run M2 on the second
tape copy of the input (first tape is read-only)
Closure properties of decidable languages
Theorem Decidable languages are closed under:
complementation union
intersection concatenation
Closure under concatenation Reminder L1L2 = {yz | y ∈ L1 and z ∈ L2 }
Assume M1 deciding L1 and M2 deciding L2. The TM deciding L1L2 is non-deterministic with two tapes.
If rejects If accepts
If rejects
If accepts
Non-determinism means: if there is at least one splitting x = yz such that y ∈ L1 and z ∈ L2, then x is accepted.
non- deterministically choose y and z
such that x = yz. Write y on tape 1 and z on tape 2.
Run M1 on y (tape 2 stays read-only).
run M2 on z. (tape 1 stays read-only).
Closure properties of decidable languages
Theorem Decidable languages are closed under:
complementation union
intersection concatenation
Reminder: recognisable languages
A Turing machine M recognises a language L if:
• When x ∈ L, then M halts on x.
• When x ∉ L, then M does not halt on x.
Closure properties of recognisable languages
Theorem Recognisable languages are closed under:
concatenation intersection
Closure under concatenation
Exercise: can we adapt the proof for decidable languages? Assume M1 recognising L1 and M2 recognising L2.
Consider the following TM for recognising L1L2. If rejects
non- deterministically choose y and z
such that x = yz. Write y on tape 1 and z on tape 2.
Run M1 on y (tape 2 stays read-only).
If accepts
If accepts
If rejects
run M2 on z. (tape 1 stays read-only).
Closure properties of decidable languages
Theorem Decidable languages are closed under:
concatenation intersection
Closure under union
Exercise: is the proof the same as for decidable languages? Assume M1 recognising L1 and M2 recognising L2.
Consider the following TM for recognising L1 ∪ L2. If accepts
run M1 on the first
tape copy of the input
(second tape is read-only)
Copy the input
of the first tape
also on the
in parallel, not sequentially.
If rejects
If accepts If rejects
second tape.
This is the problem. We need to run M1 and M2
run M2 on the second
tape copy of the input (first tape is read-only)
Closure properties of recognisable languages
Theorem Recognisable languages are closed under:
concatenation
intersection Exercise!
What about complementation?
Closure properties of recognisable languages
What about complementation?
Differently from decidable languages, recognisable languages are not closed under complementation. The proof will be given next week, because it is based on the existence of a recognisable language that is not decidable.
A useful trick
One can use closure properties to simplify proofs that a certain language is decided by a Turing machine.
For instance, in order to show that the language
L = {x ∈ {0,1}* | x has odd-length and more 1s than 0s}
is decidable, it suffices to show that
L1 = {x ∈ {0,1}* | x has odd-length}
L2 = {x ∈ {0,1}* | x has more 1s than 0s}
are decidable, because L = L1∩L2. 46
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com