Transcript Turing Machines

::ICS 804::
Theory of Computation
- Ibrahim Otieno [email protected]
+254-0722-429297
SCI/ICT Building Rm. G15
Course Outline







Mathematical Preliminaries
Turing Machines
Recursion Theory
Markov Algorithms
Register Machines
Regular Languages and finite-state
automata
Aspects of Computability
Last Time: Turing Machines







What is Computation?
Informal Description of Turing Machines
Formal Description of Turing Machines
Turing Machines as Language acceptors and
Language recognizers
Turing Machines as Computers of numbertheoretic functions
Modular Turing Machines
Complexity Theory
Course Outline


Mathematical Preliminaries
Turing Machines
◦





Additional Varieties of Turing Machines
Recursion Theory
Markov Algorithms
Register Machines
Regular Languages and finite-state automata
Aspects of Computability
Additional Varieties of Turing Machines









Turing Machines with One-Way-Infinite tape
Turing Machines that accept by terminal state
Multitape Turing Machines
Encoding of Turing Machines
Universal Turing Machines
Nondeterministic Turing Machines
Turing-Computability
Turing Machines and Artificial Intelligence
Turing Machines and Cognitive Science
Turing Machines with One-Way-Infinite Tape
Tapes
So far: Turing machines with two-way infinite
tape
 Turing (1936): one-way infinite tape
 No difference in computational power
 A function Turing computable in a 2-way
infinite tape setup is also Turing computable
with a 1-way infinite tape

Turing Machines with One-Way-Infinite Tape
Machine tape infinite only to the right
 Leftmost tape square containing left
endmarker  (use , in Deus Ex Machina)
 What happens on reaching left most square?
 One-way function computation
 One-way language acceptance (recognition)

Equivalence Result

Central to theory of computability

Let f be a k-ary number-theoretic function:
Then there exists a Turing Machine with
two-way-infinite tape that two-way
computes f if and only if there exists a
Turing machine with one-way-infinite tape
that one-way computes f

Turing Machines that accept by
terminal state
Acceptance (Recap)
Word acceptance:
Deterministic Turing Machine M accepts
nonempty word w if, when started scanning
the leftmost symbol of w on an input tape
that contains w and is otherwise blank, M
ultimately halts scanning a 1 on an otherwise
blank tape.


“Acceptance by 1”
Terminal State
A single terminal state qt ( “one or more”)
 Sex-tuple Q, S, G, qinit, qt , d 

◦ qt  Q
◦ d is undefined for pairs of the form < qt , d >
◦ Turing Machine M can still halt in any
other state
◦ Not necessarily distinct from qinit
◦ Exercise: Draw a TM that accepts L = {
(abc)n | n >=1} by terminal state
Language Acceptance by Terminal State
M accepts w if halts in qt
 M accepts language L by terminal state provided
that M accepts, by terminal state, all and only
the words of L

◦ Tape content upon halting in state qt is not defined
◦ No requirement that M has read word w
completely
Equivalence Result
Theorem: Let L be a language over
alphabet S. Then there exists a Turing
machine that accepts L “by 1” if and only
if there exists a Turing machine that
accepts L by terminal state.
 Equivalence result: forward and reverse
proof involve maintaining new end
markers  and 

Multitape Turing Machines
Multitape Turing Machines
Has K+2 tapes where K >= 0
 (Possibly read-only) input tape at top
 (Possibly write-only) output tape at
bottom
 0 or more worktapes in between
 Referred to as offline TM

No worktapes
Initially
input tape: H11111111
output tape: HB
Ultimately halts in the configuration
input tape: H11111111 (unchanged)
output tape: H1111
Worktapes
Initially
input tape:
worktape1:
worktape2:
…
output tape:
HababB
HBBBBB
HBBBBB
HBBBBB
Ultimately halts in the configuration
input tape:
worktape1:
worktape2:
…
output tape:
HababB (unchanged)
…
…
H1BBB
Clarification

Let M be a multitape Turing machine.
Suppose that tape t is one of M’s k + 2 tapes.
In general, determination of which action is to
be taken by the read/write head on tape t will
depend on the symbols currently being
scanned on tapes other than t and not merely
on the symbol currently being scanned on
tape t itself.
Language Acceptance
Suppose that (k+2)-tape Turing Machine M is
started scanning the leftmost symbol of
nonempty input word w on its input tape,
which is otherwise blank initially.
Suppose all the other tapes are blank as well.
Then if M halts with its first read-head
scanning the leftmost symbol of w on its
input tape, which is otherwise blank, and
scanning a single 1 on its output tape, which
is otherwise blank, then we shall say that M
accepts word w
Example
{w *|na(w) = nb(w)}
Example

