NEODLO ˇ CLJIVI PROBLEMI V TEORIJI IZRA ˇ CUNLJIVOSTI

UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA

LUKA VIKTOR ROGA ˇ C

NEODLO ˇ CLJIVI PROBLEMI V TEORIJI IZRA ˇ CUNLJIVOSTI

MAGISTRSKO DELO

LJUBLJANA, 2017

UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA

POU ˇ CEVANJE, PREDMETNO POU ˇ CEVANJE

LUKA VIKTOR ROGA ˇ C

NEODLO ˇ CLJIVI PROBLEMI V TEORIJI IZRA ˇ CUNLJIVOSTI

MAGISTRSKO DELO

MENTOR: red. prof. dr. ALEKSANDER MALNI ˇ C SOMENTOR: doc. dr. ROK POˇ ZAR

LJUBLJANA, 2017

Zahvala

Mentorju red. prof. dr. Aleksandru Malniˇcu in somentorju doc. dr. Roku Poˇzarju hvala za strokovno pomoˇc, nasvete in vodenje pri nastajanju magistrskega dela.

Druˇzini

hvala za vso podporo in razumevanje.

Povzetek

V magistrskem delu je predstavljena hierarhija avtomatov in pripadajoˇcih jezikov. Vpeljani so pojmi, povezani z razpoznavnimi in nerazpoznavnimi jeziki. Sledi nadaljnja vpeljava podrazreda razpoznavnih jezikov; to so odloˇcljivi jeziki. S pomoˇcjo odloˇcljivih oziroma ne- odloˇcljivih jezikov prevedemo in strogo definiramo koncept odloˇcljivih oziroma neodloˇcljivih problemov. Podrobno so opisani so naslednji zgledi neodloˇcljivih problemov: problem zau- stavitve Turingovega stroja, Postov korespodenˇcni problem, problem zaposlenega bobra in Hilbertov deseti problem. V okviru magistrskega dela je bila izdelana spletna aplikacija, ki iˇsˇce konkretne reˇsitve Postovega korespodenˇcnega problema. Podrobno je opisano pro- gramsko orodje z razlago programske kode in navodili za uporabo. Naveden je tudi primer uporabe spletne aplikacije v praksi, na primer pri raˇcunalniˇskem kroˇzku.

MSC (2010) klasifikacija: 03D10, 03D20, 03D25, 68Q45.

Kljuˇcne besede: hierarhija avtomatov in jezikov, razpoznavni jeziki, odloˇcljivi jeziki, odloˇcljivi problemi, problem zaustavitve Turingovega stroja, Postov korespodenˇcni problem, problem zaposlenega bobra, Hilbertov 10. problem.

Abstract

In this master thesis the hierarchy of automata and related languages is presented. First, the concepts, associated with recognizable and unrecognizable languages are introduced, followed by further introduction of a subclass of recognized languages; these are decida- ble languages. By means of decidable and undecidable languages the concept of decidable and undecidable problems was translated and strictly defined. The following examples of undecidable problems are described in detail: the Turing’s halting problem, the Post corre- spondence problem, the busy beaver problem and the Hilbert’s tenth problem. In the frame of the master thesis, a web application which is searching for concrete solutions of the Post correspondence problem, was developed. The programming environment of the application and the interpretation of the source code with instructions for its using are described in detail. An example for the usage of the application at teaching, for example in a computer club, is presented.

MSC (2010) classification: 03D10, 03D20, 03D25, 68Q45.

Key words: hierarchy of automata and related languages, recognizable languages, deci- dable languages, decidable problems, the Turing’s halting problem, the Post correspondence problem, the Busy beaver problem, the Hilbert’s 10^th problem.

Kazalo

1 Uvod 1

2 Hierarhija avtomatov in jezikov 3

2.1 Konˇcni avtomat . . . 3

2.2 Skladovni avtomat . . . 6

2.3 Turingov stroj . . . 8

2.3.1 G¨odelovo ˇstevilˇcenje Turingovih strojev . . . 10

2.4 Linearno omejeni avtomat . . . 11

2.5 Hierarhija . . . 12

3 Razpoznavnost in nerazpoznavnost jezikov 15 4 Odloˇcljivost in neodloˇcljivost jezikov 19 5 Odloˇcljivost in neodloˇcljivost problemov 23 5.1 Problem zaustavitve Turingovega stroja . . . 23

6 Postov korespondenˇcni problem 27 7 Problem zaposlenega bobra 33 8 Problem reˇsljivosti diofantskih enaˇcb 37 9 Spletna aplikacija 39 9.1 HTML, PHP in CSS . . . 39

9.1.1 Hyper Text Markup Language . . . 39

9.1.2 PHP: Hypertext Preprocessor . . . 39

9.1.3 Cascading Style Sheets . . . 40

9.2 Opis aplikacije . . . 41

9.3 Navodila za uporabo . . . 41

9.3.1 Sploˇsna navodila . . . 41

9.3.2 Lokalna uporaba spletne aplikacije na operacijskem sistemu Windows 43 9.4 Koda . . . 44

9.4.1 Predlogi za nadgradnjo . . . 45

9.5 Uporaba pri raˇcunalniˇskem kroˇzku . . . 45

10 Zakljuˇcek 47

Slike

2.1 Konˇcni avtomat, predstavljen z diagramom. . . 4

2.2 Skladovni avtomat, predstavljen z diagramom.. . . 6

2.3 Turingov stroj, predstavljen z diagramom. . . 9

2.4 Hierarhija jezikov in pripadajoˇci avtomati. . . 12

4.1 Ce je jezikˇ L odloˇcljiv, je njegov komplement Ltudi odloˇcljiv. . . 20

4.2 Turingov stroj M. . . 20

5.1 Primer realizacije Turingovega stroja D. . . 24

5.2 Primer realizacije Turingovega stroja F. . . 24

5.3 Turingov stroj P. . . 25

7.1 Primer Turingovega strojaB(3), predstavljen z diagramom. . . 34

9.1 Zaˇcetna stran spletne aplikacije. . . 42

9.2 Aplikacija najde reˇsitev. . . 43

9.3 Programsko okno programaXAMPP. . . 43

9.4 Shematski prikaz programske kode. . . 44

Tabele

7.1 Vrednosti Σ(n) in S(n) za 1≤n≤6 [16]. . . 35

Poglavje 1 Uvod

Teorija izraˇcunljivosti je temeljna disciplina raˇcunalniˇstva, ki se ukvarja z reˇsevanjem pro- blemov s pomoˇcjo razliˇcnih modelov raˇcunanja. Pri reˇsevanju problema zahtevamo tak postopek oziroma algoritem, ki poda reˇsitev za vse mogoˇce konkretne primere. Pomembna veja teorije izraˇcunljivosti je teorija avtomatov, ki leˇzi na preseku med logiko, matematiko in raˇcunalniˇstvom.

Avtomat predstavlja abstraktni model stroja s stanji, ki se glede na vhodno besedo in funk- cijo prehodov med stanji, premika po stanjih. V primeru, da se avtomat glede na vhodno besedo ustavi v konˇcnem stanju, pravimo, da to vhodno besedo avtomat sprejme oziroma razpozna. Mnoˇzici vseh tistih besed, ki jih avtomat sprejme, pravimo jezik avtomata. Na tak naˇcin lahko generiramo formalne jezike. ˇCe za nek jezik obstaja tak avtomat, ki se ne glede na vhodno besedo vedno ustavi, pa ˇce jo avtomat sprejme ali ne, temu jeziku pravimo, da je odloˇcljiv. Na podoben naˇcin konkretnemu problemu priredimo ekvivalenten jezik in pripadajoˇci avtomat, za katerega si ˇzelimo, da je odloˇcljiv. Z drugimi besedami to pomeni, da ne glede na vhodno besedo avtomat vedno poda povratno informacijo. V primeru, da za problem ni mogoˇce najti odloˇcljivega jezika, pravimo, da je problem oziroma jezik neodloˇcljiv.

O neodloˇcljivih problemih v teoriji izraˇcunljivosti najdemo kar nekaj pomembne tuje litera- ture, kot na primer dela Turinga [1], Hopcrofta s sodelavci [2], Sipserja [3] in Martina [4].

Magistrsko delo sestavlja osem poglavij. Po uvodu je v drugem poglavju predstavljena hierar- hija avtomatov in pripadajoˇcih jezikov, kjer spoznamo naslednje ˇstiri tipe avtomatov: konˇcni avtomat, skladovni avtomat, Turingov stroj in linearno omejeni avtomat. V naslednjem po- glavju si ogledamo pomen razpoznavnosti oziroma nerazpoznavnosti jezika s konkretnim zgledom nerazpoznavnega jezika. V tretjem poglavju definiramo podrazred razpoznavnih je- zikov, ki se imenujejo odloˇcljivi jeziki. Nato v ˇcetrtem poglavju odloˇcljive jezike prevedemo na odloˇcljive probleme ter se posvetimo temeljnemu neodloˇcljivemu problemu, to je problemu zaustavitve Turingovega stroja. Sledita dve poglavji konkretnih neodloˇcljivih problemov, to sta Postov korespodenˇcni problem in problem zaposlenega bobra. V predzadnjem poglavju omenimo znameniti Hilbertov 10. problem, to je problem reˇsljivosti diofantskih enaˇcb, ki ga formuliramo s pomoˇcjo teorije avtomatov. V zadnjem poglavju razvijemo lastno sple- tno aplikacijo, ki iˇsˇce konkretne reˇsitve Postovega korespodenˇcnega problema. Zakljuˇcimo s predstavitvijo spletno okolje skupaj z opisom aplikacije, razlago programske kode, navodili za uporabo in primerom uporabe v praksi.

