COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture seven 1
Copyright By PowCoder代写 加微信 powcoder
Turing Machines
Decidable and recognisable problems/languages The Church-Turing thesis
Evidences of the Church-Turing thesis:
Variations of the definition of Turing machine Other models of computation
Previously on COMP0017
In this lecture
We discuss a key concept of computer science:
the possibility of a universal Turing machine.
Towards universal machines
A little experiment
Pick a word processor program, say Microsoft Word.
Let’s now open a *.doc file with Microsoft Word.
Let’s then open a *.exe file with Microsoft Word.
A little experiment
What do we observe?
Unlike with *.doc files, Microsoft Word does not produce a meaningful output with *exe files.
A little experiment
What do we observe?
However, the important observation is that in principle Microsoft Word can run on *.exe files.
It can even run on itself (WINWORD.exe).
A little experiment
What we learned
1. Any program can be run with any file as input.
(although the resulting output will be garbage unless the input was intentionally
produced to work with the program.)
2. Programs are just files. Thus a program can run with
another program as input.
3. A program can be run using its own file as the input.
Universal programs
A universal program is one that treats other programs as meaningful inputs and runs them.
Input program P
Universal program
Output of P on x
Universal programs
Operating systems (Windows, OS-X, Linux, …) are examples of universal programs.
When you click on a file, the operating system selects a program to run that file.
Microsoft Word
*.doc file
Operating system
Visualise the
file in Word.
Universal programs
Actually, modern computer architectures are nothing but layers of universal computational devices.
Universal programs
An interpreter is another example of universal program.
Python program P
Python interpreter
Output of P on x
A Python interpreter can be written in Python.
A bit of history
All of these concepts are descendants of Turing’s intuition of a Universal Turing machine (introduced in his 1936 paper).
A bit of history
Throughout human history, computational devices were mostly designed to do one thing (run a single program, accomplish a single task).
General-purpose machines are a modern invention (by Turing, and to some extent C. Babbage). The key advancement was to understand that there is no intrinsic difference between programs and their data.
A universal machine is one that is in principle capable of accomplishing any algorithmic task (it is programmable). 14
Self-reflection
Last week we saw how URMs can be coded as input data for a Turing machine.
Now we will see that Turing machines themselves can be coded as input data for other Turing machines.
This kind of self-reflecting encoding is sometimes called Gödelization, after ̈del. He introduced it to encode statements about arithmetic within arithmetic itself, a key step of his incompleteness theorem (1931).
This idea is still very present in modern programming
(interpreters, higher order functions, object oriented, …) 15
The universal Turing machine The UTM takes as input a string y.
• First, it checks whether y is the encoding of a TM M and
of a string x in the alphabet ΣI of M.
• If so, the UTM simulates the action of M on x
Check if y = code(M)code(x)
for some M, x.
Run M on x.
We’ll define code(-) later.
If M halts on x, and produces z
If M does not halt on x
What it means to simulate M Running the Universal Turing Machine on input y =
code(M)code(x) should yield the same outcome as running M on input x.
UTM does not halt on code(M)code(x)
UTM halts on code(M)code(x)
with output z.
M does not halt on x
M halts on x with output z.
Existence of a Universal Turing Machine Theorem A Universal Turing Machine exists.
Proof We are going to explicitly construct one (in the same way as Turing did).
Encoding Turing Machines
Encoding Turing machines
We first focus on the definition of code(-).
It will translate a TM into a string over the alphabet {0,1}.
Disclaimer: there are many perfectly acceptable ways of doing this.
Encoding Turing machines M = ⟨ Σ, Q, q0, H, 𝛿 ⟩
We first introduce a few conventions.
the states in Q are ordered as q0, q1, q2, … with q0 initial. We order symbols that may appear in the definition of 𝛿
𝜎0 = ⊔ 𝜎1 = ⊳ 𝜎2 = → 𝜎3 = ← and order the remaining symbols from Σ as 𝜎4, 𝜎5, …
We can then encode states and symbols as strings of 1s:
code(qi) = 11…1 i+1 times
code(𝜎i) = 11…1 i+1 times
We encode a single tuple t = ⟨ qi, 𝜎n, qj, 𝜎m ⟩ of 𝛿 as: code(t) = code(qi)0code(𝜎n)0code(qj)0code(𝜎m)0
And the whole of 𝛿 = {t1, t2, …, tk} as
code(𝛿) = code(t1)0code(t2)0…0code(tk)0
Halting states in H can be inferred as those on which 𝛿 åis not defined (= they never occur in second position in a tuple).
Encoding Turing machines M = ⟨ Σ, Q, q0, H, 𝛿 ⟩
Consider M with Σ = {a, b, ⊔, ⊳}, Q = {q0, q1, q2, q3},
H = {q3}. It appends b to its input string.
We stick to our convention and call
𝜎0=⊔ 𝜎1=⊳𝜎2=→ 𝜎3=← 𝜎4=a𝜎5=b
Writing the program 𝛿 as set of tuples, we have
Example The tuples are coded as:
Finally, the Turing machine M in its entirety is encoded as
Inputs of M can be encoded similarly:
code(𝜎i1𝜎i2…𝜎in) = 00code(𝜎i1)0code(𝜎i2)0…0code(𝜎in). 26
Observations on the encoding
It is possible to have two or more machines that do the same job, but correspond to different strings in the encoding (e.g. if they use different states).
Nonetheless, the coding is 1-to-1, that means, two
different machines will be encoded as different strings.
Given a string over {0,1}, it’s possible to tell whether or decidable problem.
not it is the code of some TM. In fact, this is a
Check if y = code(M)code(x) for
some M, x. 27
Constructing the universal Turing machine
Running the Universal Turing Machine on input y =
code(M)code(x) should yield the same outcome as running M on input x.
UTM does not halt on code(M)code(x)
UTM halts on code(M)code(x)
with output z.
M does not halt on x
M halts on x with output z.
Definition of the UTM The UTM is defined as a three-tapes Turing machine.
Tape 1 will maintain the tape of M in encoded form. Tape 2 will maintain code(M).
Tape 3 will maintain the current state of M in encoded form. 30
Definition of the UTM To start a simulation of the UTM:
1. Preparation step: check if y = code(M)code(x) for some TM M and input x. If not, loop. If yes, it means tape 1 contains code(M)code(x). Go to step 2.
2. Move code(M) from tape 1 to tape 2.
3. Shift code(x) on tape 1 to the left and precede it with
code(⊳)0code(⊔)0. Now tape 1 contains the starting tape of M on input x, in encoded form.
4. Write code(q0) on tape 3.
5. Place head 1 at encoded ⊔ before code(x), head 2 at the
start of code(M), and head three at the start of code(q0). 31
Definition of the UTM
One step of the simulation of M by the UTM works as follows.
1. Search in code(M) for a tuple where the first element matches the state stored on tape 3 and the second
part matches the symbol currently scanned by M.
2. Use the fourth element of the tuple to update tape 1
and the position (if necessary) of head 1.
3. Use the third element of the tuple to write the new
state that M will move to on tape 3; or, if M has reached a halt state, halt.
Final consideration This construction shows the existence of a universal
Turing machine MU.
Nothing prevents MU from receiving itself (in the
encoded form code(MU)) as input of a computation! This observation will be used in the next lecture to prove
that some problems are undecidable. 33
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com