Instructions for each tape. Often: only 1 tape is reading/writing.
Other tapes: “a:a” type instructions
Example

Copies occurrences of a unto worktape1 and occurrences of b unto
worktape2. Then M ascertains whether the number of a’s on worktape1 is
the same as the number of b’s on worktape2
Example
Deus Ex Machina:
◦ Machine: SAMNUM4T.TM
◦ Try tapes 6A4BMULT.TT and 9A9BMULT.TT
Example
Calculate Time complexity
Single-tape: O(n2)
Multi-tape: O(n)
Parallel Computation?
Let M be a multitape Turing Machine. Suppose
that tape t is one of M’s k+2 tapes. In
general, determination of which action is to
be taken by the read/write head on tape t
will depend on the symbols currently being
scanned on tapes other than t and not
merely on the symbol currently being scanned
 No individual processors: no parallel
computation
 Single processor controlling multiple tape
heads
Exercise
 Develop
a TM that accepts L = { (an |
n is prime}
Time/Space trade-off
timeM(n)
spaceM(n)
 Adding tapes increases spaceM but
generally decreases timeM
Equivalence Results
Theorem A language L is accepted by
some multitape Turing machine if and only
if L is accepted by some single-tape Turing
machine.
 Theorem A language L is recognized by
some multitape Turing machine if and only
if L is recognized by some single-tape
Turing machine.

Another Equivalence Result
Theorem Similarly, a function f is computed by
some multitape Turing machine if and only if it is
computed by some single-tape Turing machine.
  always trivial
 Proof idea for : Tape alphabet of single-tape
simulator M will be large; one symbol  will
represent entire “section” through tapes of
multitape M´

Time and Space
Corollary Suppose that language L is accepted
by k-tape Turing machine M. Then L is accepted
by a single-tape Turing machine M1 such that
timeM1(n) is O([timeM(n)]2)
 Corollary Suppose that language L is accepted
by k-tape Turing machine M. Then L is accepted
by a single-tape Turing machine M´ such that
spaceM´(n) is O(spaceM(n)).

Off-line Turing Machines
Multitape machines: improved time analysis
 Singletape machines: space analysis involves
counting the number of tape squares visited
over the course of a computation
 usually visit all squares of the input
 no single-tape machine will compute in less
than O(n) space

Encoding of Turing Machines
Encoding of Turing Machines
Any Turing machine can be represented
by a natural number code
1. ASCII-style encoding
2. Euler-Gödel encoding

ASCII
a:B
q0
q1
B:R
B:1
q2
Describes language {an|n0}
 Slight changes to make it more general

s’:s
q’
q
s:R
s:s’’
q’’
<q,s’,s,q’>
<q’,s,R,q>
<q,s,s’’,q’’>
ASCII
s’:s
q’
q
s:R
s:s’’
<q,s’,s,q’>
<q’,s,R,q>
<q,s,s’’,q’’>
q’’
q: is always initial state
 Any Turing machine: finite set S of quadruples
 We want to represent S by a single symbol
string

ASCII



q: is always initial state
Any Turing machine: finite set S of quadruples
We want to represent S by a single symbol string
3*2 different ways:
q,s’,s,q’;q’,s,R,q;q,s,s’’,q’’
q,s’,s,q’;q,s,s’’,q’’;q’,s,R,q
q’,s,R,q;q,s’,s,q’;q,s,s’’,q’’
q’,s,R,q;q,s,s’’,q’’;q,s’,s,q’
q,s,s’’,q’’;q’,s,R,q;q,s’,s,q’
q,s,s’’,q’’;q,s’,s,q’;q’,s,R,q
ASCII
Member
of 
Code
,
000
q
001
s
010
R
011
L
100
;
101
‘
110
q,s’,s,q’;q’,s,R,q;q,s,s’’,q’’
q,s’,s,q’;q,s,s’’,q’’;q’,s,R,q
q’,s,R,q;q,s’,s,q’;q,s,s’’,q’’
q’,s,R,q;q,s,s’’,q’’;q,s’,s,q’
q,s,s’’,q’’;q’,s,R,q;q,s’,s,q’
q,s,s’’,q’’;q,s’,s,q’;q’,s,R,q
Each of these is a string over Turing
Machine description alphabet ,
containing the seven symbols q ‘ s L
R ,;
Represent each of these options as a
binary digit string: associate symbols
of alphabet with binary-digit strings
of e.g. length 3
ASCII
q,s’,s,q’;q’,s,R,q;q,s,s’’,q’’
Member
of 
Code
,
000
q
001
s
010
R
011
L
100
;
101
‘
110
001 000 010 110 000 010 000 001 110
101 001 110 000 010 000 011 000
001 101 001 000 010 000 010 000
010 110 110 000 001 110 110
= symbol code of machine M
Encode M as a natural number: ASCII
code of M
= natural number denoted by the 90
digit string interpreted as a binary
numeral
ASCII
Turing machines will not have unique
ASCII codes
 No natural number that encodes a Turing
machine will be the ASCII code of more
than one Turing machine
 Most natural numbers are not ASCII
codes
 If n is a code, then it is the code of a
unique machine (retrievability property).

Euler-Gödel


Based on prime decomposition
e.g. 18720 = 25.32.51.131
Associate each member of alphabet  with a natural
number
Member Code
:   {1,2,3,4,5,6,7} of 
,
1
q
2
s
3
R
4
L
5
;
6
‘
7
Euler-Gödel

Member
of 
Code
,
1
q
2
s
3
R
4
L
5
;
6
‘
7
List prime numbers for each symbol
and put it to the power of the
function call of that symbol
q,s’,s,q’;q’,s,R,q;q,s,s’’,q’’
22.31.53.77.111.133.171.192.237.296.312.3
77.411.434.471.534.591.612.676.712.73
1.793.831.893.977.1017.1031.1072.1097
.1137.
Euler-Gödel
Turing machines do not have unique
Gödel numbers
 No natural number that is the Gödel
number of a Turing Machine will be the
Gödel number of more than one Turing
Machine
 Given a natural number, there is a simple
algorithm for determining if it is the
Gödel number of a Turing Machine and
which one it is

Decoding
577565488500 is the alleged Gödel
number of a Turing Machine
 Prime decomposition

◦
◦
◦
◦
577565488500 = 22 . 144391372125
577565488500 = 22 . 31 . 48130457375
…
577565488500 = 22 . 31 . 53 . 71 . 114 . 131 . 172
Decoding
◦ 577565488500 = 22 . 31 . 53 . 71 . 114 . 131 . 172
 q,B,R,q
B:R
Memb Code
er of 
,
1
q
2
s
3
R
4
L
5
;
6
‘
7
q
Universal Turing Machines
Universal Turing machines
 So
far: machines in a peculiar sense
 Single program, single set of instructions
 Change 1 instruction  change the
machine
 Can our TM be programmed to simulate
behavior of any TM whatsoever?
Universal Turing machines
 Usual
sense of a machine: machine
(hardware) that can run several
programs (software)
 Digital Computer: Universal
Computing device that - suitably
programmed (and ignoring resource
limits) - can compute any function
that is in principle computable
Definition
Turing Machine M* is universal if, for any
Turing Machine M with input alphabet ,
when M* is started scanning the leftmost
1 in an unbroken string of n0+1 1s (n0
being the encoding of machine M)
followed by a single blank followed by
word w over , M* transforms w exactly
as machine M would transform it
UTMs as language acceptors / transducers
n0+1
...
B 1
1
...
1
1 B a
b
b
a
a B B
...
M's input w ord
M's godel number
Starting configuration for universal Turing machine M*. We suppose that n0 is
the encoding of a Turing machine that reverses words over
alphabet S ={a, b}.
M's output w ord
...
B a
a
b
b
a B B B B B
Final configuration for universal Turing machine
...
M*
Figure 2.5.1
UTMs as Function Computers
m+1
...
B 1 1
...
n+1
1 1 B 1 1
...
M's godel number
1 1 B
...
representation of argument n
Starting configuration for universal Turing machine M*. We suppose that m is
the encoding of a Turing machine M that computes unary number-theoretic
function f
representation of
value f(n)
...
B 1
...
1 1 B B B B B ...
Final configuration for universal Turing machine
M*
Figure 2.5.2
UTMs Exist
Turing (1936) proved this
 Decode/encoding of Turing Machine and
copy it to one or more worktapes
 Arguments are copied to worktape(s)
 Then the program is executed
 Proving that UTM exists different from
actually constructing it!

UTMs Exist
ENIAC (1943): programmed manually by setting flipflops and plugging wires into circuit boards
 Store these instructions in the manner of input data
 Stored-program computers (EDVAC/1946)
 Also ACE (Turing, London)
 General-purpose, executive programs: operating
systems
◦ Accept other programs as input and execute it
 hardware plasticity: ability of one general-purpose
machine architecture to mimic other, diverse machine
architectures by means of dedicated software (cf.
emulators)

EDVAC (Electronic Discrete Variable Automatic Computer)
• more internal memory than any other computing device to date
• used binary rather than decimal numbers
• 10 years after Turing!!!
History of Computing on the Internet
Charles Babbage Institute
http://www.cbi.umn.edu/photo/cbi/gallery.htm
 EDVAC site at
http://www.ifi.unizh.ch/se/people/hoyle/Lecture/edva
c.html
 Most highly recommended is the Smithsonian
Institute site (Landmarks in Digital Computing) at
http://www.nasm.edu/NASMDOCS/DSH/LDC/ldc_c
ontents.html

Nondeterministic Turing Machines
Nondeterministic Turing Machine
What is happening here?
B:1
8
B:R
7
a:B
6
a:B
0
a:B
B:R
1
b:B
2
a:B
Figure 2.6.1
B:R
3
B:1
4
5
Nondeterministic Turing Machine
L = {(ab)n | n  1}
B:1
8
B:R
7
a:B
6
a:B
0
a:B
B:R
1
b:B
2
3
a:B
Figure 2.6.1
B:R
B:1
4
5
Nondeterministic Turing
Machine
L = {(ab)n | n  1}
L’ = {an | n  1}
B:1
8
B:R
7
a:B
6
a:B
0
a:B
B:R
1
b:B
2
a:B
Figure 2.6.1
B:R
3
B:1
4
5
Nondeterministic Turing
Machine
L = {(ab)n | n  1}
L’ = {an | n  1}
B:1
8
B:R
7
a:B
6
a:B
0
a:B
B:R
1
b:B
2
B:R
3
B:1
4
5
a:B
Figure 2.6.1
Alternative execution paths
Non-deterministic language accepting Turing machine
Should accept L  L’
Language Acceptance
 Accepts
w if some computation of M
results in an accepting 1
 In general there will be “nonaccepting”
computations even in the case of an
accepted w
 M accepts L if and only if M accepts all
and only the words of L
Transition Functions
In the case of a nondeterministic M, we have
that dM is not single-valued, e.g., dM(q0, a) = (B,
q1) and dM(q0, a) = (B, q6).
 We speak of a transition mapping, instead of
transition function
 Deterministic machines of those among the
nondeterministic machines with single-valued
transitions mappings.
 Determinism = a special case of nondeterminism.

The World of Automata
U= {MM is an automaton}
nondeterministic
Turing machines
deterministic
Turing
machines
Turing-Computability
 Theorem
Let f be a numbertheoretic function. Then f is
computed by some nondeterministic
Mnd if and only if f is computed by
some deterministic Md.
Time complexity (recap)
Complexity class P: class of all languages
accepted in polynomial time by some
Turing Machine
 L = {w*| na(w) = nb(w) } is a member
of complexity class P
A language L over alphabet  is said to be
polynomial-time Turing-acceptable if there
exist both a deterministic TM M and a
polynomial p(n) such that for any w *,
we have w  L if and only if M accepts w
in O(p(|w|)) steps.

A New Complexity Class
 NP
= class of polynomial-time nondeterministically Turing-acceptable
languages
 P  NP trivially
 Every language in NP is Turingacceptable
P  NP?


Is something that is easy to check, also easy to compute?
Open problem worth $1M
http://www.claymath.org/millennium/P_vs_NP/
Suppose that you are organizing housing accommodations for a group of four hundred university
students. Space is limited and only one hundred of the students will receive places in the
dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible
students, and requested that no pair from this list appear in your final choice. This is an example
of what computer scientists call an NP-problem, since it is easy to check if a given choice of one
hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your
coworker's list also appears on the list from the Dean's office), however the task of generating
such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total
number of ways of choosing one hundred students from the four hundred applicants is greater
than the number of atoms in the known universe! Thus no future civilization could ever hope to
build a supercomputer capable of solving the problem by brute force; that is, by checking every
possible combination of 100 students. However, this apparent difficulty may only reflect the lack of
ingenuity of your programmer. In fact, one of the outstanding problems in computer science is
determining whether questions exist whose answer can be quickly checked, but which require an
impossibly long time to solve by any direct procedure. Problems like the one listed above
certainly seem to be of this kind, but so far no one has managed to prove that any of them really
are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the
help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP
(i.e., easy to check) problem independently in 1971.
P  NP?






