$BBh(B 6 $B2s(B $B@~7A2CB.DjM}!"3,AXDjM}(B

$BK\F|$NFbMF(B

6-1. $B@~7A2CB.DjM}(B

$B@~7A2CB.DjM}$O!"0l%9%F%C%W$K=hM}$9$k>pJsNL$r2?G\$K$b$7$F7W;;B.EY$rB.$/(B $B$9$k$H$$$&$b$N$G$9!#(B $B$3$3$G$OM?$($i$l$?(B Turing $B5!3#(B M $B$r(B c/6 $BG\B.$/7W(B $B;;$9$k(B Turing $B5!3#(B M' $B$r:n$k$3$H$r9M$($^$9!#(B $B0J2

$B?7$7$/:n$k(B Turing $B5!3#(B M' $B$G$O(B M $B$N(B c $B%9%F%C%W$N7W;;$r(B 6 $B%9%F%C%W$G9T$&$h$&$K$7$^$9!#(B $B$=$N$?$a$K$^$:I,MW$J$N$O!"%F!<%W$N0l%^%9$K=q$-9~$a$k5-9f$N?t$r!"(B M $B$N(B c $B>h$H$7!"(B M $B$N%F!<%W(B c $B%^%9J,$N>pJs$r(B 1 $B%^%9$K=q$1$k$h$&$K$7$^$9!#(B $B$3$l$r0J2<(B$BBg$-$$%^%9(B$B$H8F$V$3$H$K$7$^$9!#(B

$B$5$F!"%F!<%W$r$3$N$h$&$K(B c $B%^%9J,$r(B 1 $B%^%9J,$K=q$/$h$&$K$7(B $B$F$*$$$F!"(B M $B$N(B c $B%9%F%C%W$r(B 6 $B%9%F%C%W$G%7%_%e(B $B%l!<%H$9$k$3$H$r9M$($^$9!#(B 6 $B%9%F%C%W$NFbLu$O!":G=i$N(B 4 $B%9%F%C%W$G8=:_$N%X%C%I$N0LCV$NN>NY$NBg$-(B $B$J%^%9$NFbMF$r<}=8$7$F!"c $B%9%F%C%WJ,$N(B $BBg$-$J%^%9$NFbMF$NJQ2=$r=q$-9~$_$^$9!#(B

c $B%^%9J,$N%F!<%W$NFbMF$,(B 1 $B%^%9$K=q$+$l$F$$$^$9$,!"$3$N$&$A(B $B$b$H$b$H(B M $B$N%X%C%I$,$I$3$rFI$s$G$$$?$+$O(B c $B8D$N(B $B%i%Y%k(B($B>uBV(B)$B$G5-21$7$F$*$-$^$9!#(B $B$5$F!"(Bc$B%9%F%C%W8e$K%F!<%W$O$I$N$h$&$K$J$C$F$$$k$+$r9M$($^$9!#(B $B9b!9(B c $B%^%9$7$+F0$+$J$$$N$G!"8=:_$N%X%C%I$N0LCV$+$i:81&$K(B c $B%^%9$,:GBg$N0\F05wN%$K$J$j$^$9!#(B $B$7$+$7!"(Bc $B%^%9J,$r(B 1 $B%^%9$K=q$$$?;~!"%7%_%e%l!<%H$7$F$$$k(B M $B$N%X%C%I$O:GBg$G$bNY$N(B c $B%^%9$NCf$^$G$7$+E~C#(B $B$7$^$;$s(B($B?^(B1)$B!#(B $B$^$?%X%C%I$,F0$/7PO)$r9M$($k$HN>NY$N%^%9$K(B c $B%9%F%C%WFb$KK,(B $B$l$k$3$H$O$G$-$:!"8=:_$NBg$-$J(B 1 $B%^%9$H$I$A$i$+$NNY$NBg$-$J(B 1 $B%^%9$@$1(B $B$rK,$l$k$3$H$,$G$-$^$9(B($B?^(B2)$B!#(B

$B%X%C%I$N?J$`8B3&(B
$B?^(B1
$B%X%C%I$N0\F07PO)(B
$B?^(B2

$B$=$3$G!"N>NY$NBg$-$J%^%9$NFbMF$r<}=8$7!"(B c $B%9%F%C%W%7%_%e%l!<%7%g(B $B%s$r$9$k$H!"Cf1{$N%^%9$NFbMF$H$I$A$i$+NY$NBg$-$J%^%9$NFbMF$,=q$-JQ$o$k(B $B$3$H$K$J$j$^$9!#(B

$B$H$3$m$G!"N>NY$NBg$-$J(B 3 $B%^%9J,$N%F!<%W$NFbMF$r$"$i$+$8$a$"$i$f$k>u67(B $B$rA[Dj$7$F$*$1$^$9!#$=$7$F!"$=$l$rFI$s$G(B c $B%9(B $B%F%C%W(B M $B$NFbMF$r%7%_%e%l!<%H$9$k$N$b$"$i$+$8$a$d$C$F$*$/$3(B $B$H$,$G$-$^$9!#(B $B$D$^$j!"(B(M $B$N%X%C%I$N0LCV(B)$B$H(B($BBg$-$J(B 3 $B%^%9J,$N%F!<%WFbMF(B) $B$+$i(B (M $B$r(B c $B%9%F%C%W%7%_%e%l!<%H$7$?7k2L$N>uBV!"(B $B%X%C%I0LCV!"%F!<%WFbMF(B) $B$O$"$i$+$8$a4X?t$H$7$F7W;;$G$-$k$o$1$G!"(BM' $B$O$3$l$r&D4X?t$H(B $B$7$F

$B7k6I$^$H$a$k$H(B M $B$N(B c $B%9%F%C%W$O

  1. $B8=:_$N%X%C%I0LCV$N(B c $B%^%9J,$rFI$`!#%X%C%I$r:8$X(B
  2. $B:8B&$N(B c $B%^%9J,$rFI$`!#%X%C%I$r1&$X(B
  3. $B%X%C%I$r1&$X(B
  4. $B1&B&$N(Bc $B%^%9$rFI$_!"(BM $B$N(B c $B%9%F%C(B $B%W8e$N>u67$r7W;;$9$k!#%X%C%I$r:8$X(B
  5. c $B%9%F%C%W8e$K=q$+$l$k$Y$-8=:_$N%X%C%I0LCV$NFbMF$r(B c $B%^%9J,=q$-9~$`!#(B M $B$N%7%_%e%l!<%7%g%s$N>u67$K(B $B$h$j!"%X%C%I$r1&$^$?$O:8$^$?$O$=$N$^$^$K(B
  6. c $B%9%F%C%W8e$K=q$+$l$k$Y$-NY$N%X%C%I0LCV$NFbMF$r(B c $B%^%9J,=q$-9~$`!#(B M $B$N%7%_%e%l!<%7%g%s$N>u67$K(B $B$h$j!"%X%C%I$r$b$H$KLa$9$+$^$?$O$=$N$^$^$K(B

$B$J$*!"2CB.DjM}$H8F$P$l$k$b$N$b$"$j$^$9(B ($B>ZL@$OFq$7$$$1$I!"e0UL#$,$J$$$N$G3d0&$7$^$9(B)$B!#(B $B0J2<$N$h$&$K!"$$$/$i$G$b2CB.$G$-$k(B($B$D$^$j:GE,$J%"%k%4%j%:%`$NB8:_$7$J(B $B$$(B)$B4X?t$,B8:_$9$k$H8@$&$b$N$G$9!#(B

$B2CB.DjM}(B

$Br7o$rK~$?$97W;;2DG=4X?t(B f(x) $B$,B8:_$7$^$9!#(B

$B$I$s$JA}2C4X?t(Bg(n)$B$KBP$7$F$b!"(B $BM-8B$N>l9g$r=|$-!"(B g(|x|)$B%9%F%C%W0JFb$K(B f(x) $B$r7W;;$9$k(B Turing $B5!3#$,9=@.$G$-$k!#(B

6-2. $B3,AXDjM}(B

$B$3$3$G$O7W;;;~4V$r$+$1$J$$$H2r$1$J$$LdBj$,B8:_$9$k$3$H$r<($7$^$9!#(B $B$O$8$a$K$3$l$KI,MW$JJdBj$r$^$H$a$^$9!#(B

$BJdBj(B6-1-a

$B;~4V7W;;NL(B f(n) $B$NG$0U$N(B Turing $B5!3#$N%3!<%I$r(B O(f(n)2) $B$G%7%_%e%l!<%H$9$kK|G=(B 1 $B%F!<%W(B Turing $B5!3#$,B8:_$9$k!#(B

$B$3$l$OK|G=(B Turing $B5!3#$N9=@.$G>ZL@$N35N,$r@bL@$7$^$7$?!#(B $B$5$i$K(B 2 $B%F!<%W(B Turing $B5!3#$r;H$&$H

$BJdBj(B6-1-b

$B;~4V7W;;NL(B f(n) $B$NG$0U$N(B Turing $B5!3#$N%3!<%I$r(B O(f(n)log f(n)) $B$G%7%_%e%l!<%H$9$kK|G=(B 2 $B%F!<%W(B Turing $B5!3#$,B8:_$9$k!#(B

$B$3$N>ZL@$O4pK\E*$K$O(B 1 $B%F!<%W(B Turing $B5!3#$G9=@.$7$?K|G=(B Turing $B5!(B $B3#$HF1FbMF$G$9!#(B $B%F!<%W$N;H$$J}$K%F%/%K%C%/$,I,MW$G$9!#(B $B>ZL@$K$D$$$F$O(B$B3^0fBvH~(B $B!V%3%s%T%e!<%?%5%$%(%s%9Bg3X9V:B(B 17 $B7W;;NL$NM}O@!W6aBe2J3X $B$K>y$j$^$9!#(B

$B$5$i$KF1$84X?t$r7W;;$9$k%W%m%0%i%`$,L58B$KB8:_$9$k$H$$$&

$BJdBj(B6-2-a

$B0l$D$N7W;;2DG=$J4X?t$KBP$7$F!"$=$l$r7W;;$9$k(B Turing $B5!3#$OL58B8DB8:_$9(B $B$k!#(B

$B$3$l$O%W%m%0%i%`$N@hF,$J$I$K!"2?$b$7$J$$F0:n$rKd$a9~$`$3$H$G4JC1$K<($9(B $B$3$H$,$G$-$^$9!#(B $B0lJ}!"ZL@$9$k$N$K;H$o$l$F$$$^$9!#(B

$BJdBj(B6-2-b

$B0l$D$N7W;;2DG=$J4X?t$KBP$7$F!"$=$l$r7W;;$9$k(B Turing $B5!3#$OM-8B$N>l9g$r(B $B=|$-!"$I$s$JD9$5$N%3!<%I$G$b:n$k$3$H$,$G$-$k!#(B

$B$3$NJdBj$K4X$7$F$O!";29MJ88%$G$O(B Turing $B5!3#$N%3!<%I$NF,$K(B 0 $B$rKd$a9~(B $B$`$3$H$r$f$k$9$3$H$G<($7$F$$$^$9!#(B $B$7$+$7$3$l$r5v$9$+5v$5$J$$$+$O%3%s%T%e!<%?$N%b%G%k2=$d%3!<%I2=$K0MB8$7(B $B$=$&$G$9!#(B $BC"$7!"$3$A$i$rG'$a$?J}$,NI$$7k2L$,F@$i$l$^$9!#(B

$B4X?t$N%*!<%@!<$H$7$F(B O $B$NI=5-$r;HMQ$7$F$-$^$7$?!#(B $B$,!"$3$3$G$OIU$12C$($F(B o $B$NI=5-$rDj5A$7$^$9!#(B f(n)=o(g(n)) $B$O!"(Bf$B$NA}$(J}$O(Bg$B$h$j$b??$K>/$J$$$3$H$r0UL#$7!"$"$k0UL#(B f<g $B$N$h$&$J0UL#$r;}$A$^$9!#(B $B$3$N5-9f$N87L)$JDj5A$O

$B!V$I$N$h$&$JDj?t(B c>0 $B$KBP$7$F$b(B $B$"$k?t(B N0 $B$,B8:_$7!"A4(B $B$F$N(B N0 $B$h$jBg$-$$?t(B N $B$KBP$7$F(B f(N)$B!e(Bcg(N) $B$,@.$jN)$D!W!#(B $B$J$*!"$3$l$O0l3,=R8lO@M}<0$G$O ($B"O(B c>0) ($B"P(B N0) ( $B"O(B N$B!f(BN0) [f(N)$B!e(Bcg(N)]

$B$J$*!"(B f(n)=o(g(n)) $B$H(B g(n)$B!b(B O( f(n)) $B$OF1CM$G$O$"$j$^$;$s!#(B

f ( n ) = n
g ( n ) = Lbrace {matrix left 2 2 {n^2 } {roman{ if} ~ n ~ roman{i s ~ e v e n}} {0} {roman{o . w .}}}
$B$H$9$k$H!"(B g(n)$B!b(B O( f(n)) $B$H$J$j$^$9$,!"(B f(n)$B!b(Bo(g(n)) $B$G$9!#(B

$B$3$l$i$NJdBj$rAH$_9g$o$;$k$3$H$G

6-1-a, 6-2-a $B$r;H$C$?$b$N(B

T1(n) $B$,;[email protected]=4X?t$@$H2>Dj$9$k!#(B $B$^$?(B T2(n) 2 = o(T1(n)) $B$H$9$k!#(B $B$=$N;~!"(B $B$I$s$J;~4V7W;;NL(B T2(n) $B$N(B Turing $B5!3#(B $B$K$b7W;;$G$-(B $B$J$$!";~4V7W;;NL(B T1(n) $B$G7W;;$G$-$k4X?t(Bf(x)$B$,B8:_$9$k!#(B

6-1-a, 6-2-b $B$r;H$C$?$b$N(B

T1(n) $B$,;[email protected]=4X?t$@$H2>Dj$9$k!#(B $B$^$?(B T1(n)$B!b(B O(T2(n)2) $B$H$9$k!#(B $B$=$N;~!"(B $B$I$s$J;~4V7W;;NL(B T2(n) $B$N(B Turing $B5!3#(B $B$K$b7W;;$G$-(B $B$J$$!";~4V7W;;NL(B T1(n) $B$G7W;;$G$-$k4X?t(Bf(x)$B$,B8:_$9$k!#(B

6-1-b, 6-2-a $B$r;H$C$?$b$N(B

T1(n) $B$,;[email protected]=4X?t$@$H2>Dj$9$k!#(B $B$^$?(B T2(n) log T2(n) = o(T1(n)) $B$H$9$k!#(B $B$=$N;~!"(B $B$I$s$J;~4V7W;;NL(B T2(n) $B$N(B Turing $B5!3#(B $B$K$b7W;;$G$-(B $B$J$$!";~4V7W;;NL(B T1(n) $B$G7W;;$G$-$k4X?t(Bf(x)$B$,B8:_$9$k!#(B

6-1-b, 6-2-b $B$r;H$C$?$b$N(B

T1(n) $B$,;[email protected]=4X?t$@$H2>Dj$9$k!#(B $B$^$?(B T1(n)$B!b(B O(T2(n) log T2(n)) $B$H$9$k!#(B $B$=$N;~!"(B $B$I$s$J;~4V7W;;NL(B T2(n) $B$N(B Turing $B5!3#(B $B$K$b7W;;$G$-(B $B$J$$!";~4V7W;;NL(B T1(n) $B$G7W;;$G$-$k4X?t(Bf(x)$B$,B8:_$9$k!#(B

$B$3$3$G$O(B 6-1-b, 6-2-a $B$r;HMQ$7$?$b$N$KBP$7$F>ZL@$9$k$3$H$K$7$^$9!#(B

$BCp(B: $B$3$N(B f(n) $B$,(B$B;[email protected]=(B$B$H$O!"(B $BM?$($i$l$?(B n $B$KBP$7$F!"(Bf(n) step $B$A$g(B $B$&$I$GDd;_$9$k(B Turing $B5!3#$r9=@.$G$-$k$H8@$&$3$H$G$9!#(B $BDL>o$NA}2C4X?t$O$[$\2DG=$G$9!#(B

$B>ZL@(B

$B4X?t(B f $B$OF~NO(Bx $B$KBP$7$F

  1. $BK|G=(B Turing $B5!3#$K(B x $B$H(B x $B$rF~NO$H$7$FM?$(!"(B $B%3!<%I(B x $B$N(B Turing $B5!3#$K(B x $B$rF~NO$7$?$b$N$r%7%_%e(B $B%l!<%H$7$^$9!#(B
  2. $B$3$l$r(B T1(|x|) $B%9%F%C%W%7%_%e%l!<(B $B%H$7$^$9!#(B
  3. $B$=$N7k2L(B 1 $B$r=PNO$7$?>l9g$O(B f(x) $B$NCM$r(B 0 $B$H(B $B$7$^$9!#$=$l0J30$N>l9g$O(B($B7W;;$,=*$i$:ESCf$GBG$A@Z$C$?;~$b4^$a(B) f(x) $B$NCM$r(B 1 $B$H$7$^$9!#(B

$B$3$N4X?t$r7W;;$9$k$N$K(B T1(|x|) $B%9%F%C%W$+$+$k$N$OL@$i$+$G$9!#(B $B0lJ}!"(B f(x) $B$,(B O(T2(|x|)) $B%9%F%C%W$G7W;;$G(B $B$-$J$$$3$H$r<($7$^$9!#(B f(x) $B$r(B T2(|x|) $B%9%F%C%W$G7W;;$9$k(B Turing $B5!3#(B M $B$,B8:_$9$k$H2>Dj$7$FL7=b$r(B $BF3$-$^$9!#(B $B$b$7(B M $B$,B8:_$9$k$N$G$"$l$P!"$=$N%3!<%I(B y $B$,B8:_(B $B$7$^$9!#$=$N$H$-(B g(y) $B$r9M$($^$9!#(B T1(|y|)$B!f(B T2(|y|) log T2(|y|) $B$,@.$jN)$F$P!"(B f(y) $B$N7W;;$K$*$$$F%7%_%e%l!<%H$5(B $B$l!"CM$r=P$9$3$H$K$J$j!"BP3Q@~O@K!$K$h$jL7=b$rF3$1$^$9!#(B $B$7$+$7!"M?$($i$l$?>r7o$O$3$l$rK~$?$9$[$I6/NO$G$O$J$$$?$a!"$3$N>r7o$OK~(B $B$?$5$l$kJ]>Z$,$"$j$^$;$s!#(B

$B$H$3$m$,!"JdBj(B 6-2-a $B$K$h$j!"(Bf(x) $B$,7W;;2DG=$G$"(B $B$k>l9g!"$=$l$r7W;;$9$k(B Turing $B5!3#$OL58B8DB8:_$7$^$9$N$G!"$=$N%3!<%I$r(B y1, y2, y3, ... $B$H$7$^$9!#(B T2(n) log T2(n) =o(T1(n)) $B$,@.$jN)$D;~!"$I$s$J78?t(B c $B$KBP$7$F$bM-8B$N>l9g$r=|$-$9$Y$F(B $B$N(B yi $B$K$*$$$F

T2(|yi|) log T2(|yi|) $B!e(B c T1(|yi|)

$B$7$?$,$C$F!"$3$l$rK~$?$9$h$&$J(B yi $B$K$*$$$F!"%7(B $B%_%e%l!<%7%g%s$,:G8e$^$G

6-3. $BNN0h7W;;NL(B

$B$$$^$^$G(B Turing $B5!3#$N7W;;%9%F%C%W$K4X$7$F!"$$$m$$$m5DO@$7$F$-$^$7$?$,!"(B $B$3$l$i$N$3$H$O%F!<%W$N>CHqNL$K4X$7$F$bF1MM$K$J$j$?$A$^$9!#(B $B$3$l$r(B$BNN0h7W;;NL(B$B$H8@$$$^$9!#(B

$BNN0h7W;;NL(B S(n) $B$N(B k $B%F!<%W(B Turing $B5!(B $B3#$rK|G=(B Turing $B5!3#$G%7%_%e%l!<%H$9$k;~!"(B O(S(n)) $B$NNN0h7W;;NL$G7W;;$G$-$^$9!#(B

$B@~7A2CB.DjM}$KBP$7$F!"F1MM$N>ZL@$GNN0h@aLsDjM}$,@.$jN)$A$^$9!#(B $BC"$7!"NN0h@aLsDjM}$G$O

$B3,AXDjM}$O

S1(n) $B$,[email protected]=4X?t$@$H2>Dj$9$k!#(B $B$^$?(B S1(n)$B!b(B O(S2(n)) $B$H$9$k!#(B $B$=$N;~!"(B $B$I$s$JNN0h7W;;NL(B S2(n) $B$N(B Turing $B5!3#(B $B$K$b7W;;$G$-(B $B$J$$!"NN0h7W;;NL(B S1(n) $B$G7W;;$G$-$k4X?t(Bf(x)$B$,B8:_$9$k!#(B

mail protected]=4X?t$H$O!"M?$($i$l$?4X?t(B g(n) $B$KBP$7$F!"$9$Y$F$N%Q%i%a!<%?(B n $B$KBP$7!"$A$g$&$I(B g(n) $B%^%9$@$1;HMQ$7$FDd;_$9$k(B Turing $B5!3#$r9=@.(B $B$G$-$k$3$H$r8@$$$^$9!#(B

$BC"$7$3$l$r>ZL@$9$k$K$O!"?7$7$$35G0$H!"JdBj$,I,MW$K$J$j$^$9!#(B $BMMAj(B(Configuration) $B$H$O!"(BTuring $B5!3#$N>uBV$H%F!<%W%X%C%I$N(B $B0LCV$H0l2s$G$b;HMQ$7$?%F!<%W$NFbMF$NAH$r;X$7$^$9!#(B $B%F!<%W$ND9$5$OL58B$r2>Dj$7$F$$$^$9$,!"M-8B;~4VFb$K;HMQ$9$k%F!<%W$NNL$O(B $BM-8B$G$9$N$G!"MMAj$ND9$5$OM-8B$K$J$j$^$9!#(B $B0lJ}!"&D4X?t$K$h$j!"$"$kMMAj$+$i(B 1 $B%9%F%C%W$G9T$1$kMMAj$r(B $BDj5A$9$k$3$H$,=PMh$k$^$9!#$9$k$H!"MMAj$N=89g$r9M$($?;~!"7W;;$rMMAj$+$i(B $BMMAj$X$N0\$jBX$o$j$NNs$HDj5A$9$k$3$H$,=PMh!"$^$?!"MMAj$rD:E@$H$9$k$H!"(B $B&D4X?t$GA+0\$G$-$k$H8@$&4X78$rJU$GI=$9M-8z%0%i%U$rDj5A$G$-$^$9!#(B $B:#2s!"MMAj$rMQ$$$k$3$H$G;HMQ$9$k$N$O

$BJdBj(B

Turing $B5!3#(B M $B$NNN0h$N;HMQNL$,(B S $B$GM^$($i$l$F$$(B $B$k$H$9$k!#(B $B$=$N;~!"(B 2cS $B;~4V$G(B M $B$,Dd;_$9$k$+$7$J$$$+$r7hDj$G$-$k$h$&$JDj?t(B c $B$,B8:_$9$k!#(B

$B>ZL@(B

$BNN0h$,(B S $B$GM^$($i$l$F$$$k;~!"MMAj$NI=8=$ND9$5$b(B S $B$NDj?tG\(B cS $B$GM^$($k$3$H$,=PMh$^$9!#(B $B$3$3$G!"0lHL@-$r<:$o$:!"MMAj$,(B 0, 1 $B$@$1$GI=8=$5$l$F$$$k$H2>Dj$G$-$^$9!#(B $B$9$k$H!"I=8=2DG=$JMMAjA4$F$O9b!9(B 2cS $B8D$@$1$K$J(B $B$j$^$9!#(B

Turing $B5!3#(B M $B$N7W;;$r9M$($k$H!"=i4|MMAj$+$i%9%?!<%H$7!"&D(B $B4X?t$K=>$C$F!"MMAj$r0\$jBX$o$j$J$,$i7W;;$r$7$^$9!#(B $B$5$F!"(BM $B$N7W;;$,(B 2cS+1 $B;~4VB3$$$?$H$7(B $B$^$9!#(B M $B$NMMAj$NNs(B c1, c2, c3, ..., c2cS+1 $B$r9M$($k$H!"(B c2cS+1 $B$O!";~9o(B 1 $B$+$i(B 2cS $B$N4V$K!">/$J$/$H0l2s$O=P8=$7(B $B$F$$$k$O$:$G$9!#(B $B$3$3$G!"$"$kMMAj$+$iM $B$OL58B%k!<%W$KF~$C$F$$$k$3$H$K$J$j$^$9!#(B $B=>$C$F!"(B M $B$,(B 2cS $B;~4V$G7W;;$r=*N;$7(B $B$J$$;~$O!"Dd;_$7$J$$$HH=CG$G$-$k$3$H$K$J$j$^$9!#(BQ.E.D.

6-4. $B=IBj(B

1

$BZL@$7$J$5$$!#(B

S1(n) $B$,[email protected]=4X?t$@$H2>Dj$9$k!#(B $B$^$?(B S2(n)= o(S1(n)) $B$H$9$k!#(B $B$=$N;~!"(B $B$I$s$JNN0h7W;;NL(B S2(n) $B$N(B Turing $B5!3#(B $B$K$b7W;;$G$-(B $B$J$$!"NN0h7W;;NL(B S1(n) $B$G7W;;$G$-$k4X?t(Bf(x)$B$,B8:_$9$k!#(B

2

g(n)$B!b(B O( f(n)) $B$+$D(B f(n)$B!b(Bo(g(n)) $B$H$J$k(B f(n), g(n)) $B$O$I$A$i$bC1D4Hs8:>/4X?t$H$7$F$b8+$D$+$j$^$9!#(B $B$=$N$h$&$JNc$r0l$D5s$2$J$5$$!#(B

6-5. $B

$BR2p$7$^$9!#(B

$B:dK\D>;V(B <[email protected]>
$BEl5~EE5!Bg3X9)3XIt>pJsDL?.9)3X2J(B