Poglavje 2

Hierarhija avtomatov in jezikov

Avtomat je abstraktni model stroja, ki se glede na vhodno besedo (zaporedje simbolov) in funkcijo prehodov premika po stanjih. V primeru, da avtomat po prebrani vhodni besedi obstane v konˇcnem stanju, to besedo avtomat sprejme oziroma razpozna. Mnoˇzici vseh besed, ki jih avtomat sprejme, pravimo jezik avtomata. Na tak naˇcin generiramo formalne jezike, ki jih je moˇzno hierarhiˇcno razdeliti glede na to, s kako enostavnim avtomatom jih je moˇc razpoznati. V tem poglavju bomo s pomoˇcjo literature [2, 3] spoznali to razdelitev. V prvem razdelku se bomo dodatno oprli ˇse na dela [5, 6], v drugem in ˇcetrtem razdelku bomo uporabili informacije iz [7], v tretjem iz [1, 8, 9] in v petem razdelku iz [6, 10].

2.1 Konˇ cni avtomat

Konˇcni avtomat si lahko predstavljamo kot raˇcunalnik, ki ga sestavljajo centralna procesna enota brez internega pomnilnika, zunanji pomnilnik, ki je kar trak, na katerem je zapisana beseda nad abecedo Σ, ter bralna glava, ki s traku sekvenˇcno bere vsakiˇc po en simbol dane besede, to je zaporedje simbolov iz dane abecede Σ. Procesno enoto sestavljajo stanja in kazalec na stanja; eno od stanj jezaˇcetno stanje, nekatera pa sokonˇcna stanja. Kazalec stanj se premika glede na simbol, ki ga prebere bralna glava. ˇCe se kazalec z zaˇcetnega stanja po branju vhodne besede prestavi v eno od konˇcnih stanj, pravimo, da avtomat prepozna vhodno besedo in jo sprejme. Jezik avtomata M je mnoˇzica vseh tistih besede nad abecedo Σ, ki jih avtomat sprejme; oznaˇcimo gaL(M).

Bolj nazorno lahko avtomat predstavimo v obliki diagrama, pri ˇcemer so stanja narisana kot krogci, prehodi med stanji pa kot usmerjene povezave s pripadajoˇco oznako, ki predstavlja prebrani simbol. Zaˇcetno in konˇcno stanje sta posebej oznaˇceni. Zaˇcetno stanje je predsta- vljeno v obliki krogca s ˇsirˇso puˇsˇcico nanj; konˇcno stanje pa je oblikovan krogec s posebno obrobo. Te oznake veljajo za vse nadaljnje avtomate.

Zgled 1.

Na sliki 2.1 je prikazan diagram konˇcnega avtomata M nad abecedo Σ ={0,1}, ki sprejme jezik

L(M) ={w∈Σ|enak prvi in zadnji simbol v besediw}.

4

Slika 2.1: Konˇcni avtomat, predstavljen z diagramom.

Formalno je konˇcni avtomat urejena peterica

M_KA = (Q, Σ, δ, s, F), pri ˇcemer je:

• Q – mnoˇzica stanj,

• Σ – abeceda,

• s∈Q – zaˇcetno stanje,

• F ⊆Q– neprazna mnoˇzica konˇcnih stanj,

• δ:Q×Σ→Q– funkcija prehodov med stanji.

Zgoraj smo formalno definirali konˇcni avtomat, ki ga bolj natanˇcno imenujemo determini- stiˇcni konˇcni avtomat. Obstajajo tudi nedeterministiˇcni konˇcni avtomati. Prav tako kot deterministiˇcni tudi nedeterministiˇcni konˇcni avtomat formalno sestavlja urejena peterica (Q, Σ, δ, s, F), pojavi pa se razlika pri funkciji prehodov med stanji. Pri nedetermini- stiˇcnem konˇcnem avtomatu je funkcija prehodov med stanji definirana kot

δ:Q×Σ_ε →P(Q),

kjer je P(Q) potenˇcna mnoˇzica mnoˇzice stanj in Σε = Σ∪ {ε}. Nedeterministiˇcni konˇcni avtomat poleg tega omogoˇca tako imenovane tihe prehode, kar pomeni prehajanja med stanji v primeru, ko je ”prebrana” beseda prazna beseda ε.

Formalno lahko pokaˇzemo, da deterministiˇcni in nedeterministiˇcni konˇcni avtomati sprej- mejo isti razred jezikov, kljub temu, da se na prvi pogledi zdi, da so nedeterministiˇcni konˇcni avtomati ”moˇcnejˇsih” zaradi ”ˇsirˇse” funkcije prehodov in bi zato morda lahko spre- jeli veˇcji razred jezikov. Reˇcemo, da sta dva konˇcna avtomata ekvivalentna, ˇce sprejmeta isti jezik. Ker je deterministiˇcni konˇcni avtomat zgolj posebna oblika nedeterministiˇcnega, lahko zgornjo trditev zapiˇsemo z izrekom 1. Dokaz najdemo v literaturi [2, 3, 5].

Izrek 1 Vsak nedeterministiˇcni konˇcni avtomat je ekvivalenten kakemu deterministiˇcnemu konˇcnemu avtomatu.

Uporabnost ekvivaletnosti deterministiˇcnih in nedeterministiˇcnih konˇcnih avtomatov je v tem, da je za doloˇceni jezik laˇzje skonstruirati nedeterministiˇcni konˇcni avtomat kot deter- ministiˇcnega. Razred jezikov, ki jih sprejemajo konˇcni avtomati, imenujemo tudi razred regularnih jezikov. To pa zato, ker so to natanko tisti jeziki, ki jih lahko formalno opiˇsemo s pomoˇcjo regularnih izrazov v pregledni krajˇsi obliki. Mnoˇzico regularnih izrazov Reg(Σ) in pripadajoˇcih regularnih jezikov nad abecedo Σ definiramo rekurzivno na naslednji naˇcin:

1. Regularni izraz ∅ definira regularni jezik L(∅) = ∅, regularni izraz ε pa regularni jezik L(ε) = {ε}.

2. Naj boa ∈Σ. Potem je a∈ Reg(Σ) regularni izraz, ki definira regularni jezikL(a) = {a}.

3. ˇCe sta r₁ ∈ Reg(Σ) in r₂ ∈ Reg(Σ) regularna izraza, potem je tudi njun stik r₁r₂ ∈ Reg(Σ) regularni izraz; jezik, ki mu pripada, pa je stik jezikov, ki pripadata regularnima izrazoma r₁ in r₂, to je, L(r₁ ·r₂) =L(r₁)◦L(r₂) = {a·b | a∈L₁, b ∈L₂}.

4. ˇCe sta r₁ ∈Reg(Σ) in r₂ ∈ Reg(Σ) regularna izraza, potem je r₁+r₂ ∈ Reg(Σ) prav tako regularni izraz; jezik, ki mu pripada, pa je L(r₁+r₂) = L(r₁)∪L(r₂), torej unija regularnih jezikov, ki pripadata izrazoma r1 inr2.

5. ˇCe je r∈Reg(Σ) regularni izraz, potem je njegovoKleenovo zaprtje r^∗ ∈Reg(Σ) tudi regularni izraz, ki mu pripada ustrezeno Kleenovo zaprtje jezika L(r), torej L(r^∗) = L(r)^∗.

6. Regularni izrazi so natanko tiste besede nad razˇsirjeno abecedo Σ∪ {+,·,^∗,(,)}, ki jih iz 1. in 2. toˇcke izpeljemo po pravilih iz toˇcke 3., 4. in 5.

Zaradi enostavnejˇsega zapisa se dogovorimo za prioritetni vrstni red operacij. Operacija z najviˇsjo prioriteto je operacija Kleenovo zaprtje, sledi stik in nato unija. Tako na primer regularni izraz ((01) + 1)^∗+ 0 zapiˇsemo kot (01 + 1)^∗+ 1.

V luˇci izreka 1 v nadaljevanju ne bomo razlikovali med deterministiˇcnim in nedetermini- stiˇcnim konˇcnim avtomatom, zato ga bomo imenovali kar konˇcni avtomat (razen, ˇce bo to posebej poudarjeno). Izrek, povezan s konˇcnimi avtomati in regularnimi izrazi, bomo zapisali z izrekom 2. Dokaz je v literaturi [2, 3, 5].

Izrek 2 Za vsak regularni izraz r nad abecedo Σ obstaja tak konˇcni avtomat M_KA nad abe- cedo Σ, da je jezik avtomata L(M_KA) enak jeziku regularnega izraza r. Obratno, za vsak (determinstiˇcni) konˇcni avtomat nad abecedo Σ obstaja tak regularni izraz r nad Σ, da je L(r) enak jeziku tega avtomata.

Regularni jezik konˇcnega avtomata iz zgleda 1, ki sprejme besede nad abecedo Σ = {0,1}, ki se zaˇcnejo in konˇcajo z enakim simbolom, zapiˇsemo z regularnim izrazom

1(0 + 1)^∗1 + 0(0 + 1)^∗0.