Probable answer: yes
NP-complete problems: problems that are most likely
not to be in P
NP-hard problems: NP problems that can be reduced
in polynomial time
Traveling salesman: NP-complete problem. If this
problem turns out to be in P, P=NP
So far: no one has been able to find a polynomial time
solution to an NP-hard problem
Inherent problem of computation? Or human
intelligence problem?
Turing Machines and
Artificial Intelligence
Machine Intelligence
 Descartes Test: intelligence
= a machine’s
ability to use language:
◦ More than language recognition?
◦ Communication with humans?
◦ Weizenbaum’s ELIZA?
Turing Test


Computing Machinery and Intelligence (1950)
3 participants: 2 men (manA and manB) and 1 woman play
imitation game:
◦ Room 1: manA as the interrogator
◦ Room 2: manB + woman
◦ Communication through networked computers
◦ Goal: interrogator needs to identify male or female in
room2 through questioning (questions to player X and
player Y (predefined by manB and woman))
◦ If the interrogator correctly identifies them, interrogator
and woman win
 Woman has to help interrogator by answering like a
woman
 manB has to confuse the interrogator by answering like
a woman
Turing Test
Interrogator has to ask intelligent questions:
◦ Name a shoe manufacturer
◦ Name a football team
◦ What is your shoe size
 If the 3 participants are of the same
