$BBh(B 3 $B2s(B $B7W;;NLM}O@(B

$BK\F|$NFbMF(B

• 3-1. $B7W;;NLM}O@(B
• 3-2. $B7W;;NLM}O@$N
• 3-3. $B7W;;;~4V(B
• 3-4. $BA02s$N%W%m%0%i%`$N;~4V7W;;NL(B
• 3-5. $B

3-1. $B7W;;NLM}O@(B

$BLdBj$NFq$7$5!"J#;($5$r9M$($k$?$a$K!"(BTuring $B5!3#$rMxMQ$7$^$9!#(B $B$?$H$($P!":GBg5i$KFq$7$$LdBj$H$7$F$O(B Turing $B5!3#$G%W%m%0%i%`$rAH$a$J$$(B $B$h$&$JLdBj$r9M$($k$3$H$,$G$-$^$9!#(B $B$^$?!"$=$l$h$j$d$5$7$$LdBj!"$D$^$j(B Turing $B5!3#$G%W%m%0%i%`$rAH$a$kLdBj(B $B$G$"$C$F$b!"7W;;%9%F%C%W?t$,$I$l$/$i$$$+$+$k$+$GHf3S$,2DG=$K$J$j$^$9!#(B

$B%W%m%0%i%`$,AH$a$kAH$a$J$$$r5DO@$9$kM}O@$O(B$B7W;;2DG=@-M}O@(B$B$H8F(B $B$P$l$F$$$^$9!#(B $B$^$?!"%W%m%0%i%`$N7W;;%9%F%C%W?t$r5DO@$9$kM}O@$O(B$B7W;;NLM}O@(B$B$H(B $B8F$P$l$F$$$^$9!#(B

$B%W%m%0%i%`$,B8:_$9$k$3$H$r<($9$K$O

1. $B$B%W%m%0%i%`$,B8:_$9$k$3$H$r<($9(B
2. Church $B$NDs>'(B($B2>@b(B)$B$rMxMQ$9$k!#(B

Church $B$NDs>'$H$O!V?M4V$,7W;;2DG=$JLdBj$H!"%3%s%T%e!<%?(B(Turing $B5!3#(B)$B$,(B $B7W;;2DG=$G$"$kLdBj$OEy2A$G$"$k!W$H$$$&$3$H$rZL@$OIT2DG=$GHs?t3XE*$J

Church $B$NDs>'$O!"LdBj$NJ#;($5$r5DO@$9$k$N$K$J$<%3%s%T%e!<%?$r;H$&$N$+(B $B$H$$$&Ld$$$KEz$($F$$$^$9$,!"$=$l$@$1$G$O$"$j$^$;$s!#(B $B%3%s%T%e!<%?$N%W%m%0%i%`$r:n$k$3$H$K$h$k>ZL@$r9T$&:]!"?M4V$,$I$N$h$&$K(B $B2r$/$+$r@bL@$9$k$3$H$K$h$j!"%W%m%0%i%`$,:n$l$k$3$H$HEy2A$H$_$J$7!">ZL@(B $B$K$*$$$F%W%m%0%i%`$r40`z$K:n$k$3$H$r>JN,$G$-$^$9!#(B

$BNc(B3-1

$B4X?t(B f₁, f₂ $B$r7W;;$9$k(B Turing $B5!3#(B M₁, M₂ $B$,B8:_(B $B$9$k$J$i!"[email protected]?t(B f₁$B!&(Bf₂ $B$r7W;;$9$k(B Turing $B5!3#(B M₃ $B$,B8:_$9$k!#(B

$BNc(B3-2

$B4X?t(B f $B$r7W;;$9$k(B C $B$N%W%m%0%i%`$r=q$1$k$J$i!"(Bf $B$r7W;;$G$-$k(B Turing $B5!3#$r9=@.$G$-$k!#(B

$B$D$^$j!"(B Turing $B5!3#$O$"$i$f$k%3%s%T%e!<%?8@8l$HEy2A$N7W;;G=NO(B($B2DG=$+(B $BH]$+(B)$B$r;}$A$^$9!#(B

$B$J$*!"(BChurch $B$NDs>'$O7W;;$NJ#;($5$K$D$$$F$O2?$b8@$C$F$^$;$s!#(B $B$=$l$O$D$^$j?M4V$O(B Turing $B5!3#$N$h$&$K$O9M$($J$$$H$$$&$3$H$G!"9M$(J}$N(B $B8zN($O0[$J$C$FEvA3$@$+$i$G$9!#(B

$B$J$*!":#8e$O7W;;NL$N5DO@$r$9$k;~$G$5$($b(B Turing $B5!3#$ND>@\E*$J%W%m%0%i(B $B%`$NNc<($OI,MW:G>.8BEY$K$H$I$a!"F|K\8l$d(B ALGOL $B$N$h$&$J4J0W$N%W%m%0%i(B $B%_%s%08@8l$K$h$k@bL@$r$9$k$3$H$,$"$j$^$9(B($B$^$@JQ?t$N=hM}$J$I$r$I$&$9$k(B $B$+65$($F$J$$$N$G!"$=$NJU$O@bL@$7$^$9(B)$B!#(B

3-2. $B7W;;NLM}O@$N

3-3. $B7W;;;~4V(B

$B%W%m%0%i%`$N7W;;;~4V$NHf3S$r9T$&$K$"$?$C$F!"$+$1;;$N%W%m%0%i%`$r9M$($F(B $B$_$^$9!#(B

$BFs?J?t$NCM(B x $B$H(B y$B$KBP$7$F(B $B$+$1;;(B x$B!_(By $B$r9T$&$N$K

1. x $B$r(B y$B2sB-$9(B
2. $BI.;;$r9T$J$&(B

$B$^$:!"(B1 $B$NJ#;($5$G$O(B x $B$r(By$B2sB-$9$H8@$&$3$H$G!"(B y$B$KHfNc$7$?7W;;;~4V$,$+$+$k$H8@$($^$9!#(B $B0lJ}!"(B 2 $B$G$OI.;;$G$9$N$G!"(Bx $B$N7e$r0l$D$:$D$:$i$7!"9b!9(B y $B$N7e?t8DJ,$NB-$7;;$r$9$k$@$1$G$+$1;;$,7W;;$G$-$^$9!#(B logy $B$O7e?t$KHfNc$7$^$9$N$G!"7W;;;~4V$O(B log y $B$K(B $BHfNc$9$k$H8@$($^$9!#(B

$B0lJ}!"%W%m%0%i%`$N@-]$K$7$?7W;;NL$N5DO@$OLdBj$NJ#;($5$H$O4X(B $B78$J$$$3$H$K$J$j$^$9!#(B $B$7$?$,$C$F!"M-8B$N>l9g$rL5;k$9$k$h$&$J5DO@$r$7$J$1$l$P$J$j$^$;$s!#(B

$B$5$i$K8e$K<($7$^$9$,!"!V$I$s$J%W%m%0%i%`$N7W;;;~4V$G$bDj?tG\$J$i$$$/$i(B $B$G$bB.$/$G$-$k(B($B@~7A2CB.DjM}(B)$B!W$,$"$j$^$9!#(B $B$3$l$K$h$j!"=>Mh$h$j(B 5 $BG\B.$$%W%m%0%i%`$J$I$r9=@.$7$F$b!"$b$H$b$H=>Mh(B $B$N%W%m%0%i%`$r(B 5 $BG\B.$/$9$k$3$H$,$G$-$k$N$GL50UL#$K$J$j$^$9!#(B

$B$^$H$a$k$H!"%W%m%0%i%`$NB.$5$r5DO@$9$k;~!"M-8B$N>l9g$r>J$-!"Dj?tG\$N:9(B $B$OL5;k$G$-$k$h$&$K$9$kI,MW$,$"$j$^$9!#(B

$B$3$l$KBP1~$9$k?t3X$N35G0$H$7$F(B$B%*!<%@(B$B$,$"$j$^$9!#(B

f(n)=O(g(n)) $B$O!"(Bf$B$NA}$(J}$O9b!9(Bg$BDxEY$r0UL#$7!"$"$k0UL#(B f$B!e(Bg $B$N$h$&$J0UL#$r;}$A$^$9!#(B $B$3$N5-9f$N87L)$JDj5A$O

$B!V$"$k?t(B N₀ $B$H(B c>0 $B$,B8:_$7!"A4(B $B$F$N(B N₀ $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"P(B N₀, c>0) ( $B"O(B N$B!f(BN₀) [f(N)$B!e(Bcg(N)]

$B$G$Oe$K>e$2$?$h$&$JNI$$@-

$BITEy9fE*$J@- n=O(n²) $B$,@.$jN)$A$^(B $B$9!#(B $B$3$l$O(B N₀ = 1, c=1 $B$H$7$F!"(B 1 $B$h$jBg$-$$$9$Y$F$N(B N $B$G(B N $B!e(B 1 $B!_(BN² $B$,@.$jN)$D$+$i$G$9!#(B

$BM-8B$rL5;k$G$-$k(B

n² + 1 = O(n²) $B$,@.$jN)$A$^$9!#(B $B$3$l$O(B N₀ = 1, c=2 $B$H$9$l$P(B 1 $B$h$jBg$-$$$9$Y$F$N(B N $B$G(B N² + 1 $B!e(B 2 $B!_(BN² $B$,@.$jN)(B $B$D$+$i$G$9!#(B

$BDj?tG\$rL5;k$G$-$k(B

3 n² = O(n²) $B$,@.$jN)$A$^$9!#(B $B$3$l$O(B N₀ = 1, c=3 $B$H$9$l$P(B 1 $B$h$jBg$-$$$9$Y$F$N(B N $B$G(B 3 N² $B!e(B 3 $B!_(BN² $B$,@.$jN)(B $B$D$+$i$G$9!#(B

$B0lHVBg$-$$(B($B 2 n² + 3 n + 5 = O(n²) $B$,@.$jN)$A$^$9!#(B $B$3$l$O(B N₀ = 6, c=11 $B$H$9$l$P(B 6 $B$h$jBg$-$$$9$Y$F$N(B N $B$G(B 2 N² + 3 N + 5 $B!e(B 11 $B!_(B N² = 2 $B!_(B N² 3 $B!_(B N² 5 $B!_(B N² $B$,@.$jN)$D$+$i$G$9!#(B

$B$3$N5-K!$r$H$k$H!"A0=R$N$+$1;;$NNc$G$O:G=i$NNc$O(B O(y)$B2s(B $B$NB-$7;;$,I,MW$G$"$j!"O( log y ) $B2s$NB-$7;;$,(B $BI,MW$K$J$j$^$9!#(B

3-4. $BA02s$N%W%m%0%i%`$N;~4V7W;;NL(B

$BA02s=q$$$?(B Turing $B5!3#$N%W%m%0%i%`$N;~4V7W;;NL$r5DO@$7$^$7$g$&!#(B

Palindrome $B$KBP$9$k(B k-$B%F!<%W(B Turing $B5!3#(B

$BF~NO$ND9$5(B n $B$KBP$7$F!"=*C<5-9f$,$=$l$>$l$D$$$F$$$k$N$G!"F~(B $BNO%F!<%W>e$N%X%C%I$N0\F05wN%$O(B n+2 $B$K$J$j!"$=$l$K$O(B n+1 $B%9%F%C%W$+$+$j$^$9!#(B

$B$^$:!"F~NO$r%F!<%W(B 2 $B$K%3%T!<$9$k$K$O%F!<%W%X%C%I$r:8$+$i1&$K0\F0$5$;(B $B$kI,MW$,$"$k$N$G(B n+1 $B%9%F%C%W$+$+$j$^$9!#(B $Bn+1 $B%9%F%C%W$+$+$j(B $B$^$9!#$=$7$F!"%F!<%W$r>H9g$9$k$N$K$5$i$K(B n+1 $B%9%F%C%W$+$+$j(B $B$^$9!#(B $B7k6I9g7W$G(B 3n+3 $B%9%F%C%W$+$+$k$N$G!"(B O(n) $B%9%F%C%W$H8@$($^$9!#(B

Palindrome $B$KBP$9$k(B 1-$B%F!<%W(B Turing $B5!3#(B

$B:8$+$i(B k $BHVL\$N5-9f$O1&$+$i(B k $BHVL\$N5-9f$HHf3S$7(B $B$^$9!#(B $B$=$N;~$N%X%C%I$N0\F05wN%$O(B k $B$+$i(B n-k+1 $B$^$G$N1}I|$J$N$G!"(B 2(n - 2k + 1) $B$H$J$j$^$9!#(B $B$3$l$r(B k=1 $B$+$i(B n/2 $B$^$G9T$$$^$9$N$G!"(B $B7W;;;~4V$O

$B1i=,(B3-1

$B%+%C%38@8l$N;~4V7W;;NL$r5DO@$7$J$5$$!#(B

3-5. $B