V tem poglavju smo spoznali formalno in neformalno koncept konˇcnega avtomata in regu- larnega izraza. V naslednjem poglavju si bomo ogledali konˇcni avtomat z dodatnim pomnil- nikom, ki ga imenujemo sklad. Takemu avtomatu bomo rekli skladovni avtomat.

2.2 Skladovni avtomat

Skladovni avtomat je konˇcni avtomat z dodatnim pomnilnikom, tako imenovanim skladom, kamor avtomat zapisuje/preberesimbole skladovne abecede Γ po principuzadnji noter –prvi ven. To pomeni, da podatek, v naˇsem primeru simbol iz abecede Γ, ki je zadnji dodan na sklad, ga bo tudi prvi zapustil. Lahko si predstavljamo, da so simboli iz abecede Γ naloˇzeni samostojno drug nad drugega, zadnjemu dodanemu podatku pa pravimo vrh sklada. Sklad poleg tega podpira dve operaciji, ”dodaj na vrh” in ”briˇsi z vrha”. S to nadgradnjo se spre- meni funkcija prehodov med stanji in procesiranje skladovnega avtomata. Procesno enoto tako kot konˇcni avtomat sestavljajo stanja (eno je zaˇcetno stanje –q0, nekatera pa so konˇcna stanja) in kazalec na stanja. Kazalec na stanja se premika glede na prebrani simbol, ki ga prebere bralna glava s traku in prebrani simbol z vrha sklada, ki se nato izbriˇse. Ko se kazalec na stanja premakne na naslednje stanje, se na vrh sklada doda nov simbol, ki ga dodeluje funkcija prehodov med stanji. ˇCe se kazalec stanj po branju vhodne besede in vrha sklada prestavi iz zaˇcetnega stanja v konˇcno stanje, pravimo, da skladovni avtomat prepozna vhodno besedo in jo sprejme. Potrebno je poudariti, da je lahko sklad na zaˇcetku tudi prazen.

Skladovni avtomat lahko laˇzje predstavimo v grafiˇcni obliki, za katero veljajo podobni do- govorjeni grafiˇcni elementi, kot smo jih spoznali v prejˇsnjem poglavju. Razlika se pojavi pri oznakah na usmerjenih povezavah, ki predstavljajo funkcijo prehoda med stanji. Oznaka sestoji iz treh elementov: prvi predstavlja prebrani simbol s traku, drugi simbol predstavlja prebrani simbol z vrha sklada (po branju se izbriˇse), tretji simbol pa predstavlja simbol, ki ga zapiˇsemo na vrh sklada. Oglejmo si spodnji zgled.

Zgled 2.

Na sliki 2.2 je prikazan diagram skladovnega avtomataM, ki sprejme natanko tiste besede, ki so vsebovane v mnoˇzici jezika

L(M) ={0ⁿ1ⁿ |n≥0}.

Simbol $ oznaˇcuje prazen sklad.

Slika 2.2: Skladovni avtomat, predstavljen z diagramom.

4

Formalno skladovni avtomat definiramo kot urejeno ˇsesterico M_SA = (Q,Σ,Γ, δ, q₀, F), pri ˇcemer je

• Q – mnoˇzica stanj,

• Σ – abeceda vhodne besede,

• Γ – abeceda sklada,

• δ :Q×Σ_ε×Γ_ε→P(Q×Γ_ε) – funkcija prehodov med stanji, kjer je Σ_ε = Σ∪ {ε} in Γ_ε = Γ∪ {ε},

• q₀ ∈Q – zaˇcetno stanje in

• F ⊆Q – neprazna mnoˇzica konˇcnih stanj.

Podobno kot pri konˇcni avtomatih, skladovne avtomate razdelimo nadeterministiˇcne inne- deterministiˇcne. Ponovno se razlikujeta v funkciji prehodov med stanji, kjer je pri nedeter- ministiˇcnem prehod definiran kot funkcija iz mnoˇzice stanj Qv potenˇcno mnoˇzico stanj, pri deterministiˇcnem pa je novo stanje natanˇcno doloˇceno. Zaradi laˇzjega razumevanja in pred- stavljivosti obiˇcajno uporabljamo nedeterministiˇcni skladovni avtomat, ki je opisan zgoraj.

Razreda deterministiˇcnih in nedeterministiˇcnih skladovnih avtomatov sta si ekvivalentna v smislu, da generirata isti razred jezikov.

Skladovni avtomati generirajo jezike imenovane kontekstno neodvisni jeziki, ki jih opiˇsemo s konceptom kontekstno neodvisne gramatike. Kontekstno neodvisno gramatiko G formalno definiramo kot urejeno ˇcetverico

(V,Σ, R, S), kjer je:

• V – mnoˇzica simbolov, ki jim reˇcemospremenljivke,

• Σ – mnoˇzica simbolov, ki jim reˇcemo konstante, pri ˇcemer velja Σ∩V =∅,

• R – mnoˇzica pravil za izpeljavo, ki rekurzivno omogoˇcajo izpeljavo spremenljivke v konstanto,

A→α; A∈V, α ∈(V ∪Σ)^∗,

• S ∈V – zaˇcetna spremenljivka.

Jezik L(G) gramatike G je mnoˇzica vseh tistih besed nad abecedo Σ, ki jih lahko z uporabo pravil izpeljav izpeljemo iz zaˇcetne spremenljivke. Takemu jeziku pravimo, da je kontekstno neodvisen. Izrek, ki se nanaˇsa na skladovne avtomate in kontekstno neodvisne jezike, je zapisana spodaj. Dokaz bralec lahko najde v literaturi [2, 3, 5].

Izrek 3 Za vsak skladovni avtomat MSAlahko konstruiramo kontekstno neodvisno gramatiko G, da velja L(G) = L(M_SA). Obratno, za vsak kontekstno neodvisni jezik L(G) obstaja tak skladovni avtomat M, da velja L(M_SA) = L(G).

V nadaljevanju bomo spoznali nadgrajen skladovni avtomat, imenovan Turingov stroj.

2.3 Turingov stroj

Turingov stroj si lahko predstavljamo kot nadgrajen skladovni avtomat, kjer pa zapis sim- bolov ne poteka na sklad, ampak kar na trak vhodne besede. Trak, ki je neomejen v desno, je razdeljen na celice, vsaka s svojim pripadajoˇcim simbolom, ki pa je lahko tudi prazen (oznaˇcuje prazno celico). Zapis je mogoˇc v prazno celico ali v ˇze zapisano celico traku, ka- tere vsebino je naprej potrebno izbrisati in nato na novo zapisati. To je prva pomembna razlika, saj skladovni avtomat ne omogoˇca sprememb vsebine traku. Dodatno je nadgrajena bralna glava, pri kateri je omogoˇceno premikanje levo in desno in ne samo v eno smer. Tu- ringov stroj v enem koraku procesiranja opravi branje simbola, spremembo stanja, brisanje oziroma zapis simbola v trenutno dostopno celico ter nazadnje premik bralne glave za eno celico levo ali desno (ˇce je bralna glava na zaˇcetku in se bralna glava premakne v levo, te- daj Turingov stroj oˇcitno ne more premakniti bralne glave, zato preneha s procesiranjem – ”zmrzne”). Mnoˇzica konˇcnih stanj obsega dve posebni stanji – stanje qsprejmi in stanje q_zavrni. Turingov stroj razpozna vhodno besedo w ∈ Σ^∗, ˇce obstane v q_sprejmi. Mnoˇzici besed, ki jih dani Turingov stroj sprejme, pravimojezik Turingovega stroja.

Turingov stroj je formalno definiran kot urejena sedmerica M_{T S} = (Q,Σ,Γ, δ, q₀, q_sprejmi, q_zavrni), pri ˇcemer je:

• Q – mnoˇzica stanj,