intelligence, the interrogator will end up
merely guessing
◦ Woman+Interrogator wins half the games
◦ manB wins half the games

Turing Test






What if the role of manB is played by a computer?
Interrogator needs to guess who is the computer and
who is the woman
Woman will help the interrogator and computer needs
to confuse him
If the number of games won by the computer is at least
as great as that of manB, we pronounce the computer
intelligent
Computer’s knowledge of the world is just as important
as its knowledge of human knowledge limitations
But: anthropocentric (cf. extraterrestrial intelligence)
Block’s critique
Given 60 minutes of Imitation Game, 88
characters, … the class of imitation game
conversations is finite
 A machine Aunt Bubbles has access to all of
these conversation and simply searches for the
most appropriate next answer
 Is this machine intelligence?
 “Intelligence of a jukebox”
 Deep Blue?

Turing Machines and
Cognitive Science
Cognition
Sensory perception, natural language
processing, reasoning, judgment, memory, …
 Computation = one sort of human cognitive
activity
 Cognitive scientists: seek plausible models of
cognitive activity
 Theory of computability can make a
contribution to cognitive science

Cognition and Turing Machines

Strong claim: Universal Turing Machines model
human cognition?
◦ Is human cognition goal-oriented?
◦ Is everything we think about computation?

Weak claim: every genuinely cognitive aspect of
the human mind can be modeled with a Turing
Machine, given the correct tape representation.
The rest is noise
Cognition and Turing Machines
 Competence
models of cognition: formal
analysis of overall input/output relations
 Performance models of cognition: includes
modeling of noise
Turing Machine modeling: only competence!
Exercise 4
 Use
Deus ex Machina to design a 3tape turing machine that accepts the
language {w * | w = wR}
Exercise 5

Use the ASCII translation table to find the
ASCII code of the Turing Machine below
s’:R
q
Exercise 6

Find the Turing Machine encoded by natural number
1,312,648,837,500
Using the Euler-Gödel scheme and the following translation
table:
Member
of 
Code
,
1
q
2
L
3
R
4
S
5
;
6
‘
7
Exercise 7 (difficult)

Use Deus Ex Machina to design a nondeterministic Turing Machine that accepts
language {ww|w*} with  = {a,b}
hint: design a machine that
nondeterministically selects a candidate
midpoint within its input word and then
proceeds to compare its front half with
its back half, one character at the time
Exercise 8
Given the following deterministic Turing Machine that
should accept all and only the words over alphabet  =
{a,b}, but fails
 Try word bbaabb

Exercise 8

Design a deterministic or nondeterministic
Turing Machine which does accept the language
L ={waaw’|w,w’  *}