Turing Machines
COMP1600 / COMP6260
Australian National University
Semester 2, 2021
1/45
(1912–1954)
2/45
2/45
Turing’s Scientific contributions
1936
introduces Turing machines and the study of computability 1950.
introduces the Turing test that turns AI into a concrete research problem
current today: Mitsuku, a computer programme has convinced judges (for the last 5 competitions – from 2013 to 2019) that it was a 18-year-old female from Leeds, England.
1952.
Pioneering work on computation in nature;
Also. Key figure in the invention of the earliest modern computers.
3/45
3/45
Turing at War
Germany
Germans used enigma machines – most sophisticated crypto equipment
The U.K.
code breaking effort assembled at Bletchley park Turing chief scientific genius
Achievements
cracked secret Enigma code
estimated to have shortened world war II by 2 years
Fallout
may ideas and technologies discovered in Bletchley park fed directly into modern computers
4/45
4/45
Death and Legacy
1952
less than 10 years after heroic war efforts for the UK Turing prosecuted for ‘crime’ of homosexuality sentenced to chemical castration
1954
death by suicide
Legacy Now
widely recognised as the father of computing Turing award equivalent of Nobel prize
UK government apologised for persecution in 2009 2012 officially named the Turing year
Royal Pardon in 2013
5/45
5/45
Turing Machines – Introduction
Computability – 1936 paper
On computable numbers, with an application to the Entschei- dungsproblem
solved long standing open problem posed by Hilbert
changed the world (of mathematics, and computing)
simple mathematical device that is able to simulate any computer this device instrumental in solving Hilbert’s problem
Modern Computers
didn’t exist in 1936?
ENIAC in 1946 generally considered to be the first
6/45
6/45
Computing as a profession
Photo c/o Early Office Museum Archives
7/45
7/45
A model for ‘computers’
Computing in 1936
computers not machines, it was a profession.
Turing’s contribution: mathematical definition of what computers can do.
justification: references to ‘state of mind’ or similar
see original paper, Section 9.I (quite readable!) http: //www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Turing’s model today
no computer has been built that is more powerful than Turing’s model Turing has discovered the essence of computation
Mathematical Models vs Reality
no formal proof that the model is the “right” one but widely accepted
new paradigms emerge, e.g. quantum computing
8/45
8/45
Push Down Automata, reloaded
a0
read head
a1
a2
…
. . . .
an input tape
Finite
State Control
zk
A PDA with its auxiliary store is almost a whole computer, except we can only directly access the symbol on the top of the stack.
9/45
stack
memory z2
z1
9/45
Turing Machines
a0
read head
a1
a2 …
Finite
State Control
. . . .
an input tape
Generalisation from PDA to Turing machine
replace stack memory by tape memory
can access arbitrary symbols on tape by moving tape head
read
write head
zk
z2 z1
tape memory
10/45
10/45
Single tape Turing Machines
input data a0 a1
an
scratch space
z0 z1 zk
read / write head
Simplification.
Finite
State Control
have the same tape both for input and for storage tape is assumed to be infinite in both directions analogy: “get more paper if you run out”
11/45
11/45
Turing Machines as language recognisers
Deterministic Machines for the time being
at every time of the computation, at most one action is possible
If there is no action that is legal, the TM halts
If a TM halts in a final state, it has accepted the original input. The set of strings accepted by a TM is its language.
If it halts in a non-final state, this is an ‘error’, i.e. the input is rejected.
A TM may also loop forever…
Definition. If a language is recognised by a Turing machine, then it is called recursively enumerable.
12/45
12/45
Output
Turing Machines as Computing Devices
TMs can calculate any computable function.
input: a string written onto the tape before the machine starts output: whatever is left on the tape when the machine halts
Infinite Tapes aren’t a problem
computation halts after finitely many steps only finitely many tape cells will be written to
13/45
13/45
Turing Machine – formal definition
A Turing Machine has the form (S,s0,F, Γ,Σ,Λ, δ), where
S isthesetofstates,s0 ∈S istheinitialstateandF ⊆S arethe
final states;
Γ is the set of tape symbols, Σ ⊆ Γ is the set of input symbols, and
Λ ∈ Γ − Σ is the blank symbol.
δ is a (partial) transition function
δ : S×Γ → S×Γ×{L,R,S}
(state, tape symbol) → (new state, new tape symbol, direction)
The direction tells the read/write head which way to go next: Left, Right, or Stay.
14/45
14/45
Running a TM
Initialisation.
some input (a finite string over Σ) is written on the tape;
every other tape cell is a blank – Λ;
the read/write head sits over the some cell of the input (or over any Λ is the input is ε);
the state is the start state s0. Running.
in a cycle: read symbol and execute action (state dependent): move/write/change state
until a final state is reached (or the machine gets stuck)
15/45
15/45
Graphical Representation of the Transition Function
Λ Λ
1,L
– S 0 6
– S 1
– H
1,S
1 1,L
(Like FSA, annotate transition edges with commands for accessing tape.)
Convention.
Numerator: symbol read from tape.
Λ means the tape is blank at that position.
Denominator: symbol written / direction of head movement. direction one of L, R, S for Left, Right, Stay.
16/45
16/45
What does it do?
111111
@ @ head
1,L
Λ Λ
– S 0 6
– S 1
– H
1,S
1 1,L
Adds two to a unary number!
Assume the head starts over the input data. First phase scans left.
Second phase writes two extra 1s.
17/45
17/45
The Convention for Errors
Λ Λ
1,L
– S 0 6
– S 1
– H
1,S
1 1,L
TMs getting Stuck
suppose that the input contains a token other than 1.
TM would halt in state S0, as there is no arc telling us what to do if we meet such a token (this is the job of the rightwards scan).
this is an error – the input is rejected.
S0 not an accepting state!
Language
TM accepts precisely {1n | n ∈ N}. Alternative Formulation (not used here)
could add an error state that the machine transitions to error state not accepting
18/45
18/45
What does this one do?
0 0 0,R 1,L
? ? ΛΛ
Λ,L
– S0 66
– S1 1 1
– H
Λ,R
1,R 0,L
Questions.
Do you see two phases?
What does each phase accomplish?
19/45
19/45
What does this one do?
0 0 0,R 1,L
? ? ΛΛ
Λ,L
– S0 66
– S1 1 1
– H
Λ,R
1,R 0,L
Answer.
Phase 1: initialisation.
Phase 2: computation, in this case, complement a binary number.
20/45
20/45
Harder Problems?
Incrementing a binary number
You should try this!
Adding numbers – need terminators
Convenient to write the result before the data. Multiplication – and so on!
1
0
0
0
1
0
1
1
#1
1
0
0
0
1
#1
1
1
0
1
1
#
21/45
21/45
Incrementing a binary number
Example. Number increment
Solution:
0 0,R
1
0
0
0
1
0
1
1
? Λ 0
S Λ,L S 1,S H
-0 -1Λ-
1,S 66
1 1 1,R 0,L
22/45
22/45
Decrement
Example. Number decrement (similar)
0 0,R
1
0
0
0
1
0
1
1
? Λ 1
S Λ,L S 0,S H
– 0 – 1 -
66
1 0 1,R 1,L
Failure (or non-acceptance): If given number is 0 it fails (at state S1),
23/45
23/45
How to add two numbers?
Input. Binary numbers separated by #, say nm
Operation.
10100101 # 100101010
Go back and forth between m and n, decrementing one (until this fails) and incrementing the other.
decrement m, and increment n, because n will expand leftwards. m gets changed to 00…0, n is replaced by the sum.
Finally, delete the #00 · · · 0 on the right.
24/45
24/45
How to add two numbers? ctd.
1 Λ,R
? Λ
1
0 1,R #
SΛ,S H
4 -
0,R#,R #6
Z} Z66
Λ,R Λ1
? S Λ,L S 0,S
– 2 S
– 0 – 1
1,S 1,S Z 1,L #,L 0,L 1,L
Z 0ΛZ0#01
Z
Z =
S3
6
1 0,L
25/45
25/45
How to multiply two numbers?
Input. as for addition
Operation.
# 10100101 # 100101010
pnm
Repeatedly decrement m (until this fails) and add n to p (p is initially blank)
Must modify the addition routine to not erase the number n being added.
Modification of addition routine
Two new tape symbols, 0′ and 1′.
Before each addition stage, change all the 1s in n to 1′.
When decrementing n, swap 0s and 1s as usual, but keep the primes. When finished adding n to p, go back and use the primes to restore n.
Observation.
this is very tedious – but the model is simple and easy to analyse tricks that you see here are typical
26/45
26/45
Programming Issues – Data
Data Types and Gadgets
not present in the model
but can be simulated . . .
Numbers.
Usually use unary or binary for integers.
Vocabulary.
Can be arbitrary, and {0, 1} suffice. Characters are represented as strings of bits.
Variables, Arrays, Files
Use markers on the tape to separate values.
27/45
27/45
Programming Issues – Control
Common Idioms.
Scan to blank, or to find, insert, delete a symbol.
Use control states to remember information
In particular, we often need to “remember” a symbol, to write it elsewhere: this typically requires a set of states, one per symbol
Composition
If you have a TM to multiply by 3 and one to multiply by 5, put them together to multiply by 15.
Decisions (conditional computation)
As we have seen, we can branch on 0 or 1 (or T or F).
Loops — of course.
28/45
28/45
Using States to Remember a Tape Symbol
1 1,L
0U1 0,R 0 1,R
Λ
0,L 0 Λ,R
Λ SΛ,RT
Given a string of 0 or 1 surrounded by blanks, this machine repeatedly forever erases the leftmost bit, and writes it on the right hand end. (Not so useful, but illustrates the point)
We use the choice of states U0 or U1 to remember which symbol has been erased and is to be written
0
0,L 1
Λ Λ,R 1,L
0U1 0,R 1 1,R
29/45
29/45
Universal Turing Machines and Turing Completeness
We can construct a TM to simulate any conventional computer. (Cost effectiveness is not brilliant.)
From this point, just think of a TM as like a computer program (with a machine that will run it)
We can construct a TM that first reads a description of some other TM and then simulates it. This is a universal TM. (Think of a Haskell program whose purpose is to read any other Haskell program and run that)
Turing machines can simulate themselves.
Turing machines can compute properties of themselves.
Any computing device which can simulate a universal Turing Machine is also called universal or Turing Complete.
30/45
30/45
Church-Turing Thesis
Church-Turing Thesis.
If a function is computable, then it can be calculated by a Turing machine.
Equivalent Formulation.
if a problem can be solved by an algorithm, then it can be solved by a Turing machine.
This is a Thesis.
more a definition than a theorem
can never be proved: what does algorithmic mean? however, there’s lots of evidence
Evidence.
all other definitions of the term computable give the same class of
computable functions
there are many: λ-calculus, register machines, while programs, etc. 31/45 31/45
Church and λ-calculus
Example. The (untyped) λ-calculus
proposed by (the Church in the Church-Turing thesis) in 1932, even before Turing’s paper
Rosser showed that both notions are equivalent
Equivalence. (Rosser, 1939)
if a function is computable by a Turing machine, then it is
computable in the λ-calculus
…and vice versa
simulation of the respective formalism in the other approach.
32/45
32/45
Can real computers simulate Turing Machines?
Differences between computers and Turing machines A Turing Machine has an infinite tape.
“real” computers have finite memory (sometimes a lot, but nowhere near infinite)
physical devices necessarily have finite memory. They’re more like finite automata.
. . . but the number of states can be very, very large. How big is 24294967296?
physical computers are an approximation of TMs.
Intuitive Understanding
Turing machine model feels closer to what we can program
e.g. we can recognise the language {anbn | n ≥ 0}
if the real machines runs out of memory . . . we can always buy more this is about computation in principle
33/45
33/45
Church-Turing Thesis: Argument 1
Turing Machines emulate humans.
comparison how humans perform tasks
Turing’s ‘computers’ only perform TM operations: writing, reading, refocussing (state change)
TMs are finite like humans
can’t do infinite operations, e.g. work with infinitely many symbols can’t read the whole infinite tape
Taken together
convincing (in the 1930s) that Turing’s model is correct but no mathematical evidence (yet)
34/45
34/45
Church-Turing Thesis: Argument 2
Stability of the TM Model.
adding ‘features’ doesn’t make more functions computable
Multi-tape.
have extra tapes to store data
easier to program, but no extra “power” (single-tape can simulate multi-tape)
Multi-head.
have more than one head, heads can move independently heads can access multiple symbols at once
again, no extra power
Non-determinism. (as for nfa’s)
tm can make one of several possible next moves
tm can “guess” the right next move
may make it faster, but cannot compute more functions.
35/45
35/45
Church-Turing Thesis: Argument 3
Many Models of Computation
plenty of different definitions of what computable may mean different purposes, different contexts
Main Insight.
any (reasonable) model of computation can compute precisely the same functions as the TM model.
“reasonable” in the sense of modelled on mechanical computation
Examples.
Lambda-Calculus (Church, 1932) Post-Systems (Post, 1939) Register Machines
…
Doesn’t include
models based on physical phenomena …or biology, or …
36/45
36/45
Argument 3B: Grammars
Theorem. Any language that is generated by a grammar can be recognised by a Turing machine.
Proof (Sketch)
write the start symbol S onto the tape (say, right of our input) search through all possible derivations from S
each time we reach a sentence, check whether it matches the input
Acceptance.
if the grammar finds the input, we will find a derivation
if the grammar does not generate the input, we may loop forever (and not accept)
37/45
37/45
Argument 3B – grammars ctd
Unrestricted Grammars. Have productions of the form α→β
where β is arbitrary, and α contains at least one non-terminal.
Theorem. For any TM, there exists a grammar that generates precisely the
words that the TM accepts.
Proof (Sketch)
non-terminals (of the grammar) are states of the TM
run TM “backwards” (we are interested in inputs, not outputs)
0 T 1,R U
–
TM Transition. Grammar Production. 1U → T0.
(Detail missing, e.g. how to handle blanks)
38/45
38/45
Argument 3C – Computers & Programming Languages
Observation.
no computer ever invented could do things that a TM can’t do no programming language can do more than a TM back-and-forth translation TM ↔ PL
Common Terminology.
A programming language that can compute every function that can be computed by a Turing machine is called Turing complete.
Examples.
The languages that you know: Haskell, Java, Python, . . .
even the simple while language that we used for Hoare logic implement TM simulator in your favourite programming language
39/45
39/45
Argument 3D – ’s Game of Life
Game of Life.
infinite 2d grid
finitely many cells marked alive, all others are dead
Rules of the Game. iterate through generations
live cells with fewer than two live neighbours die (under-population)
live cells with more than three live neighbours die (over-population);
dead cells with exactly three live neighbours come alive (reproduction);
all other cells stay as they are.
Emergent Behaviour.
visualised by GoL, many interesting forms
analogy of complex behaviour emerging from simple rules
40/45
40/45
Argument 3D – ’s Game of Life ctd.
From TM’s to Conway’s Game
can implement Game of Life on a Turing machine lots of coding, in particular 2d grid onto 1d tape
From Conway’s Game to TMs ( , 2011)
showed that GoL can simulate Turing machines
comes down to clever choice of initial configurations see
http://rendell-attic.org/gol/turing_js_r.gif
41/45
41/45
are programs that have other programs as input or output. Examples
Lexical analysers and parser generators SPARK Examiner, which automatically proves correctness properties of programs written in SPARK Ada;
Code generation which automatically produces codes from e.g. a Z specification or a formal proof
Next Goal. Scrutinise TMs that take TMs as input. main goal: halting problem
42/45
42/45
Coding a TM onto tape
Coding of a TM as binary strings can be written onto a tape
just code the transition function
States are ordered S1, S2, . . . , Sk , where S1 is the start state and S2 the unique final state
Tape Symbols are ordered X1,X2,X3,…,Xl where X1 is 0, X2 is 1, and X3 is Λ.
Directions {L, R, S} as D1, D2, D3 respectively. Transitionsδ(Si,Xj) = (Sk,Xl,Dm)mappedto
0i 10j 10k 10l 10m (the 0s carry information, the 1s act as separators.)
43/45
43/45
Coding a TM onto tape ctd.
Coding of all transitions. A TM with transitions C1, . . . , Cn is codes as C1 11C2 11 ··· 11Cn
(11 is used as a separator for transitions)
Additional Input.
code for a TM, and additional string
use 111 to separate TM and string input
44/45
44/45
Coding a TM onto tape – example
Λ Λ
1,R
– S1 6
– S3
– S2
1,S
1 1,R
The transitions are
0 1 00 1 0 1 00 1 00
0 1 000 1 000 1 00 1 00
000 1 000 1 00 1 00 1 000
Recall: States, Symbols, Directions.
So the TM as a whole is encoded by the binary string
010010100100 11 010001000100100 11 00010001001001000
45/45
45/45