# CS代考 Turing Machines – cscodehelp代写

Turing Machines

COMP1600 / COMP6260

Australian National University

Semester 2, 2020

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: in June 2014, , a computer programme convinced 33% of judges that it was a 13-year-old boy.

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

Short video

https://www.youtube.com/watch?v=S5CjKEFb-sM

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 (Q,q0,F, Γ,Σ,Λ, δ), where

Q isthesetofstates,q0 ∈Q istheinitialstateandF ⊆Q 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

δ : Q×Γ → Q×Γ×{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 q0. 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

– S1 66

– H

– S0

1 1

Λ,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