!"#$%$$!&!'()'%$$*+,%*$$#%$)-%',*.#$$%"/)'0%"(!$)&!$+!$,%!(!$$)(#!12.13#4%'
"!5.%%' (5,!!' #$.% !.#!..! -),.%%',#' ,!#,,# )6-%"(#%' $)#(#'$!!7 $!# $!+,%((#'
.!')%' '##8%' "!.,%(#! ./9$%:$5").;,5&!5,.#! ,).,%&!$ ,/./(/,.%$ )&!$ +!$,%!(!$;
$)(#!1
<= <=> ?@ABCDBC EFCGBHGC IJKLMNJOBKFCDGPOQ
R!5.%S T#%"#
U V WXYZ [\ ]/.*6$// ./9$$%%""* Z^
)' +%,5+.##&#.%.$# "5%$%"$!&!7 (5$$! %# +%,5+.##&#'%'1
_
`abcdecfg
)8%$!!' %'.#'7 %$$* ,#%"# U )' +%,5+.##&#.%.$# "5%$%"$!&!S
h i
'#&%+.!!"#,)'%%.$! \j )' 6%"]]) (5),!$! ,)'%7-),! ./9$$%%""* XYZ .#(5")#
,)'%%' \ "!.,%'$!! ./9$$%%""* Z -! ]/.*6$// 6/&*,./&**' ")]]5$#"!!'7-). -!
&!#' -). .#(5")#$5 "!.,%'$! /"#]**$**' ]/.*6$//1
k.)#$%$!!' .#$$%'7%$$* ,#%"# U %# )"% +%,5+.##&#'%'S
h k
"%$%$!!'7 %$$* )"#.# U V lm\no-)""!,#' $)$!!"#.%""!
g
5+#'0#' ,)'%%""! \n1
h k
"%$%$!!' "#.*,.#7 %$$* ,)'% \n ]/.*6$/%..**' -*$$** '!56!""% !",5]%+*#.%'
./9$$%%'.*7 (!68)""#.%.$# $/6-*(%+,%#""*-!$,%$$5'!1
h
k",))' \j %8%""* ,)'.$+5)#$5 5'#&%+.!!"#,)'%1
h
T#%"%""% p &)#$!#.##' '/$ (5)8).$!! $)$!!"#'%' $5''#.$!-! /68#.$*(*""* ,)'%%$
\n -! \j ,!!&#)' %.#$$*(*""* $!&!""!1
h q
#%((!' $5"),.%' (5,!!' $*""!#.$! $)$!!"#! ,#%"%' p $5''#.$!-!,)'%$$! %#
,5#$%',!!' &)# )""! )"%(!..!r s!!$5 +#.$#+##$! ).)#$$!!7 %$$* U %# &)# )""! +%;
,5+.##&#'%'1 t
u
s%5+!5.S T#%"#
v
U V WXYZ [\ %# ]/.*68/ ./9$$%%""* w^
%# )"% +%,5+.##&#.%.$# "5%$%"$!&!1 t
<= <= QOQ N@PFK QKQPBPPQ
g
5+#'0#' ,)'%#8%' -! $!&!""#.$%' )6-%"(#%' &!.$!!&55.S
g
5+#'0#' ,)'% ;)+(!"#.(# )6-%"()#'$#,#%"#
g
5+#'0#' ,)'% )6-%"(!
g
5+#'0#' ,)'%%' ,))8# ,)'%,#%"#%.#$/.
i
'#&%+.!!"#,)'% ,)'%,#%"%' $5",,#
h
T).,! (#,* $!6!'.!
g
5+#'0#' ,)'% &)#8!!' $)$%5$$!! !.4!";)6-%"(!'! -!
,**'$*%'7 .##+$/&*$
g
5+#'0#' ,)'%#$! ,).,%&!$ +!$,%!&55.; -! +!$,%!(!$$);
(55.$5"),.%$ &*"#$$9(*.$# ,).,%(!!' (/9. !.4!";)6-%"(#!1
h
.#(%+,#,.# ]/.*6$/(#.)'0%"(!' !.4!";$5",#'$! )'S
# )"% )"%(!..! $)$!!;
"#.$! !.4!";)6-%"(!!7 -),! +!$,!#.#.#7 ]/.*6$//,9 !''%$$5 !.4!";)6-%"(!
!''%$5""! ./9$$%%""* Z 1
!"
k"%$%$!!'7 %$$* &)#$!#.##' ,#+-)#$$!! $)$!!"#'%' !.4!";5',$#)
#! U$
%&
Z S
d'(d) S *
``+' ,- 7
-),! .!! !+&)' 7-).(%+,,#-)')]!+!(%$+#'
%
%.#$$*(* ]+).%855+#]/.*6$// ./9$;
$%%""* Z7-! # (55$%'1
T#+-)#$%$!!' $*(*' ]%+5.$%%""! !.4!";]+).%855+# U.S
/
! U.$
% S
d'(d)0
#! U$
%&
Z S
d'(d) S *
``+' ,-0
1 235',$#)' U +5',)4
555
0
1 2**)6 -%"(!4
# Um
%&%
o 6
0
1
7%+,#$**' ]+).%855+#' U. )6-%"(!$%,.$#*
.
8S""! -! $!+,!.$%""!!' ]+).%855+#' U. "!.;
,%'$!! )(!""! ,5&!5,.%""!!'1
s!!8!!' +#.$#+##$!S
.
Um8.o ]/.*6$// 9 Um8.
&
.
8o V #
9 U.m8.o %# ]/.*68/1
3#.$#+##8!.$! .%5+!!7%$$* )"%$%$$5! $)$!!"#.$! ]/.*6$/(#.%'$%.$!5.)6-%"(!! U %# &)#
)""! )"%(!..!1
<= <= GOQCNNBKNGC FOBCQBK@@EKBGC AQNEGQOQNNFO@@K
h g
5+#'0#' ,)'%%' \
c',-ddb-'- `b-,bceec
(#,* $!6!'.! .%""!#'%' )(#;
'!#.55. 7-),! +##]]55 &!#' ,)'%%' \ $5''#.$!(!.$! ,#%"%.$*7%# .%' ./'$!,;
$#.%.$! +!,%'$%%.$!1 $-).,5. ]565$!!' (/9.
e-db`-,,+bcbcd, `b-,bceecbcd, 7
(#,* &##$$!! ,)'%%' $)#(#'$!!'
)
h
$!+,,!!' )$$!%' .%(!'$$#'%' )(#'!#.55. )' (#,* $!6!'.! ,),)%"(! +%,5+;
.##&#.%.$# "5%$%"$!&#! !!,,).$)' W
&
^ ,#%"#* -! ,)'%%""! \ )' )(#'!#.55. 7
-). lm \o 1
h
.#(%+,,%-* .%(!'$$#.#.$! )(#'!#.55,.#.$!S
\ 6/&*,.// $/6-*' ./9$%-)')'
\ 6/&*,.// -)',#' ./9$%-)')'
\ 6/&*,.// **+%$$9(*' ()'$! (%+,,#-)')!
\S' $5''#.$!(! ,#%"# )' .**''9""#'%' -'%1
h
). ,!68%""!
g
5+#'0#' ,)'%%""! \ -! \ )' lm \o V lm\o7'##' ,)'%#""! \
-! \ )' $*.(*""%%' .!(!$ .%(!'$$#.%$ )(#'!#.558%$1
h
k(#'!#.55. )'
,d' ,,
7 -). !''%$5.$!
g
5+#'0#' ,)'%%' ,))8#.$! &)#8!!'
!"0)+#$(#.%.$# ]**$%""*7)',) ,)'%%""! ,/./$$/ .%(!'$$#'%' )(#'!#.55.1
h
$.1-). -)5,,)
4)8%.mo V WX [lm\o ^
)' +%,5+.##&#'%'1
h _
bb,,+bd `b-,bceea'd
)&!$ )(#'!#.55. 7 -)$! %# )"% (#""**' ,)'%%""! -!
)(#'!#.55. 7-),! )' ,!#,#""! ,)'%#""!1
b'- +,ec'
T!#,,#
g
5+#'0#' ,)'%#8%' %]*$+#&#!!"#$ .%(!'$$#.%$ )(#'!#.558%$ )&!$
+!$,%!(!$$)(#!1
_
`abcdecf
k",))' (#%"#&!"$!#'%' %]*$+#&#!!"# .%(!'$$#'%' )(#'!#.55.1
h
)#8!!' )"%$$!!7 %$$* S $)#.#' .!')%'7 %$$* $/6-*' -)5,)' $5''#.$!&#""!
g
5+#'0#' ,)'%#""! %# )"% $!+,!.$%"$!&!! )(#'!#.55$$!1 $
g
*(* %# (%+,#$.% )"%%";
"#.$!+!-)#$5.$!7.#""*-). 7&)#8!!' .%5+!!&!! $)8#.$5.$! ,*/$$*%' ).)#$$!!7
%$$* )(#'!#.55. V 3
)' +!$,%!(!$)'7-! ]**$%""* %8%""%%' $*.$*7 %$$*
(/9. )(#'!#.55. )' +!$,%!(!$)'1
)
h
T).,! )' %]*$+#&#!!"#7 )' )"%(!..! -),#'
g
5+#'0#' ,)'% \7-)""! )' )(#;
'!#.55. -)""! .##. lm \o V 1
h
k",))' \
g
5+#'0#',)'%7-),! (5)8).$!!./9$$%%'* !''%$5.$!7(5)$)!
XYZ )"%&!.$! (%+,,#-)').$!7.%5+!!&!'"!#.%'
g
5+#'0#' ,)'%%' \ ,))8#' $-).
./9$% %# )"% &!!8#$$5! (5)$)!7 \ ]**$// 6/",**&**' ")]]5$#"!!'
) S
T5&! 1S
g
5+#'0#' ,)'%%' \ +!,%''% $ 3#4%' "!5.%
) 1
h
s/9$$%%""* w ,)'% \ $)#(##%'.#' ,5$%' \ ./9$$%%""* Z1 ). \ 6/&*,.// ZS'7
\ $)#(## ,5$%' ,)'% \ ./9$$%%""* w1 ). \ 6/",** ZS'7 (/9. \ 6/",**
wS' $,5&! 1
) 1
h
T)'%%' \ $5''#.$!(! ,#%"# )' .#$%'S
lm \
o V
lm\o
&
-). Z lm \o
0
&
-). Z lm \o1
h
T).,! )"%$5,.%' (5,!!' lm \o -! 7)' ,)'%%""! \ )(#'!#.55. 7
-).-! &!#' -). Z lm\o1
h
!.$!&*#$%S)(#'!#.55. )' +!$,%!&!7$.1 ,#%"%""* 4)8%.$
)
)' $)$!!"#'%' $5';
'#.$!-!,)'% \
1
h g
*""9#' .!!$!#.##' $)$!!"#'%' $5''#.$!-!,)'% ,#%"%""% p /68#.$*(*""* ,)'%%$
\ -! \ ,5&!' (5,!#.%.$#1 s%"&*.$# ,)'% \
j
)' $)$!!"#'%'7-). \
T5&! 1S
g
5+#'0#' ,)'%%' \
j
+!,%''% $ 3#4%' "!5.%
) 1
)'7-!
XYZ lm \
j o
9 XY lm\
o V 4)8%.mo
9 lm \
o
9 Z lm \o
5
h
T).,! ,#%"# p %# )"% +%,5+.##&#'%'7.%5+!! +#.$#+##$!7%"# )(#'!#.55. %# &)# )""!
+!$,%!&!1 t
<= <= @BNQ AQNEGQOQNNFOBQ FCDGPOBQ
h
!
# )"% )"%(!..! !"0)+#$(#!7-),! +!$,!#.#.#7)',) !''%$$5 %'.#((*#.%' ,%+$!"5;
&5' ]+%8#,!!$$#,!",//"#' ,!!&! &!"#8# $"))0#.%.$# $).# 7$)8#.$5&! ]+%8#,!!$;
$#,!",//"#' !,.#))(#.$!
) 1
t
h
1
1 !
"
# )"% )"%(!..! !"0)+#$(#!7-),! +!$,!#.#.#7)',) !''%$5""! ,),)'!#."5,5,%+$)#;
(#.%""!])"/')(#""! mw
&
555
&
w#o,),)'!#."5,5')""!,)6$#! $.)1-)')-! m$
&
555
&
$#o
%
#
7 -)#""! m$
&
555
&
$#o V
) 1
k
'0%"(! )' +!$,%(!$)' -)7 ,5' (55$$5-#%'
",( & V
'
$!# ])"/')(#' !.$% 8%0m o V (1 t
h
+*#8%' ,#%"#)]]#)'0%"(#%' +!$,%!&55.7 ,5' !''%$$5'! )' ,#%"#)]#$ ) -! )*
+6)(.,/' 6#%+!+,#!' $#%$/"$* $!.)"$! ,-! (%+,,#-)') Z1 !5"5,)..! - +!$;
,%!&! 7 %# +!$,%!&! 7 !#'! $)$$! 1
g
!.) ,S
k'0%"(!S)',)
Z lm )o - - -
lm )o V - -
lm )o V -
lm )o V lm )*o -
lm )o lm)*o -
lm )o lm )
*
oV -
lm )o .**'')""#'%'
lm )o lm )*o $//]]#* ,
lm )o $//]]#* ,
h
5)(r
.#(1-*.%''/.)'0%"(! Z lm )o7 ,5' ,#%"#)]]# ) )' +!-)#$$!(!$)'7
)' .##.+!$,%!(!$)' )'0%"(!1s!()#' (#%"#&!"$!#.%' ,#%"#)]#' ,5&!!(!' ,#%"%'
.**''9""#.//.-! %+**$ .5",%5(!)(#'!#.558%$1
<= <= FBNQBC MQ@KEFQ AQNEGQOQNNFOBQ FCDGPOBQ
5./ %!&%+;)'0%"(!..! $%6$*&*'* )' ,%,.#* &;$#"!#'%' .$!'8!+8#(!""#'%'
g
5+#'0#'
,)'% $-)',! )' .##. -),! !.,%"%%""! .##++/$$*&* -),) )#,%!""% $!# &!.%((!""% ]!#,!";
"!!' %# .!! ]/./*
)
7-),! !")#$$!! $)#(#'$!'.! $/6 -*""* '!56!""! -! )' ]/.*6$/%..**'
,#+-)#$$!'5$ '!56!""% (!68)""#.#((!' ()'$! (%+,,#*1
q
!,,).$)'! &)#8!!' ,*/$;
$** (#$* $!6!'.! 5'!!+#!!,,).$)!7 %.#(1 V W^7 -)"")#' $%6$*&*'* )' ,#+-)#$$!!
'!56!""% (!68)""#.#((!' ()'$! ;,#+-!#'$!1 !#6$)%6$)#.%.$#$%6$*&*'* &)# )""! "!!;
$#! (!68)""#.#((!' 6#8!.
g
5+#'0#' ,)'%7-),! .##..5)+#$$!! (!68)""#.#((!' ()'$!
!.,%"$! %''%' ]/.*6$/(#.$**'1 T5((!..!,#' )'0%"(!..! ,)'%%' $*/$// ,5#$%',#'
]/.*6$/* ")]5"$!1
g
#")-%' "5,5(**+**' & %# "!.,%$! (5,!!' ")]]5$#")-!1
.#(%+,#,.# ;$#"!#'%' 5./ %!&%+ ;,)'% &)# ,#+-)#$$!! (%+,,#* -! $)#(#!
.##+;
$/(*' !-!'1 T5&!..! ,)'%7-),! ]/.*6$// .##+$/(*' -*",%%' -! ,#+-)#$$!! (!,.#;
(!!"#.%' (%+,,#*S
1/1,L 1/1,R
</1,L 1/1,R
0 1 2 ok
</1,L
</1,R
5./%!&%+;5',$#) m&o V Ww[&;$#"!#'%' ,)'% ,#+-)#$$!! (!,.#(#..!!' w (%+,,#*
!")#$$!%..!!' $/6-*"$* '!56!"$!^ ,!.&!! $!&!$$)(!' ')]%!.$#1
.#(1 ;$#"!#.%' ,);
'%%' %''*$/.)'
7 7
(%+,,#*-! ,)'% ]/9+##]!+6!#((#""!!' 7
7 7
7
7
!.,%"%%' !-!'135',$#)$! %# ,5#$%',!!' ]/.$/ "!.,%(!!'7-)$%' $5"),.%$ )' .!!$5 ,);
,%#"%(!""!-! 55.#! %''*$/,.#* )' )8)$%$$!&#..!1
!
/
!
/
1
+;)'0%"(!' &)# (!""#'$!! 8)(#')]%"#'*7-)..! )' ,*/$%$$*&#..* **+%""#'%' ,),)%";
(! %+#"!#.#! 8)(#')'!]]5")#$!1T5',#' '!]]5"!' /"*;-! !"!+%5'!..! )' (%+,,#-)')7
%.#(1
&
&
&
1 T5.$!,#' '!]]5"!.$! &)# $!#,)! '##' ()'$! ,)]#)$! ,5#'
#,#'* 6!"5!!1
g
%6$*&*'* )' !.%$$!! '!]]5"!$ .#""* $!&!""! ]%+*,,*#'7%$$* !"!;-! /"*;
+%5'!!' (5)8).$55 .!(! (%+,,#-)')1
.#(1 %8%""#.%' ,),)%"(!' '!]]5")#""! %+*.
+!$,!#.5 )"#.#
1
"%#.%.$# )'0%"(! )' .##. .%5+!!&!S
q
''%$$5'! ,),)%"(! V
&
&
555
&
7 )',)
)"%(!..! .%""!#.$! #'8%,.#-)')! ,
&
,
&
555
&
,#7 %$$*
555
V
555
).,5. )'0%"(! &)#8!!' ]!"!5$$!! $+%85.)#8!
)
-),.#,#' $)#.%,.# $5''%$5,.# )'0%";
(!,.#7-)"")#'&)#((% ]**$%""*(/9.!",5]%+*#.%' )'0%"(!'+!$,%!&558%':+!$,%!(!$$)(558%'1
6$)'! ,5#$%',#' )'7%$$* )'0%"(!' ]!"!5$5. )' #$.%..**' +!$,%!&! )'0%"(! ,!#,#""!
./9$$%#""* $$.1 .% &)#8!!' .5)+#$$!! $)$!!"#.%""!
g
5+#'0#' ,)'%""!
) 1
8%!S
1 7%#""* )' $5'$%(!$)' ,#%"# -! $5''%$$5 ,#%"#
1 !"!5$%$!!' S,.# ]!"!5$5.5',$#)""! .#$%'7 %$$* w 9 mwo
,!#,#""! w 1
1 2/$ )' +!$,%!&!7 -). )'7 )' ).#$$!#' +!$,%!&!7 -). )'7 -! )'
+!$,%!(!$)'7-). )'7
e- ,-
]!"!5$5.5',$#) )' #$.%..**' +!$,%!&!1
bd'+
g
5+#'0#' ,)'%%' \ V m
&
&&&& &
o
+,c', `cbdd,bce,ec
$$1
e-db`)
Y
(**+#$%""**'S
Y mwo V
&
-). m
&
wo
m
&
o-)""!,#'
W
&
^
&
(**+#$$%"%(*$9'7(55$%'1
h k
.#$$!#.5',$#) )'
`cbdd,bc
'e
cbbb-'-
-). .% &)#8!!' "!.,%!
-)""!,#'
g
5+#'0#' ,)'%%""! -!
``-,bc
'e
cbbb-'-
7 -). .% &)#8!!' "!.,%!
-)""!,#' $)$!!"#.%""!
g
5+#'0#' ,)'%%""!1
h
,&#&!"%'$#.$# &)#$!#.##' (**+#$%""*7 %$$* ).#$$!#.+%,5+.##',$#) )' +%,5+;
.##&#'%'7-). .%' !+&) mwo )' (**+#$%"$/ ,!#,#""! w1
h g
!+&#$.%((% .##.
'e
cbbbc'- ,+,edec
e-db`-
bd'+
3)+(!!"#,#%"# &)#8!!'
,+,edd,,
'e
cbbbc'cdb
,#%"%%'
7
(%+,#$**'
&
-). )' )"%(!..! +%,5+.##&#'%' 5',$#)
7-)""! )' )(#'!#.55.S
w 9 mwo
&
,!#,#""! w
5
h
5)(r !"!5$5.,%$-5 &)# )""! ]#$,*,#'7 .#""* +%,5+.##&#'%' ]!"!5$5.+%"!!$#) )'
$+!'.#$##&#'%'7$.1-). -! 7 '##' 1
h
)#.#((% .##. ]!"!5$$!! S' S,.#7 S' S,.#7 S' S,.#7-'%1,5''%. &!.$!!'
$5"%% $5$$5 ,#%"#1
h
). -! )' +%,5+.##&#.%.$# '5(%+)#$5&!7 )' S,#' +%,5+.##&#.%.$#
'5(%+)#$5&!1
). -! )' +%,5+.##&#'%'7 )' S,#' +%,5+.##&#'%'1
h
T!,.# ,#%"$* -! )&!$ ,%.,%'**' #.)()+ .%$7-). '% )' (**+#$%"$/ .!(!..!
!!,,).$)..! -! +%,5+.##&#'%' ]!"!5$5.5',$#) )' #-%,$#) $.1 &)#((% .5)+#$;
$!! ]!"!5$5,.%' ,5(]!!',#' .55'$!!'1
h
3)+(!!"#.$#S
bd'+
T#%"%$
&
W
&
^ )&!$
'e
cbbbc'cdb bc``
cb,
7-). )' )"%;
(!..! +%,5+.##&#'%'#-%,$#) W
&
^ W
&
^ $$*""9#'(/9.,**'$%#.5',$#)
)' &*"$$*(*$$* +%,5+.##&#'%'
) 7-)""!
w 9 mwo
&
,!#,#""! w
5
h
3%,5+.##&#.%.$# '5(%+)#$5&!! ,#%"$* .!')$!!' -;$*/8%""#.%,.#7-). (#,* $!;
6!'.! "5),!' - ,#%"# &)#8!!' +%,5+.##&#.%.$# ]!"!5$$!! S6!'1
h
3)+(!!"#.$#S
T#%"# W
&
^ )'
d
a'++b-'- 7-).
$#
)
3
-!
$##
)
,!#,#""! 3
1
h
%.#(%+,#,.# 5'#&%+.!!"#,#%"# p )' 3
;$*/8%""#'%'1
_
`abcdecfg
#%8%$**'7 %$$* p 3
1
k
",))' V lm \o (#%"#&!"$!#'%' "5),!'
3
,#%"#1
g
*""9#' &)#8!!' ]!"!5$$!! pS65' 5',$#)""! mwo V XYw1
g
*(*
5',$#) )' .%"&*.$# +%,5+.##&#'%'7-! .#""* )' )(#'!#.55.
w V lm\o 9 mwoV XYw p
5 t
h
3#4%' "!5.%%.$! .%5+!!7%$$* ((1,!#,,#)'0%"(!$7-)#..! /+#$%$**' $%68*-)$!#'
]**$%"(#*
g
5+#'0#' ,)'%#8%' $5''#.$!(#.$! ,#%"#.$* '##8%' ,))8#%' ]%+5.$%%""!
)&!$ 3
;$*/8%""#.#*1
h
"%%'.*,#' '*/$$** )"%&!' '##'7 %$$* ,!#,,# "5)'')""#.%$ +%,5+.##&#.%.$# "5%;
$%"$!&!$7 %#;+%,5+.##&#.%$ ,#%"%$ )&!$ 3
;$*/8%""#.#*1
h g
%)+%%$$#.%.$# &)#8!!' ,5#$%',#' ).)#$$!!7 %$$* ).$ R5),!..! 3
3
+ )'
,#%"#*7-)$,! %#&*$ )"% 3
;$*/8%""#.#*1 t
h
5)(rT!#,,# 3
;$*/8%""#.%$,#%"%$ )&!$ +%,5+.##&#.%.$# #.)()+ .#!1 $$.1'% &)#;
8!!' ]!"!5$$!! $)#.#,.%%'
)
&##(%#.%""* "5%'')""!111
{a b c | i=j tai j=k } i j k
kielet äärelliset
tunnistus:
äärellinen automaatti (rajall. muisti) k k
k {a b }
{a } kontekstiton kielioppi
tunnistus:
epädeterministinen pinoautomaatti
{ww } R
kielet, joilla on yksiselitteinen rajoitettu
i i i {a b c | >=0 } tunnistus: Turingin kone, jonka tyotila lineaarisesti
Kontekstiset kielet
Kontekstittomat kielet
Säännölliset kielet =lineaariset kielet
deterministiset
pinoautomaatti kontekstittomat kielet
tunnistus: deterministinen Ratkeamattomat ongelmat
ei ole olemassa edes hyvaksyvassa tapauksessa
pysahtyvaa Turingin konetta Universaalikielen komplenmentt:i
kone−syote−parit, missa kone ei hvaksy syotetta
Rekursiivisesti numeroituvat kielet tunnistus: Turingin kone, joka pysahtyy ainakin
hyvaksyvassa tapauksessa
Universaalikieli:
kone−syote−parit, missa kone hyvaksyy syotteen
tunnistus:
universaalikone Rekursiiviset kielet
tunnistus: totaalinen Turingin kone
g
#%$)-%',*.#$$%"#-*""% %# +##$* $#%$)7 )',) )'0%"(! +!$,%!&!7 &!!' 6*' 6!"5!! (/9.
$#%$**7 ,5#',! &!!$#&! .% )'1 +6)(.,/' ,#%"#6#%+!+,#!' "5),!$ !'$!&!$ /"%#.,5&!'
.##$*7 ,5#',! &!#,%! )'0%"(! )'1 ). -),5 )'0%"(! +!$,%!! **+%""#.%""* !5$)(!!;
$#""! -! $)#'%' &!!$##
g
5+#'0#' ,)'%%'7 )' %'.#((*#'%' -)..!#' (#%"%..* 6%"])(]#
)'0%"(!1 75$$! %'$* -). %'.#((*#'%' )'0%"(! &!!$## **+%""#.%' !5$)(!!$#'7-)',!
$#")-%' "5,5(**+* )' %,.])'%'$#!!"#.%.$# .55+%(]# ,5#' $)#.%' )'0%"(!' +!$,!#.%;
&!'
g
5+#'0#' ,)'%%'
'** %'.#((*#.%' )'0%"(!' /,.#',%+$!#.55. %# )"%,!!' '##'
#$.%.$**'.%"&**1
7#$%' .#$$%' &)#.#((% &%++!$! )'0%"(#%' &!!$#&55$$! )-%,$##&#.%.$#
'$* -). &%+;
$!#.#((% +!$,!#.%&#%' )6-%"(#%' ,))8%-! $!# ].%58),))8#!"0)+#$(%-! T5(]#,!!'
'*#.$* %# ,5#$%',!!' $*/.#' ]!"-!.$! )'0%"(!' $)8%""#.$! &!!$#&55$$!7 &!#,,! ,*/;
$*''9' )6-%"()#'$#$#"!'$%#..! '##8%' !+&#)#'$# +##$$** 6/&#'1 k6-%"(! &)# ]##")$$!!
/6$%%' !.,%"%%.%%' 6/&#',#' &!#6$%"%&!' (**+*' )]%+!!$#)#$!7%#,* %.#(1 !..%("%+;
-! !.4!";,))8#' !.,%"#%' &%+$!#"5 !''! -*+,%&** $5").$!1
k
''%,.# ,!#,,# +!$,%!&!$ )'0%"(!$ &)#8!!' ,5#$%',#' %.#$$**
g
5+#'0#' ,)'%#'!r k
"#;
]! ,/.%%..* **+%""#.%""* $!# ]#')!5$)(!!$#""! +!$,%!&! )'0%"(!7 &)#((% !#'! ,)';
.$+5)#8! (/9.
g
5+#'0#' ,)'%%'7 -),! +!$,!#.%% )'0%"(!'7-! &%+$!#""!
g
5+#'0#' ,);
'%#8%' !#,!&!!$#&55,.#!1
g
*.$* .//.$*
g
5+#'0#' ,)'%%$ )&!$ 6/&#' $*+,%#$*7 ,5' 6!;
"5!((% $#%$** )'0%"(!' $)8%""#.%' !#,!&!!$#&558%'7 +##]5(!$$! .##$*7(#""* ,#%"%""*
$!# "!#$$%#.$)""! .% $5""!!' $)8%""#.558%..! $)$%5$$!(!!' $$!# -). 6!"5!((% $#%$**7
,!''!$$!!,) .#$* +/6$/* "!#',!!' $)$%5$$!(!!'
) 1
g
5+#'0#' ,)'%%' !#,!;-! $#"!&!!$#&55..!!8!!' .%' ,*/$$*(#%' !.,%"$%'-!$/9'!56!'
.)"5 -%' "5,5(**+#.$*1 s!')$!!'7 %$$* ,)'% \ 6/&*,.// ,#%"%' l !-!..! m&o7 -).
,!#,#""! w l7 (#..* [w[V &7 \ 6/&*,.// wS' mm&ooS""* !.,%"%%""!1 s!()#' ,)'%
\ 6/&*,.// ,#%"%' l $#"!..! m&o7 -). ,!#,#""! w l7 [w[ V &7 \ 6/&*,.// wS'
,*/$$*%' m m&ooS** $/9'!56!' .)"5!1
5)(r
]*8%$%+(#'#.$#'%'
g
5+#'0#' ,)'% &)# +!$,!#.$! )'0%"(!' ]#%'%((#' !#,!;
-! $#"!&!!$#(5,.#' ,5#' 8%$%+(#'#.$#'%'
g
5+#'0#' ,)'%1T*/$*''9..* %]*8%$%+(#'#.;
$#.%$ ,)'%%$ $*/$// %'.#' 8%$%+(#'#.)#8!7 (5$$! $%)+%%$$#.%..! ])68#.,%"5..! %]*;
8%$%+(#'#.$#.$%'
g
5+#'0#' ,)'%#8%' &!!$#&55.!'!"//.# &)# )""! 6/&#',#' &!"!#.%&!!1
.#(%+,#,.# &!!$#&55."5),!' (**+#$%"(* ]%+5.$55 $*6*'S"5),!' )'0%"(!$
,/%$**' +!$,!#.%(!!' ])"/')(#.%..! !-!..! %]*8%$%+(#'#.$#.%""*
g
5+#'0#' ,)'%%""!1
s%"&*.$# "5),,! $)'0%"(!$7-)$,! &)#8!!' +!$,!#.$! ])"/')(#.%..! !-!..! 8%$%+(#;
'#.$#.%""*
g
5+#'0#' ,)'%%""!
)
.#.*"$// "5),,!!' $
)
7 (5$$! %((% $#%8*7
]*$%%,9 .!(! $)#.#']*#'7 $.1 )',)
g
*(* V ;)'0%"(! )' %6,*
$*+,%#' $#%$)-%',*.#$$%"#-9#$* ,#5.!!&#.$! !&)#(#.$! )'0%"(#.$!1
T*/$*''9..* (%+,#$$*&#(]#* "5),!' )'0%"(#.$! )&!$ '.1
d
a'++bc'd
)'0%";
(!$ $
`+'d'
`+'c)
7 -)$,! )&!$ %+**'"!#.#! !+,,#$//]]#)'0%"(#! "5),!..!
1 7#,* $!6!'.! "5),!' )'0%"(#.$! &)#8!!' '*%$ ]!"!5$$!! ])"/')(#.%..!
!-!..! 2;$*/8%""#.%,.# )'0%"(!,.#1
g
)#.#' .!')%'7-). /,.#,#' 2;$*/8%""#'%' )';
0%"(! ]/.$/$$*#.##' +!$,!#.%(!!' ])"/')(#.%..! !-!..!7 '##' ,!#,,# (55$,#' "5),!'
)'0%"(!$ +!$,%!#.#&!$ ])"/')(#.%..! !-!..!1
g
*.$* .%5+!!7 %$$* 55.# )'0%"(!
&)#8!!' ).)#$$!! 2;$*/8%""#.%,.# &!+.#' 6%"]).$#S +##$$** ).)#$$!!7 %$$* .% ,55"55
"5),,!!' -! %$$* -),#' ;$*/8%""#.%,.# $5''%$$5 )'0%"(! &)#8!!' ]!"!5$$!!
.##6%'1
g
*""9#' (/9. ,!#,,# (55$ "5),!' )'0%"(!$ .%5+!!&!$ ]%+*..*1
2#(#$/.$*
`,
)'0%"(! $
,
a
`+')
,*/$%$**' .%""!#.%.$! )'0%"(!.$!7
-),! (/9. ,!$$!! ,!#,,# "5),!' )'0%"(!$7 $.1 (#,* $!6!'.! "5),!' )';
0%"(! &)#8!!' (55'$!! ])"/')(#.%..! !-!..! ,/.%#.%,.# )'0%"(!,.#1
((% ,5#$%';
,!!' $#%8*7 ,55"55,) 2;,)&! #$.% "5),,!!' $.% )' .##. '##' ,)&! )'0%"(!7
%$$* ,5,!!' %# )"% ,%,.#'/$ .#""% %]*8%$%+(#'#.$#.$*7 ])"/')(#.%..! !-!..! $)#(#&!!
g
5+#'0#' ,)'%$$!
)
1 7#,*"# -),5 )'0%"(! 6!&!#$!!' 2;,)&!,.#7 &)# 6/&#' .55+%""!
$)8%''*,9#.//8%""* !+&!$! .%' )"%&!' %,.])'%'$#!!"#.$! $!# &#%"*,#' ]!6%(]!! !#,!;
&!!$#&55."5),,!!1
!"# $ %&'&
( ()
*+
( ,
