3004
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture two
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP3004
What is a computer?
Are there limits to what a computer can do?
In this lecture
We begin the study of computability theory by introducing our first abstract model of computation: the Turing Machine (TM).
Towards Turing Machines
Alan Turing (1912-1954)
Known to the general public for deciphering the Enigma code in WW II
But before the war (1936) he wrote the paper:
On Computable Numbers, with an Application to the Entscheidungsproblem
Theoretical computer science was born.
Turing’s question
Turing’s article posed the question:
what is computation?
Turing’s Approach Watch a human being calculating something.
(S)he is following a set of rules
symbols are read and written (say on paper)
human behaviour changes depending on the symbol under examination.
Turing’s Approach Task of the scientist (Turing):
extract from this process what is essential and eliminate what is irrelevant.
Remember Aristotle Remember geometry
Essential vs accidental
What is essential?
Abstracting the data
What is essential?
Abstracting the actions
Write the symbol 0
Write the symbol 1
Move one square to the right
Move one square to the left
Observe the symbol currently scanned and choose the next step accordingly Stop
The Turing Machine
Turing Machine, informal definition
A Turing Machine has a single tape. The tape has a left end and is The leftmost cell is numbered 0 and is always marked with the
infinite to the right. It is divided into numbered cells.
Each cell on the tape can contain a symbol or be blank. Initially the tape is blank, with the exception that cell #0 contains ⊳ and any
input string a = a1 a2 … am is written in cells #2 to #m+1.
A Turing Machine has a head, which during the computation can be in a finite number of states.
Initially the head is in a distinguished starting state q0 and scanning cell #1.
Turing Machine, informal definition
At any time the head is reading the contents of a single cell on the
tape. Based on the current content of the cell and the current state,
the Turing Machine can do one of the following:
Change to a new state and either write a new symbol in the current cell or move one cell to the left or right.
There is an exception: if the head is reading the special symbol ⊳ (left end of the tape), then it can only move to the right.
The actions to be taken are specified by a program.
Turing Machine, formal definition A Turing Machine is a tuple ⟨ Σ, Q, q0, H, 𝛿 ⟩
Σ is a finite alphabet of symbols. It includes:
Q is a finite set of states.
q0∈Q is the initial state.
H⊆Q is the set of halting states. 𝛿 is the transition function
the blank symbol ⊔
the end of tape symbol ⊳
𝛿: (Q\H)xΣ → Qx(Σ⊎{→,←})
The transition function
𝛿: (Q\H)xΣ → Qx(Σ⊎{→,←})
𝛿 encapsulates the program governing the operation of the TM. 𝛿 is a total function.
We can write the definition of 𝛿 as a set of 4-tuples:
{⟨ qi, a, qj, ⊔ ⟩, ⟨ qk, ⊳, ql, →⟩,⟨ qi, b, qk, ←⟩,…}
current state
symbol being scanned
next state
action: write symbol or move left or move right
The transition function Two caveats on the definition of 𝛿:
If 𝛿(q, ⊳) = (q’,a) then a = → If 𝛿(q, a) = (q’,b) then b ≠ ⊳
𝛿: (Q\H)xΣ → Qx(Σ⊎{→,←})
Exercise: why these restrictions?
What does a TM compute? The alphabet of input/output symbols ΣI is Σ\{⊔, ⊳}.
⟨ Σ, Q, q0, H, 𝛿 ⟩
Halting state q∈H
The initial state
A toy example
⟨ Σ, Q, q0, H, 𝛿 ⟩
Σ = {1, ⊳, ⊔}
Q = {q0, q1, q2, h}
𝛿(q0,⊔) = (q1, →)
𝛿(q1,⊔) = (q2, 1) 𝛿(q2,⊔) = (h, ⊔)
What does this machine compute? Try it on
𝛿(q0,1) = (q1, →) 𝛿(q1,1) = (q1, →) 𝛿(q2,1) = (q2, ←)
𝛿(q, ⊳) = whatever for all q∈Q\H
A toy example
⊳⊔111 ⊳⊔11⊔
𝛿(q0,⊔) = (q1, →) 𝛿(q1,⊔) = (q2, 1) 𝛿(q2,⊔) = (h, ⊔)
𝛿(q0,1) = (q1, →) 𝛿(q1,1) = (q1, →) 𝛿(q2,1) = (q2, ←)
Diagrammatic Representation of Turing Machines
Σ = {1, ⊳, ⊔} ΣI = {1}
The “add 1” Turing Machine
Q = {q0, q1, q2, h} H = {h}
We only draw
configurations
𝛿(q0,⊔) = (q1, →) 𝛿(q1,⊔) = (q2, 1)
𝛿(q0,1) = (q1, →) 𝛿(q1,1) = (q1, →) 𝛿(q2,1) = (q2, ←)
𝛿(q2,⊔) = (h, ⊔)
𝛿(q, ⊳) = whatever for all q∈Q\H
Example: general unary addition Σ = {1, ★, ⊳, ⊔} ΣI = {1,★} Q = {q0, q1, q2, q3, q4, h} H = {h}
Numbers are represented in unary notation.
A k-tuple x ∈ Nk can be represented using unary
Computing functions Nk→N
What we have seen so far are Turing machines We can do that in general:
computing functions from Nk to N.
notation numbers separated by the ★ symbol.
Example: (4,5,1) ∈ N3 is encoded as
Thus the input alphabet is going to be ΣI = {1,★}.
1111★11111★1.
Example: unary multiplication by 2 Σ = {1, ★, ⊳, ⊔} ΣI = {1} Q = {q0, q1, q2, q3, q4, q5, q6, q7, h} H = {h}
“Forgotten” by History
Emil Post (1897-1954)
He anticipated many of the insights of Turing (and others, including Gödel), but his work remained unpublished for many years.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com