Automat´ ak mint elfogad´ ok (akceptorok) Ha egy inici´ alis Moore-automat´ aban a kimen˝ ojelek halmaza csup´ an k´ etelem˝ u: {elfogadom, nem fogadom el}, ´ es az utols´ o kimen˝ ojel d¨ onti el azt a k´ erd´ est, hogy elfogadhat´ o-e az input sz´ o, akkor ez az automata nyelvek defini´ al´ as´ ara v´ alik alkalmass´ a. A µ f¨ uggv´ enyt ebben az esetben az elfogadom elem ˝ osk´ epe is defini´ alhatja. Ez jelenik meg a k¨ ovetkez˝ o defin´ıci´ oban:
1
Defin´ıci´ o Rabin–Scott-automata Az A = hA, a0, X, δ, AF i rendezett ¨ ot¨ ost Rabin–Scott-automat´ anak nevezz¨ uk, ahol A az ´ allapotok nem ¨ ures halmaza, a0 ∈ A a kezd˝ o ´ allapot, X a bemen˝ ojelek nem ¨ ures halmaza (´ ab´ ec´ eje), δ :A×X →A az ´ atmeneti f¨ uggv´ eny, AF ⊆ A a v´ eg´ allapotok halmaza. V´ eg´ allapot: egy elfogadhat´ o sz´ o hat´ as´ ara az automata egy ilyen ´ allapotba ker¨ ul. 2
Defin´ıci´ o Azt mondjuk, hogy az A = hA, a0, X, δ, AF i Rabin–Scott-automata elfogadja a P ∈ X ∗ sz´ ot, ha az automata a P bemen˝ o sz´ o hat´ as´ ara a kezd˝ o ´ allapotb´ ol egy v´ eg´ allapotba jut, azaz ha δ(a0, P ) ∈ AF . Egy A automata ´ altal elfogadott szavak nyelv´ et az automata ´ altal felismert nyelvnek nevezz¨ uk, ´ es LA-val jel¨ olj¨ uk, azaz LA {P | P ∈ X ∗ ´ es δ(a0, P ) ∈ AF }.
3
Defin´ıci´ o Nemdeterminisztikus Rabin–Scott-automata Az A = hA, A0, X, δ, AF i rendezett ¨ ot¨ ost nemdeterminisztikus Rabin–Scott-automat´ anak nevezz¨ uk, ahol A az ´ allapotok nem ¨ ures halmaza, A0 ⊆ A a kezd˝ o´ allapotok halmaza, X a bemen˝ ojelek nem ¨ ures halmaza (´ ab´ ec´ eje), δ : A × X → 2A a nemdeterminisztikus ´ atmeneti f¨ uggv´ eny, AF ⊆ A a v´ eg´ allapotok halmaza. V´ eg´ allapot: egy elfogadhat´ o sz´ o hat´ as´ ara az automata tud ´ ugy m˝ uk¨ odni, hogy egy ilyen ´ allapotba ker¨ ul. Ha |A0| = 1 ´ es |δ(a, x)| = 1 minden a ∈ A ´ es x ∈ X eset´ en, akkor az automata megfeleltethet˝ o egy determinisztikus automat´ anak. 4
Az automata az a ´ allapotb´ ol az x jel hat´ as´ ara a δ(a, x) ´ allapothalmaz ´ allapotaiba mehet ´ at. A δ f¨ uggv´ eny kiterjeszt´ ese A × X-r˝ ol 2A × X-re: δ˜(B, x) =
[
δ(a, x)
B ∈ A, x ∈ X.
a∈B
Az automata a B ´ allapothalmaz ´ allapotaib´ ol az x jel hat´ as´ ara a δ˜(a, x) ´ allapothalmaz ´ allapotaiba mehet ´ at. A δ˜ f¨ uggv´ eny kiterjeszt´ ese 2A × X-r˝ ol 2A × X ∗-ra: δˆ(B, e) = B,
δˆ(B, P x) = δ˜(δˆ(B, P ), x),
B ⊆ A, x ∈ X, P ∈ X ∗.
Az automata a B ´ allapothalmaz ´ allapotaib´ ol a P sz´ o hat´ as´ ara a δˆ(B, P ) ´ allapothalmaz ´ allapotaiba mehet ´ at. 5
Defin´ıci´ o Azt mondjuk, hogy az A = hA, A0, X, δ, AF i nemdeterminisztikus Rabin–Scott-automata elfogadja a P ∈ X ∗ sz´ ot, ha az automata tud ´ ugy m˝ uk¨ odni, hogy a P bemen˝ o sz´ o hat´ as´ ara a kezd˝ o´ allapotok valamelyik´ eb˝ ol egy v´ eg´ allapotba jut, azaz ha δˆ(A0, P ) ∩ AF 6= ∅. Egy A automata ´ altal elfogadott szavak nyelv´ et az automata ´ altal felismert nyelvnek nevezz¨ uk, ´ es LA-val jel¨ olj¨ uk, azaz LA {P | P ∈ X ∗ ´ es δˆ(A0, P ) ∩ AF 6= ∅}.
6
Defin´ıci´ o K´ et Rabin–Scott-autmat´ at ekvivalensnek nevezz¨ uk, ha az ´ altaluk elfogadott nyelvek megegyeznek. T´ etel Tetsz˝ oleges nemdeterminisztikus Rabin–Scott-automat´ ahoz van vele ekvivalens determinisztikus Rabin–Scott-automata Bizony´ıt´ as Ha a nemdeterminisztikus automata A = hA, A0, X, δ, AF i, akkor az A0 = h2A, A0, X, δ˜, {B | B ⊆ A, B ∩ AF 6= ∅}i automata egy determinisztikus Rabin–Scott-automata, tov´ abb´ a LA = LA0 .
7
Defin´ıci´ o A G = hVN , VT , S, Hi nyelvtant jobbregul´ arisnak nevezz¨ uk, ha szab´ alyai A → λ, A → a, A → aB alak´ uak, ahol a ∈ VT , A, B ∈ VN . A jobbregul´ aris nyelvtan a jobbline´ aris nyelvtan norm´ alalakj´ anak tekinthet˝ o. T´ etel Tetsz˝ oleges jobbline´ aris nyelvtanhoz van vele ekvivalens jobbregul´ aris nyelvtan. P´ elda Legyen H = {S → a, S → aA, A → bB, A → aS, B → bB, B → bA, B → b}. Ekkor S ⇒ aA ⇒ abB ⇒ abbB ⇒ abbbA ⇒ abbbaS ⇒ abbbaa. 8
Anal´ ogi´ at keresve a jobbregul´ aris nyelvtanok ´ es a Rabin–Scott-automat´ ak k¨ oz¨ ott a p´ eld´ ab´ ol leolvashat´ o, hogy a nemtermin´ alisok j´ atssz´ ak az ´ allapotok szerep´ et. T´ etel Tetsz˝ oleges G regul´ aris nyelvtanhoz megadhat´ o olyan A nemdeterminisztikus, v´ eges ´ allapot´ u Rabin–Scott-automata, amely a nyelvtan ´ altal gener´ alt nyelvet fogadja el. Bizony´ıt´ as Legyen G = hVN , VT , S, Hi egy jobbregul´ aris nyelvtan. Legyen A = VN ∪ {⊥}, A0 = {S}, X = VT , AF = {⊥} ∪ {B | B → λ} ´ es δ(B, x) = {C | C ∈ VN ´ es B → xC, vagy C = ⊥ ´ es B → x}. Bizony´ıthat´ o, hogy S ⇒∗ P B (P ∈ VT∗, B ∈ VN ) pontosan akkor teljes¨ ul, ha B ∈ δˆ(S, P ), tov´ abb´ a S ⇒∗ P (P ∈ VT∗) pontosan akkor teljes¨ ul, ha ⊥ ∈ δˆ(S, P ), vagy van olyan B ∈ VN , hogy B ∈ δˆ(S, P ) ´ es B → λ. 9
T´ etel Tetsz˝ oleges v´ eges ´ allapot´ u Rabin–Scott-automat´ ahoz van olyan G regul´ aris nyelvtan, amelyek ´ altal elfogadott, illetve gener´ alt nyelvek megegyeznek. Bizony´ıt´ as Legyen A = hA, a0, X, δ, AF i egy tetsz˝ oleges, v´ eges ´ allapot´ u, Rabin–Scott-automata. Legyen VN = A, VT = X, S = a0 H = {a → xb | δ(a, x) = b} ∪ {a → λ | a ∈ AF }. Bizony´ıthat´ o, hogy δ(a, P ) = b (a, b ∈ A, P ∈ X ∗) pontosan akkor teljes¨ ul, ha a ⇒∗ P b, tov´ abb´ a δ(a, P ) = b ∈ AF pontosan akkor, ha a ⇒∗ P . Ezeket a = a0ra alkalmazva: P ∈ LA
⇔
δ(a0, P ) ∈ AF
⇔
S = a0 ⇒ ∗ P
⇔
P ∈ L(G).
10
K¨ ornyezetf¨ uggetlen Nyelvtanok ´ es (nemdeterminisztikus) veremautomat´ ak A (nemdeterminisztikus) v´ eges Rabin–Scott-automat´ ak kib˝ ov´ıthet˝ ok egy veremmel, ez´ altal az ’´ allapotok’ halmaza v´ egtelenn´ e tehet˝ o. A veremautomata m˝ uk¨ od´ ese: Az automata egy-egy l´ ep´ ese sor´ an beolvas egy jelet, ´ es a verem teteje, a bels˝ o ´ allapot ´ es a beolvasott jel f¨ uggv´ eny´ eben ´ allapotot v´ alt ´ es a verem teteje hely´ ebe egy ´ uj sz´ ot tesz. Az input jel beolvas´ asa esetleg elmaradhat, ekkor az ´ allapotv´ alt´ as ´ es a veremtartalom-csere csak a verem tetej´ enek ´ es az ´ allapotnak a f¨ uggv´ enye. A veremautomata l´ ep´ esekre bontott m˝ uk¨ od´ es´ enek f´ azisait konfigur´ aci´ o nak nevezz¨ uk. A konfigur´ aci´ o a verem tartalm´ ab´ ol, a bels˝ o´ allapotb´ ol ´ es az input sz´ o m´ eg be nem olvasott r´ esz´ eb˝ ol ´ all´ o sz´ o. 11
Kezdetben a verem csak a verem alja jelet tartalmazza, beolvas´ asra k´ esz a teljes input sz´ o, s a veremautomat´ ahoz tartoz´ o v´ eges automata a kezd˝ o ´ allapot´ aban van. A l´ ep´ est meghat´ aroz´ o ´ atmeneti f¨ uggv´ eny nemdeterminisztikus, azaz a k¨ ovetkez˝ o l´ ep´ es nem felt´ etlen¨ ul egy´ ertelm˝ u. Az input sz´ ot az automata most is akkor fogadja el, ha tud ´ ugy m˝ uk¨ odni, hogy a sz´ o beolvas´ as´ anak hat´ as´ ara v´ eg´ allapotba ker¨ ul, a verem tartalma k¨ oz¨ omb¨ os. A kezd˝ o konfigur´ aci´ o a verem alja jelb˝ ol mint egybet˝ us sz´ ob´ ol, a kezdeti ´ allapotok egyik´ eb˝ ol ´ es a teljes input sz´ ob´ ol ´ all. Innen kell tudni eljutni egy v´ egkonfigur´ aci´ oba, amely egy veremsz´ ob´ ol, egy v´ eg´ allapotb´ ol ´ es az ¨ ures sz´ ob´ ol ´ all. 12
Defin´ıci´ o Veremautomata a k¨ ovetkez˝ o hetes: A = (Z, A, X, δ, z0, A0, AF ), ahol Z A X δ :Z×A× z0 ∈ Z A0 ⊆ A AF ⊆ A
verem´ ab´ ec´ e, a bels˝ o´ allapotok nem ¨ ures ´ es v´ eges halmaza, a bemen˝ o jelek ´ ab´ ec´ eje, ∗ (X ∪ {λ}) → 2Z ×A a (nemdeterminisztikus) ´ atmeneti f¨ uggv´ eny, a verem alja jel, a veremautomata kezd˝ o´ allapotai, a veremautomata v´ eg- (vagy elfogad´ o) ´ allapotai.
A δ f¨ uggv´ eny ´ ert´ ekei v´ eges halmazok. Konfigur´ aci´ ok halmaza: Z ∗AX ∗
(felt´ etelez´ es: A ∩ (Z ∪ X) = ∅) 13
Defin´ıci´ o Az A veremautomata egy P ∈ Z ∗AX ∗ konfigur´ aci´ ot egy l´ ep´ esben ´ atalak´ıt a Q ∈ Z ∗AX ∗ konfigur´ aci´ oba (jelekben: P ⇒ Q), ha van olyan x ∈ X, z ∈ Z, a, b ∈ A, valamint W1, W2 ∈ Z ∗, R ∈ X ∗, hogy a k¨ ovetkez˝ o ¨ osszef¨ ugg´ esek valamelyike fenn´ all: (a) P = W2zaxR, (b) P = W2zaR,
Q = W2W1bR Q = W2W1bR
´ es ´ es
(W1, b) ∈ δ(z, a, x) (W1, b) ∈ δ(z, a, λ).
A W2 sz´ o a z bet˝ uvel alkotja a verem tartalm´ at (z a verem teteje), a a pillanatnyi ´ allapot, x az input sz´ o soron k¨ ovetkez˝ o´ es beolvas´ asra ker¨ ul˝ o bet˝ uje, R (az esetleges x bet˝ uvel) az input sz´ o m´ eg be nem olvasott r´ esze, W1 a verem teteje hely´ ebe ker¨ ul˝ o sz´ o. 14
Defin´ıci´ o A veremautomata ´ altal elfogadott nyelv: LA = {R ∈ X ∗ | z0a0R ⇒∗ W a valamely W ∈ Z ∗, a0 ∈ A0 ´ es a ∈ AF eset´ en.} T´ etel A k¨ ornyezetf¨ uggetlen nyelvek oszt´ alya egybeesik a veremautomat´ ak ´ altal elfogadott nyelvek oszt´ aly´ aval. Defin´ıci´ o Amennyiben az ´ atmeneti f¨ uggv´ eny determinisztikus, azaz δ : Z × A × X → Z ∗ × A, akkor a veremautomat´ at determinisztikusnak nevezz¨ uk. T´ etel A determinisztikus veremautomat´ ak ´ altal elfogadott nyelvek oszt´ alya val´ odi r´ eszoszt´ alya a nemdeterminisztikus veremautomat´ ak ´ altal elfogadott nyelvek oszt´ aly´ anak. 15
Mondatszerkezet˝ u Nyelvek ´ es a Turing-g´ epek A Turing-g´ ep egy potenci´ alisan v´ egtelen szalagmem´ ori´ aval ´ es egy ´ır´ oolvas´ o fejjel ell´ atott v´ eges automata. A szalagmem´ oria poz´ıci´ okra van osztva, s minden egyes poz´ıci´ o mint mem´ oria-egys´ eg az ´ ugynevezett szalag´ ab´ ec´ e pontosan egy bet˝ uj´ enek t´ arol´ as´ ara k´ epes. Kezdetben a Turing-g´ ep egy specifik´ alt kezd˝ o´ allapot´ aban van, a szalagon egy v´ eges hossz´ us´ ag´ u startsz´ o helyezkedik el, s az ´ır´ o-olvas´ o fej a startsz´ o els˝ o bet˝ uj´ en ´ all. A startsz´ o el˝ otti ´ es ut´ ani (v´ egtelen sok) szalagpoz´ıci´ o egy speci´ alis bet˝ uvel, a sz´ ok¨ ozzel van felt¨ oltve. A Turing-g´ ep egy elemi oper´ aci´ oja az ´ır´ o-olvas´ o fej alatti bet˝ u olvas´ as´ ab´ ol, ezen bet˝ u fel¨ ul´ır´ as´ ab´ ol, a bels˝ o´ allapot v´ altoztat´ as´ ab´ ol, s az ´ır´ oolvas´ o fej egy poz´ıci´ oval val´ o balra vagy jobbra mozgat´ as´ ab´ ol, vagy ´ eppen a fej helybenhagy´ as´ ab´ ol ´ all. Amennyiben a Turing-g´ ep eljut egy v´ eg´ allapotba, meg´ all. 16
Defin´ıci´ o A Turing-g´ ep egy rendezett hatos: M = (A, a0, X, [, AF , µ), ahol A
a g´ ep bels˝ o´ allapotainak (v´ eges) halmaza,
a0 (∈ A)
a kezd˝ o´ allapot,
X
a szalag´ ab´ ec´ e,
[ (∈ X)
a sz´ ok¨ oz bet˝ u,
AF (⊆ A)
a v´ eg´ allapotok halmaza,
µ : (A \ AF ) × X → A × X × {Bal, Jobb, Helyben} a g´ ep nem felt´ etlen¨ ul minden¨ utt ´ ertelmezett mozg´ asf¨ uggv´ enye. 17
µ: haktu´ alis ´ allapot, ´ır´ o-olvas´ o fej alatti jeli → h´ uj ´ allapot, a szalagjelet fel¨ ul´ır´ o szimb´ olum (mely nem felt´ etlen k¨ ul¨ onb¨ oz˝ o a fel¨ ul´ırt szimb´ olumt´ ol), az elmozdul´ as ir´ anyai. Konfigur´ aci´ ok halmaza: X ∗AX ∗ \ Felt´ etelez´ es: A ∩ X = ∅.
{[}X ∗AX ∗ ∪ X ∗AX ∗{[}
Defin´ıci´ o Az M Turing-g´ ep egy P konfigur´ aci´ ot egy l´ ep´ esben ´ atalak´ıt a Q konfigur´ aci´ oba (jelekben: P ⇒ Q), ha van olyan a, b ∈ A, x, y, z ∈ X, R, S ∈ X ∗, valamint j, k ∈ N0, hogy a k¨ ovetkez˝ o ¨ osszef¨ ugg´ esek valamelyike fenn´ all: a) b) c)
[ P [ = RxayS, [ P [ = RxayS, [ P [ = RxayS,
µ(a, y) = hb, z, Jobbi, µ(a, y) = hb, z, Helybeni, µ(a, y) = hb, z, Bali,
[j Q [k = RxzbS [j Q [k = RxbzS [j Q [k = RbxzS 18
Defin´ıci´ o Az M Turing-g´ ep ´ altal elfogadott nyelv: LM = {P ∈ X ∗ | a0P ⇒∗ QaR, ahol a ∈ AF } T´ etel A Turing-g´ epek ´ altal elfogadott nyelvek oszt´ alya megegyezik a mondatszerkezet˝ u nyelvek oszt´ aly´ aval. A kor´ abbi automat´ akhoz hasonl´ oan defini´ alhat´ o a nemdeterminisztikus Turing-g´ ep, ´ es az ´ altala elfogadott nyelv. T´ eetel A nemdeterminisztikus Turing-g´ epek ´ altal elfogadott nyelvek oszt´ alya megegyezik a mondatszerkezet˝ u nyelvek oszt´ aly´ aval. 19
K¨ ornyezetf¨ ugg˝ o Nyelvek ´ es a Line´ arisan Korl´ atolt Automat´ ak Ha kik¨ otj¨ uk, hogy a nemdeterminisztikus Turing-g´ ep m˝ uk¨ od´ ese sor´ an legfeljebb egy konstansszor annyi szalagpoz´ıci´ ot haszn´ aljon, mint a startsz´ o hossza, a line´ arisan korl´ atolt automata fogalm´ ahoz jutunk. T´ etel A k¨ ornyezetf¨ ugg˝ o nyelvek oszt´ alya egybeesik a line´ arisan korl´ atolt automat´ ak ´ altal elfogadott nyelvek oszt´ aly´ aval. Megjegyz´ es Mindezideig nevezetes megoldatlan probl´ ema, hogy a determinisztikus line´ arisan korl´ atolt automat´ ak ´ altal felismert nyelvek oszt´ alya val´ odi r´ eszoszt´ alya-e a nemdeterminisztikus line´ arisan korl´ atolt automat´ ak ´ altal felismert nyelvek oszt´ aly´ anak. 20
Megjegyz´ es Igazolhat´ o az is, hogy a line´ arisan korl´ atolt automata alkalmas ´ atdefini´ al´ as´ aval el´ erhet˝ o, hogy m˝ uk¨ od´ ese sor´ an legfeljebb annyi szalagpoz´ıci´ ot vegyen ig´ enybe, mint a startsz´ o hossza, s ugyanakkor az ´ altala elfogadott nyelv egybeess´ ek az eredeti line´ arisan korl´ atolt automata ´ altal elfogadott nyelvvel.
21
Turing-g´ ep mint jel´ atalak´ıt´ o Azt mondjuk, hogy az M = (A, a0, X, [, AF , µ) Turing-g´ ep meg´ all a P ∈ X ∗ kezd˝ o sz´ ora, ha vannak olyan Q, R ∈ V ∗ szavak ´ es a ∈ AF v´ eg´ allapot, hogy a0P ⇒∗ QaR. Ekkor azt is mondhatjuk, hogy a Turing-g´ ep a P sz´ ohoz el˝ o´ all´ıtja a QR ∈ X ∗ sz´ ot. ´Igy egy Turing-g´ ep egy parci´ alis, alfabetikus lek´ epez´ est defini´ al, m´ as szavakkal a Turingg´ ep kisz´ am´ıt egy parci´ alis, alfabetikus f¨ uggv´ enyt. Az embereknek van valamilyen elk´ epzel´ es¨ uk (intu´ıci´ ojuk) a t´ enyleges (effekt´ıv) kisz´ am´ıthat´ os´ agr´ ol. A k¨ ovetkez˝ o t´ ezis egy intuit´ıv ´ all´ıt´ ast kapcsol ¨ ossze egy egzakt ´ all´ıt´ assal: Church-t´ ezis Minden olyan parci´ alis f¨ uggv´ eny, amely effekt´ıve kisz´ am´ıthat´ o, Turing-g´ eppel is kisz´ am´ıthat´ o. 22
Probl´ ema oszt´ alyok ´ es megoldhat´ os´ aguk A Turing-g´ ep egy input sz´ ohoz igen-nem v´ alaszt is rendelhet (pl. a QR kimenet tartalmaz-e sz´ ok¨ ozt vagy nem). Ilyen m´ odon is defini´ alhat´ o nyelv. Defin´ıci´ o Egy V ´ ab´ ec´ e feletti nyelvet (V ∗ egy r´ eszhalmaz´ at) • rekurz´ıvnek nevez¨ unk, ha van olyan igen-nem v´ alaszokat ad´ o Turing-g´ ep, amely a V ∗ minden elem´ ere meg´ all, ´ es a v´ alasz pontosan akkor igen, ha a sz´ o eleme a nyelvnek. • rekurz´ıve felsorolhat´ onak nevez¨ unk, ha van olyan igen-nem v´ alaszokat ad´ o Turing-g´ ep, amely a nyelv minden elem´ ere meg´ all igen v´ alasszal, ´ es ha egy nyelven k´ıv¨ uli elemre meg´ all, akkor a v´ alasz nem. 23
T´ etel A k¨ ornyezetf¨ ugg˝ o (´ es ´ıgy a k¨ ornyezetf¨ uggetlen ´ es a regul´ aris) nyelvek rekurz´ıv nyelvek. A mondatszerkezet˝ u nyelvek rekurz´ıve felsorolhat´ ok. Probl´ ema oszt´ aly nak nevez¨ unk egy olyan halmazt, amelyhez van olyan V ´ ab´ ec´ e, amely seg´ıts´ eg´ evel az oszt´ aly minden eleme (nem felt´ etlen¨ ul egy´ ertelm˝ uen) megfogalmazhat´ o, azaz l´ etezik V ∗-nak a probl´ emaoszt´ alyra val´ o lek´ epez´ ese, tov´ abb´ a az oszt´ aly minden elem´ ehez tartozik egy-egy logikai ´ ert´ ek. Az igaz ´ ert´ ek˝ u probl´ em´ ak halmaz´ anak ˝ osk´ epe egy r´ eszhalmaza V ∗-nak, azaz egy nyelv. A probl´ ema oszt´ alyt megoldhat´ o nak nevezz¨ uk, ha ez a nyelv rekurz´ıv, illetve parci´ alisan megoldhat´ o nak, ha ez a nyelv rekurz´ıve felsorolhat´ o. 24
Egy probl´ ema oszt´ aly pl. a Turing-g´ epek meg´ all´ asa: Adott egy Turing-g´ ep ´ es egy input sz´ o. Vajon meg´ all-e a Turing-g´ ep erre a sz´ ora. Ez a probl´ ema oszt´ aly nem megoldhat´ o, de parci´ alisan megoldhat´ o. A parci´ alis megoldhat´ os´ ag igazol´ asa: Vajon l´ etezik-e univerz´ alis Turing-g´ ep, olyan Turing-g´ ep, amely tetsz˝ oleges Turing-g´ epet – ¨ onmag´ at is bele´ ertve – k´ epes szimul´ alni. Erre a v´ alasz: igen. Az univerz´ alis Turing-g´ ep kimenete legyen mindig igen. Ez a Turing-g´ ep egy rekurz´ıve-felsorolhat´ o nyelvet defini´ al, ´ eppen a sz¨ uks´ eges ˝ osk´ epet.
K¨ osz¨ on¨ om a figyelmet 25
