FIT2014 Theory of Computation Lecture 18 Turing machines and computability
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 18
Turing machines and computability
slides by
based in part on previous slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 39
Overview
I Turing Machines
I Converting Finite Automaton to a Turing Machine
I Building Turing Machines
I Turing machines for computing functions
I Church’s thesis
2 / 39
Effective process = Algorithmic process
I Can be done with pencil and paper.
I Follows a finite set of instructions.
I Demands neither insight or ingenuity.
I Will definitely work without error.
I Produces in a finite number of steps either:
I A final result, or
I If the result is a sequence, each symbol in
the sequence.
(1912–1954)
http://www.npg.org.uk/collections/
search/portrait/mw165875
3 / 39
http://www.npg.org.uk/collections/search/portrait/mw165875
http://www.npg.org.uk/collections/search/portrait/mw165875
How to model computation?
Consider a person doing a computation (pencil & paper).
At any given time, the person is . . .
I focused on some particular position on the paper;
I reading the symbol at the current position;
I in some particular mental state, i.e., is doing some particular part of the
computation.
Depending on the state and symbol, the person then . . .
I writes a symbol there
(possibly overwriting what is already there);
I may change their state;
I moves their attention nearby.
4 / 39
Annie Jump Cannon (1863–1941)
Photo: Harvard College Observatory
http://www.skyandtelescope.com/astronomy-news/digitizing-harvards-century-of-sky/
w
w
w
.
g
o
o
g
l
e
.
c
o
m
1
1
D
e
c
2
0
1
4
h
t
t
p
:
/
/
w
w
w
.
p
e
l
i
c
a
n
p
u
b
.
c
o
m
/
p
r
o
d
d
e
t
a
i
l
.
p
h
p
?
p
r
o
d
=
9
7
8
1
5
8
9
8
0
9
1
1
6
carry . . .
go to top of column . . .
add column . . .
5 / 39
http://www.skyandtelescope.com/astronomy-news/digitizing-harvards-century-of-sky/
www.google.com
http://www.pelicanpub.com/proddetail.php?prod=9781589809116
http://www.pelicanpub.com/proddetail.php?prod=9781589809116
Turing machine
Tape:
I infinite sequence of cells (or squares)
I each cell may contain a symbol from a finite alphabet
I initially, the tape contains the input string, followed by empty cells (blanks)
. . . . . . . . . . . .
Tape Head:
I at any time, it is positioned at one cell of the tape
I can read the letter from the current tape cell.
I can write a letter onto the current tape cell.
I can move one unit left or right, at each step
6 / 39
Turing machine
Program:
I has a set of states, each numbered by an integer, including
I Start State (1)
I Accept State (2)
I optionally, a Reject State
I crash = reject.
I at any time, the machine is in one state
I initially, it’s in the Start State
I a state ‘ a single instruction or statement (but very low level!)
I transitions: for each state and symbol,
specify: next state, next symbol, and direction (one step left, or one step right).
(state, symbol) 7→ (next state, next symbol, direction).
Computation:
I At each step, apply the appropriate instruction.
I Computation is deterministic.
7 / 39
Initially:
∆ ∆. . . . . . . . . . . .
︸ ︷︷ ︸
input string
︸ ︷︷ ︸
all blanks
tape
head
program
1. · · · · · ·
2. · · · · · ·
· · · · · · · · ·
q. · · · · · ·
· · · · · · · · ·
8 / 39
Later:
. . . . . . . . .
tape
head
program
1. · · · · · ·
2. · · · · · ·
· · · · · · · · ·
q. · · · · · ·
· · · · · · · · ·
9 / 39
1
2
3 4
5
6
∆→ R
a→ A,R b→ B, L
A→ R
∆→ R
a→ LA→ R
a→ R
B→ R
B→ L
a→ L
B→ R
10 / 39
Languages associated with Turing machines
For a Turing Machine T :
I Accept(T )
I the set of strings leading to the Accept state.
I called the language accepted by T .
I Reject(T )
I the set of strings that crash, or lead to a Reject state (if there is one), during
execution.
I Loop(T )
I the set of strings that cause T to loop forever.
11 / 39
1 23
∆→ R
b→ R a→ R
b→ R
a→ R
Accept(T ) = strings with aa
Reject(T ) = strings without aa that end in a
Loop(T ) = ε or strings without aa that end in b
12 / 39
Deciders, decidability
A decider is a Turing machine T that halts for all inputs.
I i.e., Loop(T ) = ∅
Let L be a language.
A Turing machine T is a decider for L if T is a decider and Accept(T ) = L.
I So, Reject(T ) = L.
I Such a TM always decides, in finite time, whether or not any input string is in L.
It never “dithers” forever.
A language L is decidable if there is a decider T for it.
13 / 39
Finite Automaton −→ Turing Machine
Every Regular Language has a decider.
FA −→ TM:
1. Label start state with 1.
2. Label all other states with an integer ≥ 3.
3. Change the edge labels:
I a to a→ R
I b to b→ R
4. Delete the second circle from all the Final states, and add an edge from each
Final state to State 2, labelled with ∆→ R.
5. Make State 2 the sole Final state.
14 / 39
Problem
Build a Turing Machine that accepts the language {anbn : n ≥ 0}.
At start:
if ∆: Accept. ∆∆∆ ∆∆∆∆∆ ∆∆∆∆. . . . . . . . .
Otherwise . . .
15 / 39
At first a
a a a a a a b b b b ∆∆. . . . . . . . .
Mark first a
A a a a a b b b b b ∆∆. . . . . . . . .
Move to right,
until b A a a a a b b b b b ∆∆. . . . . . . . .
Mark b
A a a a a B b b b b ∆∆. . . . . . . . .
Move to first a
A a a a a B b b b b ∆∆. . . . . . . . .
16 / 39
At first a
A a a a a a B b b b ∆∆. . . . . . . . .
Mark first a
A A a a a B b b b b ∆∆. . . . . . . . .
Move to right,
until b A A a a a B b b b b ∆∆. . . . . . . . .
Mark b
A A a a a B B b b b ∆∆. . . . . . . . .
Move to first a
A A a a a B B b b b ∆∆. . . . . . . . .
17 / 39
. . . and so on . . .
. . . and so on . . .
. . . until eventually . . .
18 / 39
No first a !
Last A
followed by B A A A A A A B B B B ∆∆. . . . . . . . .
Move to right,
past every B A A A A A A B B B B ∆∆. . . . . . . . .
What is just
after last B? A A A A A A B B B B ∆∆. . . . . . . . .
If it’s ∆,
then Accept,
else Reject.
19 / 39
If the current letter is blank, then Accept string.
Loop {
If current letter is a then change a to A & move right.
Move right over every a and B.
If current letter is b then change b to B & move left.
Move left over every B.
If current letter is A then move right & exit the loop.
If current letter is a then move left over every a.
If current letter is A then move right.
}
Move right over every B.
If current letter is blank, then Accept string.
20 / 39
1
2
3 4
5
6
∆→ R
a→ A,R b→ B, L
A→ R
∆→ R
a→ LA→ R
a→ R
B→ R
B→ L
a→ L
B→ R
21 / 39
Example
Build a Turing Machine that accepts the language {anbnan : n ≥ 0}.
22 / 39
Example
Loop {
If current letter is blank, then Accept string.
If current letter is a, then change a to A & move right.
Move right over a∗bb∗.
If current letter is a, then move left.
If current letter is b, then change b to a & move right.
Move right over every a.
If current letter is blank, then delete aa on the left.
Move left over every a and b.
If current letter is A, then move right.
}
23 / 39
12
3 4 5
6
789
∆→ R
a→ A,R
b→ R a→ L
b→ a,R
∆→ L
a→ ∆, La→ ∆, L
A→ R
a→ R b→ R
a→ R
a→ L
b→ L
24 / 39
Other Machines
Queue automaton
I Like a deterministic PDA, but uses a Queue.
2PDA
I Like a deterministic PDA, but with 2 Stacks.
NTM
I A Nondeterministic Turing Machine.
kTM
I A Turing Machine with k Tapes.
25 / 39
Equivalences among these machines
Theorem.
Any language which a Turing machine can accept can also be defined
by any of these machines, and visa-versa.
There are algorithms to convert all these machines (including Turing Machines)
into each other.
26 / 39
Turing machines for computing functions
So far, our Turing machines just accept/reject.
TMs can also compute functions.
Function computed by a Turing machine M:
I Domain: Accept(M)
I If input string is x ∈ Accept(M):
x 7→ the string on the tape after M halts (excluding all the blanks at the end)
What kinds of objects can Turing machines work with?
Any objects that can be encoded as strings . . .
27 / 39
Encoding objects as strings
ASCII binary unary
0 bbaaaa a ε a0
1 bbaaab b a a1
2 bbaaba ba aa a2
3 bbaabb bb aaa a3
4 bbabaa baa aaaa a4
5 bbabab bab aaaaa a5
6 bbabba bba aaaaaa a6
7 bbabbb bbb aaaaaaa a7
8 bbbaaa baaa aaaaaaaa a8
9 bbbaab baab aaaaaaaaa a9
10 baba aaaaaaaaaa a10
11 babb aaaaaaaaaaa a11
12 bbaa aaaaaaaaaaaa a12
…
…
…
…
28 / 39
Encoding objects as strings
Unary code for tuples of nonnegative integers
I Each nonnegative integers is coded using the unary code: n 7→ an
I Integers are separated by b.
I Example:
(1, 0, 2, 3) 7→ abbaabaaa
I To extend to all integers:
adopt some convention to represent minus sign by a letter.
29 / 39
Successor
f (n) = n + 1.
Using the unary code for nonnegative integers:
∆∆∆∆ . . . a ∆∆∆ . . .
a ∆∆∆ . . . a a ∆∆ . . .
a a ∆∆ . . . a a a ∆ . . .
1 2
∆→ a,R
a→ R
30 / 39
Double
f (n) = 2n.
Using the unary code:
∆∆∆∆ . . . ∆∆∆∆ . . .
a ∆∆∆ . . . a a ∆∆ . . .
a a ∆∆ . . . a a a a ∆ . . .
31 / 39
Double
1 2
3
4 5
6
∆→ R
a→ #,R
∆→ A, L
#→ a,R
A→ a,R
∆→ L
a→ #,R
a→ R
A→ R
a→ L
A→ L
A→ a,R
32 / 39
Addition
f (n,m) = n + m, using the unary code for pairs of integers:
a b a ∆ . . .︸ ︷︷ ︸
1,1
a a ∆∆ . . .︸ ︷︷ ︸
1 + 1
a b ∆∆ . . .︸ ︷︷ ︸
1,0
a ∆∆∆ . . .︸︷︷︸
1 + 0
1 3 4 2
b→ a,R ∆→ L a→ ∆,R
a→ R a→ R
33 / 39
Computability
Definition
A function is computable if it is the function computed by some Turing machine.
This assumes that the function maps strings to strings, f : Σ∗ → Σ∗.
To be able to talk about computability of functions on other objects (numbers,
sequences, arrays, graphs, . . . ), we need to have in mind some reasonable scheme for
encoding the objects as strings.
For example, a function that takes any sequence of natural numbers and returns some
sequence of natural numbers is computable if, when the sequences are encoded as
strings (e.g., using the scheme we described earlier), the resulting function from strings
to strings is computable.
34 / 39
Variations on Turing machines
Variations on Turing machines
I Direction:
I stay still, as well as Left/Right
I Tapes:
I two-way infinite
I multiple tapes
I separate input, output, work tapes
I “tapes” of 2 or more dimensions
I . . .
Same class of computable functions
35 / 39
Other approaches to computability
Recursive function theory
I starting with ̈del, 1931
Lambda calculus
I , 1936
Turing machines
I , 1936–37
h
t
t
p
s
:
/
/
m
a
t
h
s
h
i
s
t
o
r
y
.
s
t
–
a
n
d
r
e
w
s
.
a
c
.
u
k
/
B
i
o
g
r
a
p
h
i
e
s
/
G
o
d
e
l
/
̈del (1906–1978)
h
t
t
p
s
:
/
/
m
a
t
h
s
h
i
s
t
o
r
y
.
s
t
–
a
n
d
r
e
w
s
.
a
c
.
u
k
/
B
i
o
g
r
a
p
h
i
e
s
/
C
h
u
r
c
h
/
(1903–1995) 36 / 39
https://mathshistory.st-andrews.ac.uk/Biographies/Godel/
https://mathshistory.st-andrews.ac.uk/Biographies/Godel/
https://mathshistory.st-andrews.ac.uk/Biographies/Church/
https://mathshistory.st-andrews.ac.uk/Biographies/Church/
https://mathshistory.st-andrews.ac.uk/Biographies/Church/
Church-Turing Thesis
Any function which can defined by an algorithm
can be computed by a Turing Machine.
Note: not a Theorem! But widely accepted.
Evidence:
I different approaches to computability end up in agreement;
I long experience, that algorithms can be implemented as programs, and therefore
on Turing machines;
I no known counterexamples, i.e., no algorithms which seem to be unimplementable.
37 / 39
I Centenary Year (2012) website: http://www.turingcentenary.eu/
I B. , Turing: Pioneer of the Information Age, OUP, 2013.
I Andrew Hodges, : The Enigma, Vintage, London, 1983.
I Andrew Hodges, Turing, Phoenix, London, 1997.
I Turing bibliography: http://www.turing.org.uk/sources/biblio.html
I G. Farr, Calls for a posthumous pardon . . . but who was ?,
The Conversation, 22 Dec 2011,
https://theconversation.com/
calls-for-a-posthumous-pardon-but-who-was-alan-turing-4773
I G. Farr, The Imitation Game: is it history, drama or myth?,
The Conversation, 9 Jan 2015,
https://theconversation.com/
the-imitation-game-is-it-history-drama-or-myth-35849
38 / 39
http://www.turingcentenary.eu/
http://www.turing.org.uk/sources/biblio.html
https://theconversation.com/calls-for-a-posthumous-pardon-but-who-was-alan-turing-4773
https://theconversation.com/calls-for-a-posthumous-pardon-but-who-was-alan-turing-4773
https://theconversation.com/the-imitation-game-is-it-history-drama-or-myth-35849
https://theconversation.com/the-imitation-game-is-it-history-drama-or-myth-35849
Revision
I Know what a Turing Machine is, and how to use one.
I Be able to convert a Finite Automaton into a TM.
I Be able to build a Turing Machine to define a language.
I Know the unary code for natural numbers, and tuples
I Know what a computable function is, and how to define one using a TM.
I Know and understand the Church-Turing Thesis.
Reading: Sipser, Ch. 3: Section 3.1, pp. 165–176, 181–190.
Preparation: Sipser, Ch. 3, start & end of Section 3.2; Section 3.3
39 / 39