Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

'

$

Griffith University

3515ICT Theory of Computation
Turing Machines
(Based loosely on slides by Harald Søndergaard of
The University of Melbourne)

&

9-0

%

'

Overview

$

• Turing machines: a general model of
computation (3
...
2)
• Algorithms and the Church-Turing thesis
(3
...
1)
• The Halting Problem and other undecidable
problems (4
...
1)
• The Post Correspondence Problem and its
applications (5
...
28)
&

9-1

%

'

Alan Turing

$

• Born London, 1912
...

• Published landmark paper, 1936:
– Proposed most widely accepted formal
model for algorithmic computation
...

– Proved the existence of universal
machines
...

• Worked on UK cryptography program,
1939-1945
...

&
9-2

%

'

Alan Turing

(cont
...

• Proposed Turing Test for artificial
intelligence, 1950
...

• Arrested for homosexuality, 1952; died
(suicide), 1954
...

• See http://www
...
org
...


&

9-3

%

'

Turing Machines

$

So what was Turing’s computational model?
A Turing machine (TM ) is a finite state machine
with an infinite tape from which it reads its input
and on which it records its computations
...

Comparing a TM and a DFA or DPDA:
• A TM may both read from and write to its
input tape
...

• A TM halts immediately when it reaches an
accept or reject state
...
Q is a finite set of states,
2
...
Σ ⊆ Γ \ { } is the input alphabet,
4
...
q0 ∈ Q is the initial state,
6
...
qr ∈ Q (qr = qa ) is the reject state
...
the current state qi , and
2
...

It consists of three actions:
1
...
over-write tape symbol x by y, and
3
...

If the tape head is on the leftmost symbol,
moving left has no effect
...

On an arrow from qi to qj we write:
• x→d
if δ(qi , x) = (qj , x, d), and
• x → y, d if δ(qi , x) = (qj , y, d), y = x
...

This machine is not very interesting — it always
moves right and it never writes to its tape!
(Every regular language can be recognised by
such a machine
...

&

9-7

%

'

Turing Machine Configurations

$

We write uqv for this configuration:
u
v
blank

q
On input aba, the example machine goes through
these configurations:
εq0 aba
⊢

aq1 ba

⊢

abq0 a

⊢

abaq1

⊢

(or just q0 aba)

aba qr

We read the relation ‘⊢’ as ‘yields’
...

M accepts w iff there is a sequence of
configurations C0 , C1 , C2 ,
...
C0 is the start configuration q0 w,
2
...
, k − 1}, and
3
...


&

9-9

%

'

Turing Machines and Languages

$

The set of strings accepted by a Turing machine
M is the language recognised by M , L(M )
...
e
...
e
...

Three behaviours are possible for M on input w:
M may accept w, reject w, or fail to halt
...

A language A is Turing-decidable, or just
decidable, or computable, or (even) recursive iff
some Turing machine decides A
...
)
&
9-10

%

'

Example 2 (Sipser, Example 3
...


(Note that this language is not context-free
...
Read tape from left to right crossing off every
second 0
...
If the tape contained a single 0, accept
...
Otherwise, if the tape contained an odd
number of 0’s, reject
...
Return to the left of the tape
...
Go to step 1
...
)

This machine decides the language { 02 | n ≥ 0 }
...

It has input alphabet {0}, tape alphabet
{ , 0, x, #} and start state q1
...
9)

$

This machine decides the language
{ w#w | w ∈ {0, 1}∗ }
...
)
M3 = ‘On input string w:
1
...
If they do not, or if no # is
found, reject
...
When all symbols to the left of # have been
marked, check for any remaining symbols to
the right of #
...
’
See pp
...
3
...
145, for details
...
11)

$

This machine decides the language
{ ai bj ck | i × j = k, i, j, k > 0 }
...
)
An implementation-level description of the
machine follows
...
Cross off the first a, and scan to the right for
the first b
...

2
...
If there is another a, return
to step 1
...
If no c’s remain, accept,
else reject
...
)

This machine decides the language
{ ai bj ck | i × j = k, i, j, k > 0 }
...

The tape alphabet is { , a, b, c, A, B, C}
...
-, o

b→R

