CS计算机代考程序代写 scheme Lambda Calculus algorithm FIT2014 Theory of Computation Lecture 18 Turing machines and computability

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