Formula Sheets: Turing Machines

 Page 1


T uring Mac hine
T uring Mac hine Definition
Basic T uring Mac hine
• Definition: M = (Q,S,G,d,q
0
,q
accept
,q
reject
) , where Q is states, S is input alphab et, G is tap e
alphab et, d :Q×G?Q×G×{L,R,S} , q
0
is start state, q
accept
,q
reject
are accept/reject states.
• Language: L(M) ={w ? S
*
|q
0
w ?
*
q
accept
} .
Language Classes
• T uring Recognizable (Recursiv ely En umerable): L accepted if TM halts in q
accept
for w ?L .
• T uring Decidable (Recursiv e): TM halts on all inputs, accepting w ?L , rejecting w / ?L .
V arian ts of T uring Mac hines
Multitap e T uring Mac hine
• Definition: Multiple tap es, d :Q×G
k
?Q×G
k
×{L,R,S}
k
, where k is n um b er of tap es.
• Equiv a lence: Sim ulates single-tap e TM with O(T(n)
2
) time, where T(n) is single-tap e time.
Nondeterministic T uring Mac hine
• Definition: d :Q×G? 2
Q×G×{L,R,S}
.
• Equiv alence: Deterministic TM sim ulates NTM with time O(2
p(n)
) , where p(n) is p olynomial.
Univ ersal T uring Mac hine
• Input: Enco ding of TM M and input w , ?M,w? .
• Sim ulates M on w with O(T(n)logT(n)) o v erhead, where T(n) is M ’s running time.
Time and Space Complexit y
Time Complexit y
• Time: T(n) = n um b er of steps for input of length n .
• Deterministic: O(T(n)) steps.
• Nondeterministic: Time to explore all computation paths.
Space Complexit y
• Space: S(n) = n um b er of tap e cells used for input of length n .
• Linear Bounded A utomata (LBA): S(n) =O(n) , accepts con text-sensitiv e languages.
T uring Mac hine as T ransducer
T ransducer
• Output: W rites result on tap e, f : S
*
? G
*
.
• Computable F unction: TM computes f(w) if it halts with f(w) on tap e for input w .
Decidabilit y and Recognizabilit y
Halting Problem
• Problem: H ={?M,w?|M halts on w} .
• Undecidable: No TM decides H for all inputs.
Rice’s Theorem
1
Page 2


T uring Mac hine
T uring Mac hine Definition
Basic T uring Mac hine
• Definition: M = (Q,S,G,d,q
0
,q
accept
,q
reject
) , where Q is states, S is input alphab et, G is tap e
alphab et, d :Q×G?Q×G×{L,R,S} , q
0
is start state, q
accept
,q
reject
are accept/reject states.
• Language: L(M) ={w ? S
*
|q
0
w ?
*
q
accept
} .
Language Classes
• T uring Recognizable (Recursiv ely En umerable): L accepted if TM halts in q
accept
for w ?L .
• T uring Decidable (Recursiv e): TM halts on all inputs, accepting w ?L , rejecting w / ?L .
V arian ts of T uring Mac hines
Multitap e T uring Mac hine
• Definition: Multiple tap es, d :Q×G
k
?Q×G
k
×{L,R,S}
k
, where k is n um b er of tap es.
• Equiv a lence: Sim ulates single-tap e TM with O(T(n)
2
) time, where T(n) is single-tap e time.
Nondeterministic T uring Mac hine
• Definition: d :Q×G? 2
Q×G×{L,R,S}
.
• Equiv alence: Deterministic TM sim ulates NTM with time O(2
p(n)
) , where p(n) is p olynomial.
Univ ersal T uring Mac hine
• Input: Enco ding of TM M and input w , ?M,w? .
• Sim ulates M on w with O(T(n)logT(n)) o v erhead, where T(n) is M ’s running time.
Time and Space Complexit y
Time Complexit y
• Time: T(n) = n um b er of steps for input of length n .
• Deterministic: O(T(n)) steps.
• Nondeterministic: Time to explore all computation paths.
Space Complexit y
• Space: S(n) = n um b er of tap e cells used for input of length n .
• Linear Bounded A utomata (LBA): S(n) =O(n) , accepts con text-sensitiv e languages.
T uring Mac hine as T ransducer
T ransducer
• Output: W rites result on tap e, f : S
*
? G
*
.
• Computable F unction: TM computes f(w) if it halts with f(w) on tap e for input w .
Decidabilit y and Recognizabilit y
Halting Problem
• Problem: H ={?M,w?|M halts on w} .
• Undecidable: No TM decides H for all inputs.
Rice’s Theorem
1
• F or non-trivial prop ert y P of T uring-recognizable languages, {?M? | L(M) has prop ert y P} is unde-
cidable.
• Non-trivial: P holds for some but not all languages.
P ost Corresp ondence Problem (PCP)
• Input: Lists A ={a
1
,a
2
,...,a
n
} , B ={b
1
,b
2
,...,b
n
} of strings.
• Prob lem: Find sequence i
1
,i
2
,...,i
k
suc h that a
i1
a
i2
...a
i
k
=b
i1
b
i2
...b
i
k
.
• Undecidable.
Ch urc h’s Thesis
Ch urc h-T uring Thesi s
• An y function com putable b y an algorithm is computable b y a T uring Mac hine.
Go delizat ion
• Enco ding: TM M enco ded as n um b er ?M? for input to another TM.
• Enables Univ ersal TM and decidabilit y pro ofs.
2