Õ
%
()*+–
/
...
-,
{a
BB
A→R {
a→L
{
b→L B
BB
{{
a→A,R
C→R
{
BB
{{
B {{
Õ
 w
9  B→R
()*+
/
...
-,
()*+
/
...
-,
a→R
C→R
y
c 



b→B,R
→L
B→b,L
b→L



 c→C,L  B→b,L
()*+
()*+
89:;
?>=<
G /
...
-,
qa

b→R

A→R

C→L

C→R

&

9-15

%

'

Example 5 (Sipser, Example 3
...
#xl | each xi ∈ {0, 1}∗ and
xi = xj for each i = j }
A machine to recognise (the non-CFL) E:
M = ‘On input w:
1
...
If it was blank,
accept
...

2
...
If no # is
found, accept
...
By zig-zagging, compare the strings to the
right of the two marked #’s; if they are equal,
reject
...
Move the rightmost of the two marks to the
next #, if any
...
Otherwise, accept
...
Go to step 3
...

E
...
, we may allow a ‘stay put’ move in addition
to the left and right moves, i
...
, we may define
the transition function as follows:
δ : Q × Γ → Q × Γ × {L, R, S}
...

I
...
, we can simulate ‘stay put’ TMs by ‘standard’
TMs
...

&
9-17

%

'

Variants of Turing Machines

(cont
...
e
...
(This is actually the most common
definition!)
• Let the TM have several tapes, each with its
own independent tape head, which may move
left or right or stay put
...

It turns out that none of these variants increase a
Turing machine’s capabilities as a recogniser!
&

9-18

%

'

Multitape Machines

$

A multitape Turing machine has k tapes
...
The
transition function now has the form
δ : Q × Γk → Q × Γk × {L, R}k
It specifies how the k tape heads behave when the
machine is in state qi , reading a1 ,
...
, ak ) = (qj , (b1 ,
...
, dk ))
state
control

b a a x x
b b b
&

x y a y x x

9-19

%

'

Multitape Machines

(cont
...
A language is Turing-recognisable iff
some multitape Turing machine recognises it
...
We show how to simulate a
multitape Turing machine M by a standard
Turing machine S
...

S initially reorganises its input x1 x2 · · · xn into
#x′ x2 · · · xn # ′ # · · · # ′ #
1
k−1

times

Symbols of Γ′ represent marked symbols from Γ,
and denote the positions of the tape heads on the
k tapes of M
...
)

$

For example, a possible correspondence is:
M

b a a x x
b b b
x y a y x x

S

# b′ a a x x # b b b

&

9-21

′

# x y a y x′

%

'

Multitape Machines

(cont
...
S then scans the
tape again, updating it according to M ’s
transition function
...
)
If a ‘virtual head’ of M moves to a # (i
...
, passes
the input on that tape), S shifts that symbol, and
every symbol after it, one cell to the right
...
It then continues to apply
M ’s transition function
...

I
...
, adding tapes to Turing machines do not
enable them to recognise any more languages
...
e
...

If some computation branch leads to accept, then
the machine accepts its input
...


&

9-23

%

'

Nondet
...
)

$

First, here is a deterministic machine, NEXT , to
generate {1,
...
-,A
} AA
AA
}}
}
→1,L }
AA →R
}
AA
} 1→2,L
AA
}}
}
AA
}
2→3,L
AA
}}

...

()*+~ g
/
...
-,

...
-,
‰

b→1,L

i→R

Try running this for b = 3, starting with a blank
tape
...
A language is Turing-recognisable iff
some nondeterministic Turing machine recognises
it
...
We need to show that every
nondeterministic Turing machine N can be
simulated by a (deterministic) Turing machine D
...

Let b be the largest number of choices, according
to N ’s transition function, for any state/symbol
combination
...

Tape 2 is used to simulate N ’s behaviour for each
sequence of choices given by tape 3
...
, b}∗ , in increasing length
...
)

$

D
3 1

1
...

2
...

3
...
Tape 3
determines how N makes each successive choice
...
If N accepts, accept
...
Replace the string on tape 3 by the next string
generated by the machine NEXT
...
Otherwise, go
to step 2
...
Turing Machines

(cont
...
e
...

A nondeterministic Turing machine that halts on
every branch of its computation on all inputs is
called a decider
...
A language is decidable iff some
nondeterministic Turing machine decides it
...
, b}∗ is an example of an
enumerator
...
, b}∗ ,
one after the other, never terminating
...

For an enumerator to generate a language L, it
must eventually generate (or print, or write) each
string w ∈ L
...

The reason why we also call Turing-recognisable
languages computably enumerable (or recursively
enumerable) is the following theorem
...
)

$

Theorem
...

Proof
...
Then we can build a
Turing machine recognising L as follows:
1
...

2
...
For each string s output by E, if
s = w, accept
...
Then we can build
an enumerator E by elaborating the enumerator
from a few slides back: We can enumerate Σ∗ ,
producing s1 , s2 ,
...
Let i = 1
...
Simulate M for i steps on each of s1 ,
...

3
...

4
...

&
9-29

%

'

Enumerators

(cont
...
A language L is Turing-decidable iff
some enumerator generates each string of L
exactly once, in order of nondecreasing length
...
Exercise for the reader
...
)

&

9-30

%

'

Restricted TMs

$

Adding capabilities to TMs does not give more
power
...
Every TM can be simulated by a TM
with a binary tape alphabet Γ = {1, B}
...
Not every TM can be simulated by a
TM whose head always remains on the cells
containing the initial input
...
)

$

(Deterministic) Turing machines have been
proved to have the same expressive power as each
of the following computational models:
• Doubly-infinite Turing machines
• Multitape Turing machines
• Nondeterministic Turing machines
• Binary-tape-alphabet Turing machines
• Two-stack pushdown automata
• Queue machines
• Lambda-calculus expressions
• Recursively defined (numeric) functions
• Lisp-definable (symbolic) functions
• Register machines (effectively, stored program
computers, with infinite storage)
• Many other models!
&

9-32

%

'

The Church-Turing Thesis

$

Church and Turing (in effect) proposed the
following thesis:
A problem (or language) is
(algorithmically) decidable if and only if
some Turing machine can decide it
...

We cannot prove this thesis because it concerns
the informal concepts ‘algorithmically decidable’
and ‘algorithmically computable’
...

&
9-33

%

'

An example

$

Hilbert’s tenth problem (1900)
...
g
...

As it turns (Matijasevi˘ 1970), no such algorithm
c
exists! I
...
, Matijasevi˘ proved that the problem
c
“Does polynomial p have integral roots?”
is not algorithmically decidable
...


&

9-34

%

'

An example

(cont
...

To see this, here is how we can build a Turing
machine M to recognise P
...

M can enumerate all integer triples (i, j, k)
...

If any of these evaluations returns 0, M accepts
...
)

&

9-35

%

'

Descriptions of TMs

$

Turing machines may be described at different
levels:
1
...
Implementation description (data
representation on tape, head movement,
procedural)
3
...
Arithmetic
2
...
Context-free grammars
4
...
g, see Example 3
...
157–159
...

These two observations mean that TMs can be
used as general computing machines, not just as
language recognisers

---