w8;,wH;P;DGeneva Sortsw>w8;,wH;P; DHelveticaortsw>w8;,wH;P;0DMonotype Sorts>w8;,wH;P;@DChicago Sorts>w8;,wH;P;PDSymbol Sorts>w8;,wH;P;`DMathl Sorts>w8;,wH;P;pDCourier Sorts>w8;,wH;P;DMonaco Sorts>w8;,wH;P;
@ @@``
@n?" dd@ @@``:9
!"#$%&
'
()*+, ./0123456789oB$B䯬9B$ѡP['?$9B$:_0[3\܁`9B$%mY0x9B$KJqPN Go99B$
;4d<.(_) 9`1?Pi{P@
g4dd;w`;wppHContextsensitive Languages
Linear Bounded Automata .Using Multiple Tracks
!Contextsensitive Membership Test
Turing MachinesTuring TransducersUnary Representation of Nat !Recursive Functions"#$%&'
RASP Model()*+ ,!".#/$0%Turing Recognizers & Grammars1&2'3(4)A Universal Turing Machine5*6+Decision Problems7,89.:/;0<1:Post s Correspondence Problem=2>3?4@5P@Y ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd?lKd
d`" c n?" dd@ @@``PR c`p>
>qi(
8
T2@1?
~
N@1?45~
N2@1?oo~
N@1?zf
61?J:
`Umm1 ?)H6
T Click to edit Master title style!
!@
Z4Vmm1 ?H
RClick to edit Master text styles
Second Level
Third Level
Fourth Level
Fifth Level!
S
ZVwawa1?wT
A*
TTWwawa1?54
X$22C:135 Part IIIB
s*%jQ ? 2blueboxc.ppt  Blue Boxes
ZR0(
p
01 ?** @
ZVwawa1 ?
@
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
SB
s*h ? a(@0(
B
s*h ? a(
f^
( ""N
#lT]mm1 ?)H6
XB
08c?}6
T]wawa1?so
Definition 7.1.1: for a given set of nonterminals V and set of terminals S, a production is contextsensitive if it is of the form aAb agb, where AV, a,b(VS)*, and g(VS)+; a grammar is contextsensitive if all itsproductions are. 2;
T^wawa1?+
ZDefinition 7.1.2: L S* is an efree contextsensitive language if there exists a contextsensitive grammar G so that L = L(G); L is a contextsensitive language if there exists a contextsensitive grammar G so that either L = L(G) or L = L(G) {e} [in this latter case wemay write L = Le(G)].. 2IT)J
TSwawa1?[
7
Since we have previously proven that erasing rules can be eliminated in contextfree grammars, each contextfree language is contextsensitive. 2H
0%jQ ?
P8(
DD@
8
T$Wwawa1?
pTheorem 7.1.2: each nonerasing general phrase structure grammar is equivalent to a contextsensitive grammar.(q 2
d
TWwawa1?W5
zExample 7.1.1.
A nonerasing grammar for {a2k  ke"0} (start = S).
S DS  A, DA aA, A a,
Da aaD.
As a sample derivation we have:
S DS DDS DDA DaA aaDA aaaA a4\ 2
F &tV
8
TDXwawa1? c
68In general, S * Dk A * a2k 2F
B
s*%jQ ?
`L(
TXwawa1??K
xExample 7.1.2.The construction in the proof of Theorem 7.1.1 appliedto Example 7.1.1 results in the following equivalent contextsensitive grammar
S DS  A, DA XaA, A Xa, Xa a,
DXa YXa, YXa YZ, YZ XaZ, XaZ XaXaD. 2
TYwawa1?9
Example 7.1.3.A nonerasing grammar for {ak bk ck  k e" 1} (start = A).
A aABC, aB ab, C c,
A aBC, bB bb, CB BC.
As a sample derivation we have: A aABC aaBCBC aabCBC aabBCC aabbCC aabbcC aabbcc 2
'
*8B
s*%jQ ? p(
8
H
TdYwawa1?'
Theorem 7.1.3: each phrase structure language is generated by a contextsensitive grammar augmented with contextfree erasing.( 2
t
TYwawa1?
bTheorem 7.1.4: each phrase structure language is the homomorphic image of an efree contextsensitive language.Dq 2
@#41
T$Zwawa1?Q
nDefinition 7.1.3: a homomorphism h: S* D* is efree (or nonerasing) if h(l) `" e for each lS.
Theorem 7.1.5: contextsensitive languages are closed under e free homomorphisms.` 2
0,
H
0%jQ ?  $(
TZwawa1?W
H>Definition 7.1.4: if G = (V, S, P, S) is a contextsensitivegrammar, for w1,w2(VS)* a rewriting is leftmost, w1 l w2, if w1 = xyAbg, w2 = xyabg, yAb yab P, and x,yS*; a derivation is leftmost if each of its steps is; the leftmost language of G is LL(G) = {wS*  S *l w}. 2
9>
TZwawa1?g
PTheorem 7.1.6: if G is a contextsensitive grammar, then LL(G) is contextfree.(Q 2
DH
0%jQ ? N
' $v (
$
$ #lD[mm1 ?)H6
XB
$
08c?&5&
$
T[wawa1?
Definition 7.2.1: a linear bounded automaton (LBA) A is a 6tuple A = (S, S, G, d, s0, R), where S (states) is a finite non empty set, G (tape alphabet) is a finite non empty set, S G (input alphabet) is a non empty set, s0S (start state), R S (recognizing or accepting states), and d: SG p(SG{l, r}) is the nextmove function.Z 23.(+=
$
T\wawa1?
~Definition 7.2.2: an instantaneous description (ID) for an LBA A = (S, S, G, d, s0, R ) is a sequence g1sg2 where sS and g1g2G*.Z 2 H
$0%jQ ? ("( Xj$,
(D
(
Td\wawa1?+
Definition 7.2.3: a move of an LBA A = (S, S, G, d, s0, R)is denoted by a pair of instantaneous descriptions; for IDs I1 and I2 we say I1 leads to I2 in A, I1  I2, if I1 = l1l2 & lk1slk & ln (1d"kd"n) and either
(a) <t,Y,r>d(s,lk) and I2 = l1l2 & lk1Ytlk+1 & ln , or
(b) k>1,<t,Y,l>d(s, lk), and I2 = l1l2 & tlk1Ylk+1 & ln.Q 2C 0
(
T\wawa1?OC
Definition 7.2.4: a run of an LBA is just a sequence of (zero or more) moves of the machine; that is, there is a run from ID I1 to ID I2, I1  * I2 , provided there is asequence of IDs J0, J1, & , Jk (ke"0) so that I1 = J0, I2 = Jk, and Ji  Ji+1 for 0d"i<k.. 2i(Pf
(
T$]wawa1?
\Definition 7.2.5: for an LBA the language recognized by A is L(A) = {wS* s0w  * gs for some sR and gG*}.Language L is an LBA language if an LBA exists thataccepts it.H 2#IdH
(0%jQ ? !(,O(
,D
,
T]wawa1?
Example 7.2.1.This LBA recognizes the non contextfree language {ww wS+} over S = {0,1} using tape alphabet S {X, Y}. 2
;C7
,
T]wawa1?O
us00s1Xr
s01s2Xr
s10s10r
s10s3Yl
s11s11r
s21s21r
s21s3Yl
s20s20r
s30s30l
s31s31l
s3Ys3Yl
s3Xs4Xr
s40s5Xr
s41s7Xr
s4Ys9Yr 2
,
TD^wawa1?T?
is50s50r
s51s51r
s5Ys6Yr
s6Ys6Yr
s60s3Yl
s70s70r
s71s71r
s7Ys8Yr
s8Ys8Yr
s81s3Yl
s9Ys9Yr
s90s100r
s91s101rj 2
<
,
T^wawa1?
where e.g. <s1, X, r>d(s0, 0),is written as s00s1Xrs9 is the accept stateM 2
,
Td_wawa1?'
m%nondeterminism is highlighted in red,& 2"B
,s*%jQ ? fG?0(
0
0
TtRwawa1?[
u1Example 7.2.2. (repeats the LBA of Example 7.2.1)(2 2
%
0
Td#wawa1?_
d"0: if {0} print X, right_to 1;
if {1} print X, right_to 2
1: while {0,1} right;
if {0} print Y, left_to 3
2: while {0,1} right;
if {1} print Y, left_to 3
3: while {0,1,Y} left;
if {X} right_to 4
4: if {0} print X, right_to 5;
if {1} print X, right_to 7;
if {Y} right_to 9
&" 2#
0
T#wawa1? _
*5: while {0,!} right;
if {Y} right_to 6
6: while {Y} right;
if {0} print Y, left_to 3
7: while {0,1} right;
if {Y} right_to 8
8: while {Y} right;
if {1} print Y, left_to 3
9: while {Y} right;
if {0,1} halt;
accept
& 2H
00%jQ ?
( 4+ (
4
4 #l$$mm1 ?)H6
4
T$wawa1?W
By taking G = S (S {A, B, C, & }) positions on an LBA tape can be marked without obliterating the input,p 2
Y
4
T$wawa1?B
Da b c & 2
4
T%wawa1?L
>
can become
4
Td&wawa1?{J@
Z$a b c & A & 2XB
4
01?XB
4
01?mmXB
4
01?^B
4
61?IXB
4
01?rXB
4
01?zmmXB
4
01?z
4
T&wawa1? N
q;See Example 7.2.3 in the text for a detailed illustration.< 2<H
40%jQ ? 1x8(
8N
8
T$'wawa1?
DDefinition 7.2.6: if G = (V, S, P, S) is a phrase structure grammar, and a,b(VS)*" V" (VS)*, a production a b is called invertible, and b a is its inverse.6 2
,
,R'
8
T'wawa1?
XLemma 7.2.1: if G = (V, S, P, S) is a phrase structure grammar and pP is invertible with inverse p1, then for all x,y(VS)*, x y via p if and only if y x via p1.b 2
+JX
8
T'wawa1?
z6Theorem 7.2.2: each LBA language is contextsensitive.(7 2
*H
80%jQ ? d
K < (
<
< #lD(mm1 ?H
^
<
T(wawa1?
:STEPS:= <S>; /* initialize STEPS to start (derived in 0 steps) */I:= 1; /* initialize I to first step in STEPS */
while I d" size(STEPS) do /* try each step */ begin for PDN:= 1 to p do /* with each production */ for POS:= 1 to len(STEPS[I]) do /* at each position */ begin NEXT:= rewrite(STEPS[I], P[PDN], POS); if NEXT = INPUT then return(true) else if len(NEXT) d" len(INPUT) then STEPS:= append(STEPS,NEXT) end; I:= I+1 end;return(false) 2
bZMW
<
T)wawa1?' {
Brewrite(x,p,p)  returns string x rewritten with pdn p at pos p, or x if p doesn t apply at p
append(l,x)  returns list l with x added at end, or just l if x already occurs in ln 2
*o,0XB
<
01?H
<0%jQ ?
yl@5(
@
@
Td)wawa1?'w
BTheorem 7.2.3: each contextsensitive language isan LBA language.(C 2
6u
@
T)wawa1?
Theorem 7.3.1: the contextsensitive languages are closed under the regular language operations, union, concatenation, and Kleene closure.( 2
{
@
T$*wawa1?
NTheorem 7.3.2: the contextsensitive languages are closed under intersection.(O 2
BP
@
T*wawa1?
nDefinition 7.3.1: a DGSM M = (S, S, D, d, r, s0) is efree if r(s,l) `" e for all sS and lS.
Theorem 7.3.3: the contextsensitive languages are closed under efree DGSM functions.B 2
4H
@0%jQ ? D2*D(
Dn
D
T*wawa1?
Lemma 7.3.4: for each LBA A = (SA, S, GA, dA, sA, RA), there is an LBA B = (SB, S, GB, dB, sB, RB), so that when B is started on input xS+, it terminates its run with its tape containing a representation of the number of IDs a of A so that sAx  * a in A. 2(Y>+
D
TD+wawa1?_
LTheorem 7.3.5: the contextsensitive languages are closed under complement.(M 2
@H
D0%jQ ?
l6. H
(
H
H #l+mm1 ?)H6
XB
H
08c?U]
H
T,wawa1?w'
Definition 8.1.1: a Turing acceptor T is a 7tuple T = (S, S, G, d, s0, b, R), where S (states) is a finite non empty set, G (tape alphabet) is a finite non empty set, S G (input alphabet) is a non empty set, s0S (start state), bGS (blank symbol), R S (recognizing or accepting states), and d: SG > SG{l, r} is the (partial) nextmove function. 24.'+5J
H
Td,wawa1?/
RDefinition 8.1.2: an instantaneous description (ID) for Turing machine T = (S, S, G, d, s0, b, R) is a sequence g1sg2 where sS and g1g2G*; note that blank symbols atthe right of g2 may be omitted. 2"*H
H0%jQ ? z
0L
( 
Lj
L
T,wawa1?
0Definition 8.1.3: a move of a Turing machineT = (S, S, G, d, s0, b, R) is denoted by a pair of instantaneous descriptions; for IDs I1 and I2 we say I1 leads to I2 in T, I1  I2, if either
(1) I1 = l1l2 & lk1slk & ln, and either
(a) d(s,lk) = <s',Y,r> and I2 = l1l2 & lk1Ys'lk+1 & ln, or (b) k>1, d(s,lk) = <s',Y,l> and I2 = l1l2 & s'lk1Ylk+1 & ln,
or
(2) I1 = l1l2 & lk1lk & lns, and either
(a) d(s,b) = <s',Y,r> and I2 = l1l2 & lk1lk & lnYs', or
(b) ne"1, d(s,b) = <s',Y,l> and I2 = l1l2 & lk1lk & s'lnY.T 2C
>@>H
L0%jQ ?
$n
f
@P(
P
P
T$wawa1?/
.6Definition 8.1.4: a run of Turing machine T = (S, S, G, d, s0, b, R) is just a sequence of moves of the machine; that is, there is a run from ID I1 to ID I2, I1  * I2, provided there is a sequence of IDs J0, J1, & , Jk (ke"0) so that I1 = J0, I2 = Jk, and Ji  Ji+1 for 0d"i<k. 2S(P
P
Twawa1?
$Definition 8.1.5: for a Turing acceptor T, the language accepted (or recognized) by T is L(T) = {wS*  s0w  * g1sg2 for some sR and g1g2G*}. 2
d
P
Twawa1?{
Definition 8.1.6: a language L S* is (partial) Turingrecognizable if there exists a Turing machine T so that L = L(T); if there exists such a Turing machine T that halts for each xS*, then L is called total Turingrecognizable. 2uH
P0%jQ ? a Y PT(
Tl
T
TD.wawa1?7
hExample 8.1.1: a Turing recognizer for {0n1n  ne"1}.d5 2
E
T
T.wawa1?$
transition comment
s00s1Xr mark a 0 with X and goto search for a corresponding 1
s0Ys3Yr no more 0s remain, goto check that all 1s have been matched
s10s10r move right over 0s and Ys to reach corresponding 1
s1Ys1Yr
s11s2Yl mark corresponding 1 with Y and go back for next 0
s20s20l move left over 0s and Ys to reach last (rightmost) marked 1
s2Ys2Yl
s2Xs0Xr go to repeat for next 0
s3Ys3Yr check no unmarked symbols before end of input
s3bs4bl if so, accept 2
5
;
2
2
;

,7;pH
T0%jQ ? %,`XM(
X+
X
T/wawa1?o4
U0:if {0} print X, right_to 1; /* mark a 0 with X */
if {Y} right_to 3; /* marking 0s complete */
otherwise reject /* reject if no leading 0 */1:while {0, Y} right; /* search right for 1 */
if {1} print Y, left_to 2; /* mark corresponding 1 with Y */
otherwise reject /* reject if it's missing */2:while {0, Y} left; /* rewind to last X */
if {X} right_to 0; /* loop for more 0s & 1s */
otherwise reject /* other options impossible */3:while {Y} right; /* skip over marked '1's */
if {b} accept; /* check for no extra '0's or */
otherwise reject /* '1's else, reject */6V 2X
X
T%wawa1?g+
^Example 8.1.1. (continued)( 2
H
X0%jQ ?
p\+(
ː
\
\ #lt%mm1 ?)H6
u
\
T%wawa1?
YDefinition 8.1.7: a partial function is called (partial) Turingcomputable if there exists a Turing transducer that computes exactly that (partial) function; for a total function, if there exists a Turing transducer that computes that function and halts for every element of the domain, the function is said to be total Turingcomputable. Z 2 XB
\
08c?
N
\
T4&wawa1?G
By a Turing transducer we simply mean an ordinaryTuring machine where we take notice of thecorrespondence between the initial input sequencefrom S* and the content of the tape from G* (normallyignoring rightmost blanks) when the machine halts (if ever). 2
~"IH
\0%jQ ? :
`b( ː
`
` #l&mm1 ?)H6
`
T&wawa1?o
LFor the natural numbers Nat = {0, 1, 2, & } we use the unary representation, namely, nNat 0n1{0,1}*. Since we will consider functions of several arguments,we will also need to encode tuples from Nat by concatenating the representations of the constituents, e.g., <n,m> 0n10m1{0,1}*.t' 28c
`
TT'wawa1?'
TBy the literal interpretation of Definition 8.1.7, Turing machines can compute only stringtostring functions. For functions on non string domains, Turingcomputability is understood to be with respect to a simple representation of the domain in terms of strings. 2H
`0%jQ ? D=Tdl(
d
d
T'wawa1?'
jExample: Turing transducer to map 0n1 02n1, for ne"06 2d
d
T(wawa1?/
,S = {0,1} and G = {0, 1, X, Y, b(blank)}; start state is 0.
0: if {0} print X, right_to 1; /* mark next '0' with 'X' */ if {Y} print 0, right_to 3; /* all '0's copied finish */ if {1} halt /* n=0 done */
1: while {0,Y} right; /* copy '0' as 'Y' at far right */ if {1,b} print Y, left_to 2
2: while {0,Y} left; /* rewind to 'X' */ if {X} print 0, right_to 0 /* restore 'X' to '0' and loop */
3: while {Y} print 0, right; /* replace 'Y' copies with '0' */ if {b} print 1, halt /* then halt */ 2
#6
d
Tt(wawa1?
PWith this machine for me"0 and n>m 0ms00nm1Ym  * 0mX0nm1Yms11  * 0ms2X0nm1Ym+1b  * 0m+1s00n(m+1)Ym+1b  * & 0ns0Ynb  * 0n+1s3Yn1b  * 0n0ns3b  02n1$ 2#m:H
d0%jQ ?
?phh(
h
h #l(mm1 ?)H6
XB
h
08c?v
h
T4)wawa1?_S
In this model we are concerned with functions on the natural numbers, Nat = {0, 1, 2, 3, & }. The recursive functions on Nat are developed entirely in terms of function concepts without any explicit computationalmodel. 2
h
T)wawa1?7o
Definition 8.2.1: an initial function is one of the following:
(1) the constant function, zero, defined for all xNat by zero(x) = 0,
(2) the successor function, succ, defined for all xNat by succ(x) = x+1, and
(3) for each ne"1 and 1d"kd"n, a projection function taking n arguments, pn, defined for all xiNat (1d"id"n) by pn(x1, x2, & , xn) = xk.^ 2#9bi
h
Z)wawa1?
DC
7k
h
ZT*wawa1?
t
7kH
h0%jQ ? .
0lV(
l1
l
l
T*wawa1?
FThree ways are provided to produce new functionsfrom given functions.G 2G
l
T+wawa1?E
DDefinition 8.2.2: for an mary (partial) function f, and m nary (partial) functions g1, g2, & , gm, the composition of f and gi (1d"id"m), written f <g1, g2, & , gm>, is the nary function h defined by h(x1, x2, & , xn) = f(g1(x1, & , xn), g2(x1, & , xn), & , gm(x1, & , xn)); as a partial function, the domain of h is dom(h) = {<x1, x2, & , xn>  <x1, x2, & , xn>dom(gi) for all 1d"id"m and <g1(x1, x2, & , xn), g2(x1, x2, & , xn), & , gm(x1, x2, & , xn)>dom(f) }.
Of course, if all the functions are total, then so is the composition.# 2G*=R: >2%
.&OH
l0%jQ ? C
pk
(
ph
p
Tt+wawa1?O
DDefinition 8.2.3: for nary total function f and (n+2)ary total function g, the primitive recursion of f and g is the (n+1)ary function h, written pr(f,g), defined by
h(x1, x2, & , xn, 0) = f(x1, x2, & , xn),
and for each yNath(x1, & , xn, y+1) = g(y, h(x1, & , xn, y), x1, & , xn).# 2B1
D7
p
T+wawa1?
xDefinition 8.2.4: for the (n+1)ary total function f, the minimalization of f is the nary function g defined by smallest yNat so that f(x1, x2, & , xn, y) = 0 g(x1, x2, & , xn) = undefined if no such y exists> 2+(
%b >%
p
Z4,wawa1?
5{H
p0%jQ ? Lt.(
t
t
T,wawa1?
rDefinition 8.2.5: a function is primitive recursive if:
(1) it is an initial function, or
(2) it is obtained from primitive recursive functions by either composition or primitive recursion.
Definition 8.2.6: a function is (partial) recursive if:
(1) it is an initial function, or
(2) it is obtained from recursive functions by either composition, primitive recursion, or minimalization.
2 H
t0%jQ ? B
xj
(
x
x
T,wawa1?%
0
Example 8.2.1.Using informal induction we can define the 'sum' (+)function using only initial functions as for all x,y Nat sum(x,0) = x, sum(x,y+1) = succ(sum(x,y)).Formally, this is a definition via primitive recursion,
namely, sum = pr(p1, succ p2). 2
ky,X
x
TTwawa1?
51
x@
Twawa1?0 t
73 2
l
x
T.wawa1?_
Once the sum function is defined we can use it toform other definitions. Informally the 'product' (*)function can be expressed as prod(x,0) = 0, prod(x,y+1) = sum(prod(x,y), x).Formally this is again defined via primitive recursion,prod = pr(zero, sum <p2, p3>). 2
x
Tt.wawa1? K,
73 2
x
T.wawa1? @ ,
73 2
H
x0%jQ ? 6 ^(
K

T4/wawa1?[
Theorem 8.2.1: the composition of partial (total) Turingcomputable functions yields a partial (total) Turingcomputable function.( 2
wD

T/wawa1?
Theorem 8.2.2: primitive recursion applied to total Turingcomputable functions yields a total Turingcomputable function.(} 2
p_

T/wawa1?
uTheorem, 8.2.3: the minimalization of a total Turingcomputable function is a (partial) Turingcomputable function.(v 2hT

TT0wawa1?7
XTheorem 8.2.4: each (partial) recursive function on Nat is (partial) Turingcomputable.(Y 2
LH
0%jQ ? #
K(
#l mm1 ?)H6
XB
08c?U
T4
wawa1?7
{The RandomAccess Stored Program (RASP) model is anidealized version of the familiar von Neumannstyle computer. This model will be shown equivalent to the Turing machine model. 2VS
T
wawa1?w
`*We will be concerned here only with arithmeticcomputations involving Nat = {0, 1, 2, & }. Signedarithmetic and nonintegers can be treated by thesame means we employ here, but add technical complications that cloud the conceptual clarity ofthe relationship between models. 2H
0%jQ ? $ZR( jr
T
wawa1?W
~The RASP model comprises:
" internal storage(RAM) a finite collection of addressable registers capable of storing either a machine instruction or a data value (Nat)
" arithmetic unit(acc) the accumulator where all numerical operations are performed
" instruction counter(ic) retains the address of the next instruction to be executedRo 2]D,]D
TTwawa1?7+
$Some versions of the RASP model permit program selfmodification allowing machine instructions to access and change other instructions but we do not. In our version there is separate data and instruction memory.R 2'H
0%jQ ?  =(
Twawa1??
Definition 8.3.1: a randomaccess stored program (RASP) is a finite sequence of instructions i1, i2, & , im that may refer to three different types of stored values (natural numbers):
" the accumulator, acc
" the instruction counter, ic
" memory locations m1, m2, m3, &
Each instruction is one of the following nine types:L 2d9>icY
Twawa1?~
y;LDC n LDM mk STM mkADD mk SUB mkTRF n TRB nBZF n BZB n< 2
P H
0%jQ ? @
9 0h (
0
Ttwawa1?
BDefinition 8.3.2: an instantaneous description (ID) of a RASP is a tuple of natural numbers <i, x, m1, m2,& , mN>, where i represents a value of the ic, x a value of the acc,and mk, 1d"kd"N, represent the values of the each of the memory locations mk used by the RASP.The input values for a RASP are placed in the leading memory registers, m1, m2, m3, & prior to the start of execution, and the output value, if any, is the content of the accumulator (acc) when the program halts. Additional memory registers may be used for working storage without limit, and we assume that all these registers initially contain 0. We will adopt the convention that the last instruction of a RASP is always a HALT, and to halt at any other point in the program, a branch to the last instruction is executed." 26&C]gVC%%BVH
0%jQ ? B : @(
Twawa1?GU
Definition 8.3.3: a run of a RASP i1, i2, & , im with input <x1, x2, & , xp> is a sequence (finite or infinite) of IDs a1, a2, & where a1 = <1, 0, x1, x2, & , xp, 0, 0, & > and for ie"1, if ai = <k, & >, either
" 1d"kd"m, ik = HALT (i.e., k = m) and ai is the last ID in the run, or
" 1d"k<m and ai+1 is obtained by applying the effect of ik to ai, or
" k<1 or k>m, and aj = ai for all je"i this is called an abort (representing it as an infinite but unchanging run is intended to signify there is no result). 2
/)$cbT:uH
0%jQ ? l
P (
T4
wawa1?O
LDefinition 8.3.4: an nary partial function f on the natural numbers is RASPcomputable if there is a RASP p = i1, i2, & , im so that a run of p with input <x1, x2, & , xn> is finite if and only if <x1, x2, & , xn>is in the domain of f, and in these cases p s run ends with an ID of the form <m, f(x1, x2, & , xn), & >.*F 29,+tc,(+3
T
wawa1?
^RASP execution is understood as the familiar fetch and execute cycle used in electronic computers. The ic designates an instruction whose execution causes changes to the registers (including the ic) and memory, and instruction execution continues unless a halt instruction or jam is encountered.R0 2k[f,iZfH
0%jQ ? HVN` (
0
T
wawa1?
FExample 8.3.1.RASPs for the initial recursive functions are trivial: (G 2
:3
TA?1?X$
NTwawa1?_,#
=zero(x) 2
Nwawa1?W$
Wsucc(x) 2
Nwawa1?Wf
<
Jpn* 2
Ztwawa1?
TK
7kT
T4wawa1?}
A
(x1, x2, & , xn)r
Twawa1?
;Theorem 8.3.1: each recursive function is RASPcomputable.(< 2
/B
s*%jQ ? Hd3+p (

TTwawa1?'A
JRASPprogram for f <g1, g2, & , gm>& 2
TA?1?f%UX$
TA?1?V
N
X$
Zwawa1?=,
9where
Ttwawa1?O
His a program for f 2
Twawa1? vc
9and 2
Twawa1? {
sis a program for gi* 2
TA?1?5UfX$H
0%jQ ? t( :
Twawa1?/
CTheorem 8.3.2: each RASPcomputable function is Turingcomputable.(D 2
7d
<8c?mUd
<8c?mU~d
<8c?mUF,
Twawa1?
0x10y1 & 0z1t
2B
Ttwawa1?
"LDM 0r1 STM 0s1 & 2
Tdwawa1?vS
W0k18 2d
<8c?VmUd
<8c?nmU&
TĶwawa1?gv+
W0p18 2
T$wawa1?w,;
W0q18 2
Twawa1?_D #
8& 2XB
08c?mm^XB
08c?]]^
Twawa1?'4
Kacc 2
TDwawa1?,
Kpgm 2
Twawa1?J
Jic 2
Twawa1?o$
Hm1* 2
Tdwawa1?$2
Zmn* 2
TĹwawa1?g$+
8& 2H
0%jQ ?
f^(
#l$mm1 ?)H6
XB
08c?u1
Twawa1?G
iTheorem 8.4.1: for each Turing acceptor T there exists a phrase structure grammar G so that L(T) = L(G).(j 2
]>
Twawa1?s
vTheorem 8.4.2: for each unrestricted phrase structure grammar G there exists a Turing machine T so that L(G) = L(T).(w 2
j
TDwawa1?
OCorollary 8.4.3: each contextsensitive language is total Turingrecognizable.(P 2AH
0%jQ ? ,( ( Pu
Twawa1?P
Theorem 8.4.6: the unrestricted phrase structure languages are closed under union, concatenation, Kleene closure, positive closure, substitution, and intersection.( 2
b=.
Twawa1?
fTheorem 8.4.7: if language L is total Turingrecognizable, then L is also total Turingrecognizable.(g 2
Zb
Tdwawa1?0
Theorem 8.4.8: if both language L and its complement L are (partial) Turingrecognizable languages, then L (and hence L) is total Turingrecognizable.( 2
H
<
1?
Theorem 8.4.4: each phrase structure language is the homomorphic image of the intersection of (deterministic) contextfree languages.4GH
0%jQ ? "
J(
Tļwawa1?wA
Definition 8.4.1: Let S= {0,1} and consider a Turing machine T = (S, S, G, d, s0, b, R). We can assume that R contains a single state. We define a sequence encode(T)S* that provides a complete description of T as a binary sequence as follows:
" choose a numbering of the states S as <s1, s2, & , sm> where s0 = s1 and {s2} = R, and encode each state as its number in unary,
" choose a numbering of the tape symbols G as <g1, g2, & , gn> where 0 = g1, 1 = g2, b = g3, and encode each tape symbol as its unary number,
" number the directions l as D1 and r as D2,
" encode a transition d(si,gj) = (sp,gq,Dr) as 0i10j10p10q10r,
" encode T as 111code111code211 & 11codek111 where codei (1d" i d" k) are the encoded transitions of T.^ 2/Kw
^L.P,"M.H
0%jQ ?
; (
T$wawa1?o
Definition 8.4.2: for S = {0,1) the diagonal language Ld S* is defined as follows:
" let <w1, w2, w3, & > = <e, 0, 1, 00, 01, 10, 11, 000, & > be an enumeration of S* (i.e., a 11, onto mapping a: {1, 2, 3, & } S*) in lexographical order.
" regard each positive integer i as a description of Turing recognizer Ti if encode(Ti) = the binary expansion of i; if there is no such Turing recognizer, regard i as a description of the Turing machine with no transitions,
" then Ld = {wi  wiL(Ti)}.r 2
7c5O_
Twawa1?
WTheorem 8.4.9: the diagonal language Ld is not a partial Turingrecognizable language.FX 2
1$1H
0%jQ ?
rj(
#lmm1 ?)H6
XB
08c?
h
Twawa1?K
HGU = G G^ {L, R, X, Y, Z, A, B}.% 2
TA
?1?X
$d
<8c?
Tdwawa1?'D
_Starting configuration of u( 2
TĿwawa1?'
yCStates of T are represented as uniform length binarystate numbers.D 2DB
s*%jQ ? j\LD(
T$wawa1?
An outline of the operation of the Universal Turing machine is:
" locate a match for the current state/symbol within the description of T
" copy the portion in the description immediately following the match into the current state/symbol segment to update it
" move the current (overprint) symbol to the marked position of T s tape, access and mark the next position of T s tape and move that symbol to the current position
" repeat these steps until no match is found 2H
0%jQ ?
tF(
#lmm1 ?)H6
XB
08c?%
Twawa1?/
A decision problem is a family of yes/no questions p together with a decision mapping d: p {yes,no}.j 2!%
TDwawa1?O
XMembership problem for Turing machines: given a Turing machine T, and an input wS* for T, is wL(T)?pg 2>
Twawa1?'
^(The membership problem is a 2 parameter decisionsince to identify an instance of the problem, there aretwo independent arguments to be supplied. 2H
0%jQ ? w46(
Twawa1??
NDDefinition 9.2.1: a decision problem (p,d) is decidable (or solvable) if there is straightforward encoding e(p) of the problem instances into sequences in some alphabet S so that d: e(p) {yes,no} is a total Turingcomputable function; otherwise (p,d) is undecidable (or unsolvable).# 2 *< <
$
Ttwawa1?/
4Since the outcomes are binary, a decision problem (p,d) can also be regarded as a language recognition problem L(p) = {we(p) w=e(p) and d(p)=yes} S*.P 24;H
0%jQ ? :,b(
Twawa1?
pTheorem 9.2.1: the membership problem for Turing machines is undecidable, or alternatively, the language L(u) = {encode(T) w T is T.M. and wL(T)} is not total Turingrecognizable.` 2
`!)=p
T4wawa1?7
lCorollary 9.2.2: Ld is (partial) Turingrecognizable.b7 2##H
0%jQ ? 6 ^(
1
Twawa1?g
GTheorem 9.2.3: the halting problem is undecidable for Turing machines.(H 2
;%
Twawa1?
tThe Halting Problem for Turing machines: given a Turing machine T, and an input wS* for T, does T halt when started on w?b 2?'
TTwawa
!"#$%&'()*+,./1234567:;<=>?@1?G
FThe algorithm test for Turing machines: given a Turing machine T, does T halt for every input wS*?be 2N
Twawa1?c
1Theorem 9.2.4: the algorithm test is undecidable.(2 2
%$H
0%jQ ? L0B(
Twawa1?
VThe emptiness problem for Turing machines (also raised for grammars, etc.): given a Turing machine T, is L(T) = ?Ru 2]
Ttwawa1?
The language version of this problem is Le = {encode(T)  L(T) = }, where Turing machine T is encoded by previously discussed means.T 2,F
Twawa1??
^The nonemptiness problem for Turing machines (also raised for grammars, etc.): given a Turing machine T, is L(T) `" ?Ry 2].
T4wawa1?c
The language version of this problem is Lne = {encode(T)  L(T) `" }, where Turing machine T is encoded by previously discussed means.T 2,F'_H
0%jQ ? XP@(
<
Twawa1?{
4Theorem 9.2.5: Lne is (partial) Turingrecognizable.F5 2
##i
Twawa1?
aTheorem 9.2.6: Le is not total Turingrecognizable (i.e., the emptiness problem is undecidable).Fb 2
QS
TTwawa1?
JCorollary 9.2.7: Lne is not total Turingrecognizable (i.e., the nonemptiness problem is undecidable), and Le is not (partial) Turingrecognizable.d 2[',F1%
<
1?P"
UTheorem 9.2.9: it is undecidable for Turing machine Twhether or not L(T) is regular.&V
I5H
0%jQ ? 3
,Pa(
#lmm1 ?)H6
XB
08c?5
Twawa1?
bDefinition 9.3.1: Post s Correspondence Problem (PCP) is the decision problem: given a finite alphabet S and two ktuples (ke"1) of sequences A = <a1, a2, & , ak> and B = <b1, b2, & , bk> where ai,biS*, do there exist positive integers i1, i2, & , im (me"1, 1d"ijd"k), called a solution, so that ai1ai2 & aim = bi1bi2 & bim? I 2:,
%
v$2 8
TA?1?& X$
Twawa1?o3
C
Example 9.3.1 2`
T4wawa1?'
ja1 a2 a3 & = 10101101 & and
b1 b2 b3 & = 101011011 & V6 2P PB
s*%jQ ? <8`d( m
+
6
Twawa1?
LTheorem 9.3.1: PCP is undecidable if the alphabet has at least two letters.(M 2
@,
Twawa1?
j4A Turing machine description can be used to create aPCP whose matching establishes a direct correspondence between a PCP solution and a terminating run of the Turing machine. Hence analgorithm to decide the existence of a PCP solutionwould also decide Turing machine halting and istherefore impossible.5 25H
0%jQ ? ,4,p(
TTwawa1?
jTheorem 9.3.2: it is undecidable for homomorphisms h1,h2: S* D* whether or not there exists xS+ so that h1(x) = h2(x).$ 2
(,JJ
Twawa1?W
`Theorem 9.3.3: it is undecidable whether or not an arbitrary contextfree grammar is ambiguous.(a 2
TAd
Twawa1?
zCorollary 9.3.4: it is undecidable if the intersection of the languages of two arbitrary contextfree grammars is empty.({ 2lY
Ttwawa1?
TCorollary 9.3.5: it is undecidable for an arbitrary contextsensitive grammar G whether or not L(G) = .Dj 2XHH
0%jQ ? 0`X(
Twawa1?
@Theorem 9.3.6: it is undecidable for an arbitrary contextfree grammar G if L(G) = S*.TX 2
G8
T4wawa1?
NpCorollary 9.3.7: it is undecidable for arbitrary contextfree grammars G1 and G2 whether or not L(G1) = L(G2).q 2:Oz
Twawa1?
Theorem 9.4.1: it is undecidable for DGSMs M1 and M2 whether or not there exists xS+ so that M1(x) = M2(x).n 2
,DH
0%jQ ? yq (
Twawa1?
4Theorem 9.4.2: it is undecidable for 2DFAs C1 and C2 whether or not L(C1) L(C2) = (i.e., the empty intersection problem is undecidable for 2DFAs). 2
DPV
TTwawa1?
Theorem 9.4.3: for #S, it is undecidable whether or not L(C) = S*" {#} S*" {#} for 2NFA C with alphabet S {#}.u 2
+ >%7
Twawa1?'
;Corollary 9.4.4: the equivalence of 2NFAs is undecidable.(< 2,&
H
0%jQ ? xXO\E?s.(PV4[@Ik.e^<&ϼ3M&&DMIL7s.ֲpn~qs̹wʕ>#qrQ*,sHs)˲lk+8:ԑsRۼoHŤG
#~3#P)g(Lƿ%gTMi')Jc:.ӕWArO[/)o& ">gzZ+܃t/}H#EbH CzΛxS(_Y8N!~8
Κո:yѲslt?z*/_?+Xl[jk\J_H,W?L%%f%n'e9"[F%,)tAWK'Aj%Z(t>F0MЁt4#'BEeøo>Y9Llk1x߉DcsDb0p_ùɲv1gx*Y5`dwVΑmtNmÜa=7L0䄃ؼv$s֩Y^pXpy:[/j<3 Apg