• Σ – abeceda vhodne besede, ki ne vsebujepraznega simbola (oznaˇcimo ga z [),

• Γ – abeceda traku, ki vsebuje prazni simbol, pri ˇcemer je abeceda vhodne besede Σ njegova podmnoˇzica, torej

[∈Γ in Σ⊆Γ\ {[},

• q₀ ∈Q– zaˇcetno stanje,

• q_sprejmi – konˇcno stanje,

• q_zavrni – zavrnitveno stanje, pri ˇcemer mora veljati q_zavrni6=q_sprejmi,

• δ:Q×Γ→Q∪ {q_sprejmi, q_zavrni} ×Γ× {L, R} – funkcija prehodov med stanji.

Oglejmo si pojem trenutni opis procesiranja Turingovega stroja. Trenutni opis je zapis v obliki besede, ki jo zapiˇsemo na naslednji naˇcin: besedi, ki je trenutno zapisana na traku, dodamo stanje natanko pred simbol, ki je procesiran v naslednjem koraku. Na primer, ˇce imamo vhodno besedo 01001 in zaˇcetno stanje q₀, je zaˇcetni trenutni opis q₀01001, kar po- meni, da pri stanju q₀ prebere simbol 0. Trenutni opis 010q₃01 pa predstavlja neki korak procesiranja, kjer v stanjuq₃preberemo simbol 0. Zzaporedjem trenutnih opisov procesiranja Turingovega stroja lahko zapiˇsemo vsak korak procesiranja Turingovega stroja. Zaporedje trenutnih opisov je konˇcno, ˇce se Turingov stroj ustavi bodisi v stanjuq_sprejmi bodisiq_zavrni. Posamezne korake zaporedja trenutnih opisov loˇcimo s simbolom #.

Kot konˇcne in skladovne avtomate lahko tudi Turingove stroje laˇzje predstavimo v grafiˇcni obliki, za katero veljajo podobni dogovorjeni grafiˇcni elementi, kot smo jih spoznali v prej- ˇsnjih podpoglavjih. Razlika je pri oznaki nad usmerjeno povezavo, ki se sestoji iz treh simbolov: prvi predstavlja prebrani simbol s traku, drugi zapis simbola, tretji pa predstavlja simbol, ki pove smer premika bralne glave.

Zgled 3.

Na sliki 2.3 je prikazan diagram Turingovega stroja, ki sprejme natanko besede regularnega jezika, ki ga opiˇsemo z regularnim izrazom 01^∗0.

Slika 2.3: Turingov stroj, predstavljen z diagramom.

Na diagramu vsaka puˇsˇcica

0 /X,R

−−−−→

z oznako nad njo ponazarja trenutni prebrani simbol, zapis novega simbola v celico prebra- nega simbola, smer premika bralne glave in prehod v naslednji trenutni opis v zaporedju.

Kot primer procesiranja Turingovega stroja si oglejmo procesiranje vhodne besede 01110.

Procesiranje zapiˇsimo z zaporedjem trenutnih opisov procesiranja Turingovega stroja:

01110 q₀01110

0 /X,R

−−−−→ Xq₁1110

1 /Y,R

−−−−→ XY q₁110

1 /Y,R

−−−−→ XY Y q₁10

1 /Y,R

−−−−→ XY Y Y q₁0

0 /X,R

−−−−→ XY Y Y Xq2 [ /[,R

−−−→ XY Y Y X[q_sprejmi.

Zaporedje trenutnih opisov procesiranja Turingovega stroja nam pove, da tak Turingov stroj

sprejme vhodno besedo 01110. 4

Turingov stroj ima tri moˇzne izide procesiranja:

1. obstane v konˇcnem stanju q_sprejmi; 2. obstane v zavrnitvenem stanjuq_zavrni;

3. bodisi ne obstane, to je, procesiranje se nadaljuje v neskonˇcnost, bodisi stroj ”zmrzne”.

JezikL je Turingovo razpoznaven, ˇce obstaja Turingov stroj M_{T S}, katerega jezik L(M_{T S}) je enak jeziku L=L(M_{T S}).

V tem poglavju smo spoznali deterministiˇcni Turingov stroj z enim trakom. Poznamo pa ˇse nedeterministiˇcni Turingov stroj z enim trakom in Turingov stroj z veˇc trakovi, ki je lahko deterministiˇcen ali nedeterministiˇcen. ˇSe veˇc, poznamo tudi Turingove stroje z veˇc trakovi in veˇc glavami, tako deterministiˇcne kot nedeterministiˇcne, itd., kot je podano z izrekom 4.

Dokaz izreka lahko najdemo v literaturi [2, 3, 5].

Izrek 4 Vse omenjene razliˇcice Turingovega stroja je moˇzno simulirati z osnovnim deter- ministiˇcnim Turingovim strojem z enim trakom.

2.3.1 G¨ odelovo ˇ stevilˇ cenje Turingovih strojev

V tem razdelku se bomo posvetili kodiranju in ˇstevilˇcenju Turingovih strojev. Turingove stroje smo do sedaj predstavili v obliki tabele ali diagrama. Funkcijo prehodov med stanji pa lahko opiˇsemo tudi z linearnim zapisom Turingovega stroja, ki ga bomo definirali v na- daljevanju.

Naj bo M_{T S} Turingov stroj z mnoˇzico stanj Q∪ {q_sprejmi, q_zavrni} = {q₀, q₁, q₂, . . . , q_m} in abecedo traku Γ = {S0 = [, S1, S2, . . . , Sn}. Prehod δ(qi, Sj) = (Sk, A, ql) lahko zapiˇsemo tudi v obliki urejenepeterice prehoda

q_iS_jS_kAq_l, pri ˇcemer je:

• q_i – trenutno stanje,

• S_j – prebrani simbol,

• S_k – na trak zapisan simbol,

• A – premik bralne glave levo ali desno (oznaka L pomeni levo, R pa desno),

• q_l – naslednje stanje.

Na mnoˇzici vseh peteric prehodov vpeljemo linearno relacijo leksikografske ureditve:

q_iS_jS_kAq_l < q_i⁰S_j⁰S_k⁰Aq_l⁰, ˇ

ce je i < i⁰ ali i = i⁰ in j < j⁰. Linearni zapis Turingovega stroja M_{T S} dobimo, ˇce vse peterice zapiˇsemo eno za drugo v skladu z dano leksikografsko ureditvijo.

Zgled 4.

Na sliki 2.3 je prikazan Turingov stroj, ki sprejme besede regularnega jezika 01^∗0. Linearni zapis tega Turingova stroja je naslednji:

q₀[[Rq₄q₀0XRq₁q₀11Rq₄q₁[[Rq₄q₁0XRq₂q₁1Y Rq₁q₂[[Rq₅q₂00Rq₄q₂11Rq₄.

Stanjeq4 predstavlja stanjeqzavrni, stanje q5 pa stanjeqsprejmi. 4

Z vpeljavo linearnega zapisa Turingovega stroja se lahko lotimo kodiranja Turingovega stroja.

To bomo naredili s tako imenovanimi G¨odelovimi ˇstevili, ki temeljijo na praˇstevilih. Najprej praˇstevila oˇstevilˇcimo in sicer p₀ = 2, p₁ = 3, p₂ = 5, . . . Nato zakodiramo vsak sestavni del peterice. Naj bo

gn(L) = 2 gn(R) = 3

gn(qi) =p2+2i; i= 0,1,2. . . , m gn(S_j) =p_2+2j+1; j = 0,1,2, . . . , n.

Kako lahko zakodiramo celotno peterico prehoda F =q_iS_jS_kAq_l? Na naslednji naˇcin:

gn(F) = 2^gn(qi)·3^gn(Sj)·5^gn(Sk)·7^gn(A)·11^gn(ql).

Ce jeˇ F₀F₁. . . F_k linearni zapis Turingovega stroja M_{T S}, ga zakodiramo takole gn(M_{T S}) = 2^gn(F0)·3^gn(F1)·5^gn(F2)· · ·p^gn(F_k ^k).

Steviluˇ gn(MT S) pravimo G¨odelovo ˇstevilo Turingovega stroja MT S ali tudi koda Turingo- vega stroja M_{T S}.

Potrebno je opozoriti, da vsako naravno ˇstevilo ni nujno veljavna koda kakˇsnega Turingo- vega stroja. V primeru, ko imamo podano naravno ˇstevilo gn(M_{T S}) za katerega vemo, da je veljavna koda nekega Turingovega stroja, lahko linearni zapis enoliˇcno dekodiramo na naslednji naˇcin: najprej naredimo praˇstevilsko faktorizacijo ˇstevila gn(M_{T S}), nato pa po- novno na potencah gn(F_i). Tako dobimo zakodirane peterice prehodov, ki jih seveda lahko razberemo (oznaˇcimo zgn⁻¹(M_{T S})). ˇCe pa dano naravno ˇstevilo ni veljavna koda, kot smo omenili zgoraj, potem posebej definiramo, da je to koda ”praznega” Turingovega stroja, ki ima prazno funkcijo prehodov med stanji.

Z G¨odelovimi ˇstevili lahko Turingove stroje oˇstevilˇcimo: i-ti Turingov stroj M_i definiramo kot

M_i =

(M_{T S}; ˇce je gn⁻¹(i) veljavna koda nekega Turingovega stroja M_{T S}, M_∅; v vseh drugih primerih,

kjer M_∅ oznaˇcuje Turingov stroj s prazno funkcijo prehodov med stanji. Torej vsakemu naravnemu ˇstevilu pripada natanko en Turingov stroj.

V naslednjem podpoglavju bomo spoznali omejeni Turingov stroj, imenovan linearno omejeni avtomat.

2.4 Linearno omejeni avtomat

Pomembna omejena varianta Turingovega stroja je linearno omejeni avtomat, ki ga bomo spoznali v tem podpoglavju. Linearno omejeni avtomat je posebna oblika Turingovega stroja. Vsebuje vse sestavne dele Turingovega stroja, vendar pa trak ni veˇc neomejen, am- pak je omejen na interval, zamejen s posebnim levim in desnim konˇcnim znakom na traku.

Bralna glava se tako ne more premikati izven intervala, ki ga ta dva posebna znaka doloˇcata.

Jezike linearno omejenih avtomatov bolj pregledno opiˇsemo skontekstno odvisnimi gramati- kami. Taka gramatika je definirana podobno kot kontekstno neodvisna gramatika, torej kot urejena ˇcetverica (V,Σ, R, S), z nekaj razlikami:

1. Kontekstno odvisna gramatika lahko vsebuje veˇc kot en simbol na levi strani pravila izpeljave (pri ˇcemer mora biti vsaj en simbol spremenljivka), torej

αAβ →αγβ, kjer je A∈V, α, β ∈(V ∪Σ)^∗ in γ ∈(V ∪Σ)\ε.

2. ˇStevilo znakov na levi strani ne sme biti veˇcje kot na desni strani.

3. Ne dopuˇsˇcamo pravila A → ε, razen v primeru, ko je A zaˇcetna spremenljivka, ki se nikoli ne pojavi na desni strani kakega pravila.

Zaradi oblike leve strani v pravilih lahko neformalno reˇcemo, da je pri izpeljavi pomemben kontekst – podniz levo in desno od spremenljivke. Jezikom, ki jih definirajo kontekstno odvisne gramatike, reˇcemo kontekstno odvisni jeziki. Kontekstne neodvisne gramatike in linearno omejeni avtomati generirajo isti razred jezikov, kot je zapisano v izreku 5. Dokaz je v literaturi [2, 3, 5].

Izrek 5 Za vsak kontekstno odvisen jezik obstaja linearno omejeni avtomat, ki sprejme na- tanko ta jezik. Obratno, za vsak jezik linearno omejenega avtomata obstaja kontekstno odvi- sna gramatika, katere jezik je natanko jezik danega linearno omejenega avtomata.

2.5 Hierarhija

Hierarhija jezikov (in pripadajoˇcih avtomatov), ki jo je prvi opisal Noam Chomsky [10] leta 1958, je prikazana na sliki 2.4.

Slika 2.4: Hierarhija jezikov in pripadajoˇci avtomati.

V skladu s to hierarhijo razdelimo Turingovo razpoznavne jezike na 4 razrede:

3. regularni jeziki,

2. kontekstno neodvisni jeziki, 1. kontekstno odvisni jeziki, 0. Turingovi razpoznavni jeziki.

Da gre za hierarhijo, je potrebno upoˇstevati, da za vsak par indeksov i > j velja, da je i-ti razred jezikov strogo vsebovan v j-tem razredu, kar se da pokazati z izrekom 6. Dokaz lahko najdemo v literaturi [2, 10].

Izrek 6 Razred regularnih jezikov je vsebovan v razredu kontekstno neodvisnih jezikov, ta je vsebovan v razredu kontekstno odvisnih jezikov, le ta pa je vsebovan v razredu Turingovih razpoznavnih jezikih. Ob tem so vse inkluzije stroge.

Z drugimi besedami, vsak avtomat lahko simuliramo z bolj kompleksnim avtomatom, obratno pa ni mogoˇce:

• Konˇcni avtomat lahko simuliramo s skladovnim avtomatom.

• Skladovni avtomat lahko simuliramo z linearno omejenim avtomatom.

• Linearno omejeni avtomat je poseben primer Turingovega stroja.

S tem zakljuˇcujemo poglavje, v katerem smo spoznali hierarhiˇcno razdelitev avtomatov in pripadajoˇcih jezikov. V naslednjem poglavju se bomo posvetili jezikom, ki jih ne sprejme noben avtomat.

Poglavje 3

Razpoznavnost in nerazpoznavnost jezikov

V prejˇsnjem poglavju smo opredelili hierarhiˇcno razdelitev avtomatov in pripadajoˇcih jezikov.

V tem poglavja bomo natanˇcneje spoznali, da obstajajo jeziki, ki jih ne sprejme noben avtomat. Takim jezikom pravimo Turingovi nerazpoznavni jeziki. Skonstruirali bomo tudi konkreten primer takega jezika. Pri tem se bomo oprli na literaturo [2, 3, 11].

Izrek 7 Nad vsako abecedo obstaja jezik, ki ni Turingovo razpoznavnen.

Dokaz: Ker lahko Turingove stroje nad dano abecedo Σ oˇstevilˇcimo, jih je ˇstevno mnogo.

Torej je tudi Turingovo razpoznavnih jezikov nad abecedo Σ ˇstevno mnogo. Vseh jezikov nad abecedo Σ pa je neˇstevno mnogo, saj je to potenˇcna mnoˇzica mnoˇzice vseh besed Σ^∗. Po Cantorjevem izreku je moˇc mnoˇzice 2^Σ∗ veˇcja od moˇci mnoˇzice Σ^∗.

V nadaljevanju si bomo ogledali primer Turingovo nerazpoznavnega jezika. Za laˇzje razume- vanje se najprej seznanimo z metodo diagonalizacije, ki jo je leta 1891 Georg Cantor uporabil pri dokazu, da je mnoˇzica realnih ˇstevil neˇstevno neskonˇcna [11]. Ponovimo nekaj osnov iz teorije mnoˇzic.

Denimo, da imamo mnoˇzici A inB in funkcijof: A→B, ki preslika elemente iz mnoˇzice A v mnoˇzico B. Funkcijaf jeinjektivna natanko tedaj, ˇce vsak par razliˇcnih elementov a6=b iz mnoˇzice A preslika v par razliˇcnih elementov f(a)6=f(b) v mnoˇzici B. V primeru, ko za funkcijo f velja, da za vsak element iz mnoˇzice B obstaja element iz A, za katerega velja f(a) =b, pravimo, da je surjektivna. Za funkcijof, ki je injektivna in surjektivna pravimo, da je bijektivna. Pri taki preslikavi ima vsak element iz A natanko doloˇceno sliko v B in vsak element iz B je slika natanko enega elementa iz A. V tem primeru reˇcemo, da imata mnoˇzici A inB enako moˇc.

Mnoˇzica A je ˇstevna natanko tedaj, ko je konˇcna, ali pa obstaja bijektivna preslikava iz mnoˇzice A na mnoˇzico naravnih ˇstevil N.

Ne preveˇc zapleteno lahko pokaˇzemo, da med mnoˇzicama naravnih ˇstevil N in mnoˇzico racionalnih ˇstevilQ obstaja bijekcija, kar pomeni, da je mnoˇzica racionalnih ˇstevil Qˇstevna (za dokaz glej [3]). Zanima nas, kaj lahko povemo o ˇstevnosti mnoˇzice realnih ˇstevil R. V ta namen si oglejmo spodnji izrek.

Izrek 8 Mnoˇzica realnih ˇstevil R je neˇstevna [11].

Dokaz: Ker obstaja bijektivna preslikava R → (0,1), na primer _π¹arctgx+ ¹₂, je dovolj pokazati, da ne obstaja bijektivna preslikava med mnoˇzico naravnih ˇstevil N in intervalom (0,1). Recimo, da obstaja bijektivna preslikavaf medNin intervalom (0,1). Ker lahko vsako realno ˇstevilox na intervalu (0,1) zapiˇsemo v oblikix= 0, d1d2d3. . ., kjerdi zavzemajo cele vrednosti med 0 in 9, lahko f predstavimo v naslednji obliki

n f(n)

1 0, d₁₁d₁₂d₁₃d₁₄. . . 2 0, d21d22d23d24. . . 3 0, d₃₁d₃₂d₃₃d₃₄. . . 4 0, d₄₁d₄₂d₄₃d₄₄. . .

... ...

Skonstruirajmo realno ˇstevilox= 0, x₁x₂x₃x₄. . ., da veljax_n6=d_nn (pri ˇcemer izbiramo take vrednosti zax_n, da niso vse decimalke 0 ali 9). Povedano drugaˇce, decimalka x_nne zavzame vrednosti n-te decimalne ˇstevke realnega ˇstevila f(n). To so natanko vrednosti decimalnih mest na diagonali.

n f(n)

1 0, d₁₁d₁₂d₁₃d₁₄. . . 2 0, d₂₁d₂₂d₂₃d₂₄. . . 3 0, d₃₁d₃₂d₃₃d₃₄. . . 4 0, d₄₁d₄₂d₄₃d₄₄. . .

... ...

Kaj lahko povemo o ˇstevilu x? ˇStevilo x je realno ˇstevilo na intervalu (0,1), vendar ni vsebovano v sliki preslikavef, saj za vsak n∈N velja, da se f(n) in x razlikujeta na n-tem decimalnem mestu. Torej f ni surjektivna preslikava, kar je v protislovju s predpostavko.

Torej je mnoˇzica (0,1) neˇstevna. Potem pa je tudi mnoˇzica realnih ˇstevil R neˇstevna.

Z uporabo zelo podobnega ”diagonalnega principa” lahko konstruiramo konkreten primer jezika nad poljubno dano abecedo, ki ni Turingovo razpoznaven.

Naj bo Σ poljubno dana konˇcna abeceda. Simbole abecede Σ najprej poljubno oˇstevilˇcimo, nato pa vse besede w iz Σ^∗ leksikografsko uredimo v skladu z zaˇcetnim oˇstevilˇcenjem sim- bolov v abecedi Σ. Ker je besed dolˇzine k konˇcno mnogo, to je |Σ|^k, lahko vse besede nad abecedo Σ oˇstevilˇcimo z naravnimi ˇstevili: w = w_i, kjer je i = ln(w) leksikografsko ˇstevilo besede w. Kot smo spoznali v razdelku 2.3.1, lahko Turingove stroje oˇstevilˇcimo z uporabo G¨odelovih ˇstevil.

Procesiranjei-tega Turingovega strojaMi lahko opiˇsemo skarakteristiˇcnim vektorjem jezika, ki pove, katere besede ta Turingov stroj sprejme in katere ne. Vse te karakteristiˇcne vektorje po vrsticah zloˇzimo v tabelo (glej tabelo 3.1). V i-ti vrstici najdemo karakteristiˇcni vektor jezika, ki pove, katere besede sprejme Turingov stroj Mi. ˇCe je Mi =M_∅ Turingov stroj, ki sprejme prazen jezik, karakteristiˇcni vektor sestavljajo le vrednosti NE.

Skonstruirajmo tedaj diagonalni jezik:

L_D ={w_i |w_i ∈/ L(M_i)}.

Tabela 3.1: Tabela karakteristiˇcnih vektorjev.

w₁ w₂ w₃ w₄ . . . M₁

M₂ ...

M_i DA DA NE DA . . . karakteristiˇcni vektor jezika L(M_i) ...

Mj NE NE NE NE . . . karakteristiˇcni vektor jezika L(M_∅) =∅ ...

Izrek 9 Diagonalni jezik L_D ni Turingovo razpoznaven.

Dokaz: Predpostavimo, da je L_D jezik nekega Turingovega stroja. Potem je L_D =L(M_i) za nekii. Zato se ta jezik ujema s karakteristiˇcnim vektorjem jezika vi-ti vrstici v tabeli 3.1.

Vendar:

• ˇce se na i-tem diagonalnem mestu v i-ti vrstici najde DA, to jew_i ∈L(M_i), potem je w_i ∈/ L_D po definiciji diagonalnega jezika L_D;

• ˇce pa je vi-ti vrsticiNE, to jewi ∈/ L(Mi), potem jewi ∈LD po definiciji diagonalnega jezika L_D.

Sledi, da veljata naslednji implikaciji

w_i ∈L(M_i)⇒w_i ∈/ L_D wi ∈/ L(Mi)⇒wi ∈LD. Ob predpostavki, da je L_D =L(M_i), sledi, da sta implikaciji

w_i ∈L_D ⇒w_i ∈/ L_D w_i ∈/ L_D ⇒w_i ∈L_D

hkrati izpolnjeni. To pa je oˇcitno protislovje. Za vsako izjavo A velja (A ⇒ ¬A)∧(¬A ⇒ A) ∼ 0. Zato je predpostavka L_D = L(M_i) napaˇcna. Diagonalni jezik tako ni Turingovo razpoznaven.

V nadaljevanju se bomo posvetili pomembnemu vpraˇsanju, kdaj je kak jezik, ki ga sprejme nek Turingov stroj, odloˇcljiv in kdaj ne.

Poglavje 4

Odloˇ cljivost in neodloˇ cljivost jezikov

Glede na izid procesiranja lahko Turingovo razpoznavne jezike nad dano abecedo Σ razde- limo bolj natanˇcno. V tem poglavju izhajamo iz literature [2, 3, 4].

Poseben podrazred Turingovo razpozavnih jezikov tvorijo Turingovo odloˇcljivi jeziki: to so jeziki, za katere obstaja tak Turingov stroj, ki ne glede na vhodno besedo vedno konˇca pro- cesiranje bodisi v stanjuq_sprejmi, ˇce je vhodna beseda vsebovana v jeziku Turingovega stroja, bodisi v stanjuq_zavrni, ˇce vhodna beseda ni vsebovana. Pri Turingovih razpoznavnih jezikih, ki niso odloˇcljivi, gre za jezike, ki jih prepozna neki Turingov stroj, vendar se pri vhodni besedi, ki ne pripada jeziku Turingovega stroja, procesiranje konˇcna bodisi v stanju q_zavrni bodisi ne obstane. To pomeni, da ni mogoˇce odloˇciti, ali vhodna beseda pripada jeziku ali ne: ˇce stroj ne obstane, ne vemo, ali ne obstane, ker besede ni v jeziku Turingovega stroja, ali pa ne obstane, ker ni dovolj dolgo procesiral.

Ali je razred Turingovo razpozavnih jezikov kar enak razredu Turingovo odloˇcljivih jezikov?

Z drugimi besedami, ali lahko za vsak jezik, ki ga razpozna neki Turingov stroj, oblikujemo tak Turingov stroj, ki se bo vedno ustavil in ki bo razpoznal prav ta jezik? ˇCe je to res, bi to pomenilo, da je vsak jezik algoritmiˇcno razpoznaven. A to ni res. V nadaljevanju bomo spoznali, da obstajajo Turingovo razpoznavni, vendar neodloˇcljivi jeziki. V ta namen si oglejmo izreka 10 in 11.

Izrek 10 Ce je jezikˇ Lnad dano abecedo Σodloˇcljiv, je njegov komplementL tudi odloˇcljiv.

Dokaz: Naj boLTuringovo odloˇcljiv jezik, to je, naj zanj obstaja tak Turingov strojML, da se procesiranje vhodne besede konˇca bodisi v stanju q_sprejmi, ˇce je vhodna beseda vsebovana v jeziku Turingovega stroja, bodisi v stanju q_zavrni, ˇce vhodna beseda ni vsebovana v jeziku Turingovega stroja. Za jezik L lahko sedaj konstruiramo Turingov stroj M_L, ki najprej preda vhodno besedo w v procesiranje stroju M_L; konˇcni izid procesiranja stroja M_L pa je naslednji: za w ∈ L se M_L ustavi v stanju q_zavrni, za w /∈ L pa v stanju q_sprejmi. Ker se Turingov stroj ML vedno ustavi, se ustavi tudi M_L, kar pomeni, da je jezik L odloˇcljiv.

Dokaz je shematiˇcno je prikazan na sliki 4.1.

Izrek 11 Jezik L nad dano abecedo Σ je odloˇcljiv natanko takrat, ko sta L in njegov kom- plement L Turingovo razpoznavna.

Dokaz: Pokaˇzimo v obe smeri. Naj bo jezik L odloˇcljiv. Po izreku 10 je tudi L odloˇcljiv.

Ker je vsak Turingovo odloˇcljiv jezik Turingovo razpoznaven, sta tudi L in L Turingovo

Slika 4.1: ˇCe je jezik L odloˇcljiv, je njegov komplementL tudi odloˇcljiv.

razpoznavna.

Sedaj pa predpostavimo, da sta jezika L in L Turingovo razpoznavna. Potem obstajata Turingova stroja M_L in M_L, za katera velja, da je L = L(M_L) in L = L(M_L). Za jezik L oblikujmo Turingov stroj M z dvema trakovoma. Prvi trak je namenjen simulaciji Turin- govega stroja M_L, drugi pa M_L. Turingov stroj M, ki je prikazan na sliki 4.2, deluje na naslednji naˇcin:

1. ”paralelno” procesira vhodno besedow naM_L in M_L (paralelno procesiranje pomeni, da Turingov stroj M sekvenˇcno izmeniˇcno simulira procesiranje M_L in M_L na vhodni besedi w);

2. ˇceM_L sprejme vhodno besedo, vrni sprejeto; ˇce M_L sprejme w, vrni zavrnjeno.

Slika 4.2: Turingov stroj M.

Pokaˇzimo, da je jezik L odloˇcljiv. Vsaka vhodna beseda w ∈ Σ∗ je vsebovana bodisi v L bodisi v L, kar pomeni, da jo razpozna bodisi M_L bodisi M_L. Ker se Turingov stroj M ne glede na vhodno besedo vedno ustavi in sprejme jezik L, je jezik Lodloˇcljiv.

Predno preidemo na opis jezika, ki je Turingovo razpoznaven, pa ni odloˇcljiv, si oglejmo koncept univerzalnega Turingovega stroja.

Univerzalni Turingov stroj U je Turingov stroj z enim trakom nad abecedo Σ = {1} in traˇcno abecedo Γ = Σ∪ {[}, ki kot vhodni podatek dobi dva parametra in zmore simulirati poljuben Turingov stroj na poljubni vhodni besedi. Zaradi enostavnosti obravnave bomo namesto stroja U uporabili ekvivalenten Turingov stroj MU, ki pa ima tri trakove. Na prvi trak Turingov strojM_U dobi celotni vhodni podatek, iz katerega dekodira opis Turingovega stroja, ki ga bo simuliral. Nato je na drugem traku zapisana vhodna beseda za simulirani Turingov stroj. Tretji trak pa je namenjen procesiranju. Spomnimo se, da Mi in wi zapo- redoma oznaˇcujeta i-ti Turingov stroj glede na G¨odelovo ˇsteviˇcenje oziroma i-to besedo nad dano abecedo Σ glede na leksikografsko ureditev.

Naj n oznaˇcuje besedo zn enicami, torej

n = 11· · ·1

| {z }

n

.

Turingov stroj M_U iz vhodne besede m[n dekodira opis Turingovega stroja M_m in vhodno besedo w_n za Turingov stroj M_m. Drugi deln prepiˇse na drugi trak, tretji trak pa je name- njen simuliranju procesiranja stroja M_m. Stroj M_U sekvenˇcno bere transformirano vhodno besedo n na drugem traku in simulira delovanjeM_m v skladu z zakodirano funkcijo prehoda med stanji stroja M_m, ki jo razbere iz kodem na prvem traku. Sprememba stanja se zapiˇse na tretji trak.

Izrek 12 pove, da obstajajo jeziki, ki so Turingovo razpoznavni, vendar neodloˇcljivi.

Izrek 12 Komplement L_D ={w_i | w_i ∈L(M_i)} diagonalnega jezika je Turingovo razpozna- ven, vendar neodloˇcljiv.

Dokaz: Naj bo L_D = {w_i | w_i ∈/ L(M_i)} diagonalni jezik iz izreka 9. Pokaˇzimo, da je njegov komplement L_D Turingovo razpoznaven. Natanˇcneje, pokaˇzimo, da univerzalni Tu- ringov stroj sprejme jezik LD ={wi | wi ∈L(Mi)}.

Naj bo w_i ∈ L_D. Turingov stroj M_U iz vhodnega podatka i[i dekodira opis delovanja M_i in nato simulira njegovo delovanje na vhodni besedi wi. Ker je wi ∈ L(Mi), se simuliranje ustavi v stanjuq_sprejmi, v skladu z delovanjem Turingovega strojaM_i. Zato jeL_D Turingovo razpoznaven.

Ce bi bilˇ L_D odloˇcljiv, bi bil po izreku 10 tudi L_D odloˇcljiv. Po izreku 9 jezik L_D ni niti Turingovo razpoznaven! Protislovje dokazuje, da je L_D Turingovo razpoznaven, vendar ni odloˇcljiv.

V naslednjem poglavju bomo s pomoˇcjo odloˇcljivih jezikov preˇsli na odloˇcljive probleme.

Poglavje 5

Odloˇ cljivost in neodloˇ cljivost problemov

V prejˇsnjem poglavju smo pokazali, da obstajajo jeziki, ki so Turingovo razpoznavni, vendar neodloˇcljivi. Posvetimo se znamenitemu konceptu odloˇcljivih oziroma neodloˇcljivih proble- mov. Predmet obravnave bodo tako imenovani odloˇcljivostni problemi, to so problemi, na katere lahko odgovorimo bodisi z da bodisi z ne. V celotnem poglavju sledimo literaturi [1, 3, 4, 12].

Problem je sploˇsno vpraˇsanje, ki se nanaˇsa na vse mogoˇce konkretne primere; recimo, ali je poljubna gramatika dvoumna. Konkretna instanca tega problema pa je vpraˇsanje, ali jedana kontekstno odvisna gramatika dvoumna. Vsako konkretno vpraˇsanje iz danega sploˇsnega problema lahko zakodiramo kot besedo nad abecedo Σ. Sploˇsni problem torej ustreza ne- kemu jeziku nad abecedo Σ. Temu jeziku reˇcemo korespodenˇcni jezik problema.

Ce je korespodenˇˇ cni jezik odloˇcljiv, potem reˇcemo, da je problem odloˇcljiv; drugaˇce pa je neodloˇcljiv. Z drugimi besedami: problem je algoritmiˇcno reˇsljiv, ˇce je korespodenˇcni jezik problema algoritmiˇcno razpoznaven, to je Turingovo odloˇcljiv.

5.1 Problem zaustavitve Turingovega stroja

Posvetimo se najprej temeljnemu neodloˇcljivemu problemu, ki se nanaˇsa na Turingove stroje same,problemu zaustavitve Turingovega stroja. Zanima nas, ali je za vsak Turingov stroj nad dano abecedo Σ in poljubni vhodni podatek moˇzno algoritmiˇcno ugotoviti, ˇce se ta Turingov stroj ustavi. Zanima nas torej, ali obstaja algoritem (Turingov stroj, ki se vedno ustavi), ki razpozna korespodenˇcni jezik tega problema.

Preden nadaljujemo, vpeljimo pojem Turingovo izraˇcunljive funkcije. Funkcija f: N → N je Turingovo izraˇcunljiva, ˇce jo je mogoˇce v konˇcnem ˇstevilu korakov izraˇcunati na kakem Turingovem strojuM nad abecedo{1}, oziroma pri vhodni besedin, ki predstavlja vrednost n, se M ustavi in vrne vrednost f(n), ki predstavlja vrednost f(n). Podobno definiramo Turingovo izraˇcunljive funkcije veˇcih spremenljivk.

Izrek 13 Problem zaustavitve Turingovega stroja je neodloˇcljiv.

Dokaz: Predpostavimo, da nad abecedo Σ obstaja tak Turingov stroj H, ki zmore al- goritmiˇcno preveriti, ali se vsak Turingov stroj M = M_m, m = gn(M), na poljubni dani

vhodni besedi w ∈ Σ^∗, w = wi, i = ln(w), ustavi ali ne. Tak Turingov stroj H bomo simulirali z univerzalnim Turingovim strojemH_U, ki izraˇcuna funkcijoh: N× N→N, dano s predpisom

h(m, n) =

(1; ˇce se Turingov stroj M_m ustavi na vhodni besedi w_n, 2; v vseh drugih primerih.

To pomeni, da univerzalni Turingov stroj HU dobi kot vhodni podatek m[n, na koncu pa na traku ostane 1, ˇce se Turingov stroj M_m ustavi na vhodni besedi w_n in 2 v vseh drugih primerih. Obstoj takega Turingovega stroja pomeni natanko to, da je problem zaustavitve Turingovega stroja algoritmiˇcno reˇsljiv.

Konstruirajmo ˇse dva Turingova stroja D inF.

• Turingov stroj D nad abecedo Σ = {1} pri vhodni besedi j kot rezultat procesiranja vrne (podvojeno) besedo j[j, zapisano na traku Turingovega stroja. Ena od moˇznih realizacij takˇsnega Turingovega stroja D je prikazana na sliki 5.1.

Slika 5.1: Primer realizacije Turingovega stroja D.

• Turingov stroj F nad abecedo Σ ={1} pa deluje takole:

– pri vhodni besedi 1, se ne ustavi;

– pri vhodni besedi 2, se ustavi (ustavi se tudi pri vhodni besedin za n >2).

Tak Turingov stroj F je predstavljen na sliki 5.2.

Slika 5.2: Primer realizacije Turingovega stroja F.

Slika 5.3: Turingov stroj P.

Iz Turingovih strojev H_U, D inF sedaj lahko sestavimo Turingov strojP, ki je prikazan na sliki 5.3.

Kako torej deluje Turingov stroj P? Pri vhodni besedi j Turingov stroj D naprej podvoji vhodno besedo in pripravi vhodno besedo j[j za Turingov stroj H_U. Glede na dani rezultat stroja H_U se nato Turingov stroj F bodisi ustavi bodisi ne, Turingov stroj P pa se tudi bodisi ne ustavi bodisi ustavi.

Ce povzamemo, Turingov strojˇ P pri vhodni besedi j deluje na naslednji naˇcin:

• ˇce je H_U vrnil rezultat 1, se strojP ne ustavi;

• ˇce je H_U vrnil rezultat 2, se strojP ustavi.

Ker je P Turingov stroj, ga lahko zakodiramo in oˇstevilˇcimo. Naj bo P = M_p, torej je njegova koda gn(P) = p. ˇCe Turingov stroj P poˇzenemo pri vhodni besedi p, imamo dva moˇzna izida:

• Ce jeˇ h(p, p) = 1, se po definciji Turingov stroj P na vhodni besedi wp ustavi. To pomeni, da je H_U vrnil rezultat 1. Vendar se zaradi delovanja stroja F Turingov stroj P ne ustavi. Protislovje.

• Ce jeˇ h(p, p) = 2, se Turingov stroj P na vhodni besediwp ne ustavi (ali pa ”zmrzne”).

To pomeni, da je H_U vrnil rezultat 2. Vendar se zaradi delovanja strojaF stroj P na vhodni besedi w_p zagotovo ustavi. Protislovje.

Turingov stroj P je oˇcitno protisloven, zato ne obstaja. Ker obstajata Turingova stroja D in F, stroj P obstaja natanko tedaj, ko obstaja stroj H_U. Ker stroj P ne obstaja, ne obstaja nitiH_U. To pomeni, da ne obstaja tak Turingov stroj, ki bi ugotovil, ali se poljuben Turingov stroj pri poljubni vhodni besedi ustavi ali ne.

V nadaljevanju si bomo ogledali zanimiv neodloˇcljiv problem, imenovan Postov korespo- denˇcni problem.

Poglavje 6

Postov korespondenˇ cni problem

Pomemben naraven matematiˇcni problem je Postov korespodenˇcni problem, ki je povezan z manipulacijo besed nad dano abecedo. Ta problem je prvi opisal Emil L. Post leta 1946 in pokazal, da je neodloˇcljiv [13]. Ta problem zaposluje zadnjih 60 let veliko raziskoval- cev. Z razliˇcnimi metodami in strategijami iˇsˇcejo reˇsitve za konkretne primere Postovega korespodenˇcnega problema, kljub temu, da je ta problem v sploˇsnem neodloˇcljiv. Postov ko- respondenˇcni problem najdemo v veliko uˇcbenikih kot uvodni zgled neodloˇcljivega problema.

V tem poglavju se opiramo na literaturo [2, 3, 5, 13].

Postov korespodenˇcni problem: Za poljubno dana seznama x= [x₁, x₂, x₃, . . . , x_n] in y= [y₁, y₂, y₃, . . . , y_n]

besed nad neko abecedo poiˇsˇci tako zaporedje indeksov i₁, i₂, . . . , i_k za neki k ∈ N, da bo beseda x_i1x_i2. . . x_ik enaka besedi y_i1y_i2. . . y_ik.

Formulirajmo ta problem ˇse drugaˇce: dana je mnoˇzica sklopov M_{P KP} =

( x₁ y₁

, x₂

y₂

, . . . , x_n

y_n )

kjer vsak sklop sestavljata zgornja in spodnja beseda. Poiskati je potrebno tako zaporedje sklopov, da je celotna zgornja beseda enaka spodnji besedi. Reˇsitev je vsako zaporedje s to lastnostjo; tako zaporedje oznaˇcimo z hM_{P KP}i. Postov korespondenˇcni problem torej na kratko zapiˇsemo

P KP ={hM_{P KP}i | M_{P KP}}.

Oglejmo si dva konkretna zgleda.

Zgled 5.

Imamo dano mnoˇzico sklopov { ₁

111

, ₁₀₁₁₁

10

,₁₀

0

}. V tem konkretnem primeru je reˇsitev Postovega korespodenˇcnega problema podana z zaporedjem sklopov

10111 10

1 111

1 111

10 0

,

saj je zgornja beseda 101111110 enaka spodnji besedi. 4

Zgled 6.

Imamo dano mnoˇzico sklopov {₁₀

101

, ₀₁₁

11

,₁₀₁

011

}. Najprej moramo doloˇciti zaˇcetni sklop zaporedja. Sklopa₀₁₁

11

in₁₀₁

011

ne ustrezata, saj se razlikujeta ˇze v prvem simbolu. V naˇsem primeru se iskana reˇsitev zaˇcne le s sklopom₁₀

101

.

V naslednjem koraku imamo tri moˇzne izbire, ki tvorijo naslednje zgornje in spodnje besede:

1010

101101,¹⁰⁰¹¹₁₀₁₁₁ in ₁₀₁₀₁₁¹⁰¹⁰¹. Lahko vidimo, da ustreza le tretja moˇznost, ki tvori besedi ₁₀₁₀₁₁¹⁰¹⁰¹ in je sestavljena iz zaporedja sklopov₁₀

101 101 011

. Prva moˇznost se razlikuje v ˇcetrtem simbolu, druga moˇznost pa v tretjem simbolu. Potrebno je poudariti, da se po trenutni izbiri zaporedja sklopov zgornja in spodnja beseda razlikujeta po dolˇzini – zgornja beseda je za en simbol krajˇsa kot spodnja.

Ponovno imamo tri moˇzne izbire sklopov: _101011101^1010110 , ^10101011_10101111 in _101011011^10101101. Ustrezna je zadnja moˇznost, ki je sestavljena iz sklopov₁₀

101 101 011

101 011

.

Pri naslednjem in nadaljnih korakih bi ponovno izbrali sklop₁₀₁

011

, druge moˇznosti ne pridejo v poˇstev. To pomeni, da je za dano mnoˇzico domnevna reˇsitev zaporedje sklopov

10 101

101 011

101 011

101 011

101 011

. . .

Kot lahko vidimo, domnevna reˇsitev ni ustrezna, saj se besedi razlikujeta po ˇstevilu znakov.

Za dano mnoˇzico {₁₀

101

,₀₁₁

11

,₁₀₁

011

} torej reˇsitev ne obstaja. 4

Definirajmo ˇse tako imenovani omejeni Postov korespodenˇcni problem.

Omejeni Postov korespodenˇcni problem: To je Postov korespondenˇcni problem, kjer se vsaka reˇsitev zaˇcne s prvim sklopom h

x1

y1

i

. Mnoˇzico sklopov, kjer ˇze s samim zapisom nakaˇzemo, da iˇsˇcemo le take reˇsitve, oznaˇcimo z

M_{P KP}⁰ = (

x1

y₁

; x2

y₂

, . . . , xk

y_k )

.

S simbolom ”; ” ustrezno oznaˇcimo zaˇcetni sklop iskane reˇsitve. Omejeni Postov korespo- denˇcni problem na kratko zapiˇsemo

P KP⁰ ={hM_{P KP}⁰ i |M_{P KP}⁰ }.

V dokazu, da je Postov korespodenˇcni problem neodloˇcljiv, bomo potrebovali naslednji lemi.

Lema 1 Ce obstaja algoritem za Postov korespodenˇˇ cni problem, potem obstaja tudi algoritem za omejeni Postov korespodenˇcni problem.

Dokaz: Pokazati moramo, da lahko poljubnemu omejenemu Postovemu korespodenˇcnemu problemu priredimo tak Postov korespodenˇcni problem, da ima ta prirejeni Postov korespo- denˇcni problem reˇsitev natanko takrat, ko ima reˇsitev tudi omejeni Postov korespodenˇcni problem. To naredimo takole.

Naj bo M_{P KP}⁰ =n h

x1

y1

i

;h

x2

y2

i

, . . . ,h

xk

yk

i o

mnoˇzica sklopov za omejeni Postov korespodenˇcni problem. Definirajmo mnoˇzico sklopov za prirejeni Postov korespodenˇcni problem

M_{P KP} = (

x₁

y1

,

x₂ y2

, . . . , x_k

yk

,

)

. Dodani sklop

je v reˇsitvi vedno zadnji sklop, saj z njim uravnamo ˇstevilo znakov . Tu gre res za sploˇsni Postov korespondenˇcni problem, saj se ne zahteva, da naj se iskana reˇsitev zaˇcne z zaˇcetnim oziroma prvim sklopom. Lahko pa uvidimo, da se reˇsitev za mnoˇzico sklo- pov M_{P KP} zagotovo zaˇcne s prvim sklopom, torej h

x1

y1

i

, saj je to edini sklop, pri katerem se prvi ˇcrki zgornje in spodnje besede ne razlikujeta.

Naj bo h

xi1

yi1

i hxi2

yi2

i . . .h

x_il yil

i

reˇsitev za omejeni Postov korespodenˇcni problem. Potem je xi1

y_i1

xi2

y_i2

. . . xil

y_il

reˇsitev za prirejeni Postov korespodenˇcni problem, saj iz lastnosti x_i1x_i2. . . x_il =y_i1y_i2. . . y_il sledi

xi1xi2. . .xil=yi1yi2. . .yil.

Obratno je tudi oˇcitno res: pri iskanju reˇsitve za prirejeni Postov korespodenˇcni problem ne zahtevamo, da se zaporedje sklopov zaˇcne s prvim sklopom; vendar pa, kot smo ˇze omenili, se vsaka reˇsitev mora zaˇceti s prvim sklopom – kar pa je natanko omejeni Postov korespo- denˇcni problem.

S tem smo pokazali pretvorbo omejenega Postovega korespodenˇcnega problema na Postov korespodenˇcni problem.

Lema 2 Za vsak Turingov stroj M in vsako vhodno besedo w obstaja tak omejeni Postov korespondenˇcni problem P KP⁰(M, w), da velja naslednje: w ∈ L(M) natanko takrat, ko obstaja reˇsitev za P KP⁰(M, w).

Dokaz: Prirejeni omejeni Postov korespodenˇcni problemP KP⁰(M, w) konstruiramo preko zaporedja trenutnih opisov procesiranja Turingovega stroja M pri vhodni besedi w. Vsak sklop iz M_{P KP}⁰ (M, w) je sestavljen tako, da zgornja beseda predstavlja trenutni opis stroja M, spodnja beseda pa naslednji trenutni opis procesiranja. V reˇsitvi nam zgornje in spodnje zaporedje besed opiˇse delovanje Turingovega stroja M pri procesiranju vhodne besedew.

Naj bo M = (Q,Σ,Γ, δ, q₀, q_sprejmi, q_zavrni) poljubno dani Turingov stroj. Konstruirajmo konkreteno reˇsitev hM_{P KP}⁰ (M, w)i prirejenega problema P KP⁰(M, w) z lastnostjo, da ima le-ta reˇsitev, ˇce in samo ˇce Turingov stroj M sprejme vhodno besedo w = w₁w₂w₃. . . w_n. Sklopi za omejeni Postov korespodenˇcni problem, ki so lokalni opisi trenutnega procesiranja Turingovega stroja M, so naslednji (zaradi enostavnosti uporabimo krajˇso oznakoM_{P KP}⁰ = M_{P KP}⁰ (M, w)):

1.

hx1

y1

i

=

h #

#q0w1w2w3...wn

i

∈M_{P KP}⁰ ; 2. _qa

br

∈M_{P KP}⁰ zaa, b∈Γ in q, r ∈Q, kjer je q6=q_zavrni inδ(q, a) = (r, b, R);

3. _cqa

rcb

∈M_{P KP}⁰ zaa, b, c∈Γ in q, r ∈Q, kjer je q6=q_zavrni inδ(q, a) = (r, b, L);

4. _a

a

∈M_{P KP}⁰ zaa ∈Γ;

5. h

#

#

i∈M_{P KP}⁰ inh

# [#

i∈M_{P KP}⁰ ;

6. h_{a q}

sprejmi

qsprejmi

i∈M_{P KP}⁰ inh_q

sprejmi a qsprejmi

i ∈M_{P KP}⁰ za a∈Γ;

7. h_q

sprejmi##

#

i ∈M_{P KP}⁰ .

Denimo, da je w ∈ L(M). Potem obstaja konˇcno zaporedje trenutnih opisov procesiranja Turingovega stroja M

#q₀w₁w₂w_n#. . . .#q_sprejmi#.

Pokaˇzimo, da lahko to zaporedje razdelamo na zaporedje zaporednih parov(trenutno stanje, naslednje stanje), pri ˇcemer je prvi par(#, zaˇcetno stanje). Za vsak tak par na naraven naˇcin priredimo sklop, ki ima eno izmed sedmih zgoraj naˇstetih oblik. Tako definirano zaporedje sklopov je natanko reˇsitev omejenega Postovega korespodenˇcnega problemaP KP⁰(M, w).

Obratno, ˇce tako zaporedje sklopov obstaja, potem zaporedje zgornjih besed predstavlja legitimno zaporedje trenutnih opisov procesiranja Turingovega stroja – od zaˇcetnega do konˇcnega stanja, ko M sprejme w.