M ATEMATI KA
Postov problem in Turingov stroj1
nU vU NU
Rok Grecoric, Vesna Iršic, Anja Petkovic, David Gajser (mentor)
-> So problemi v matematiki, tako kot v življenju, ki jih preprosto (še) ne znamo rešiti. So pa problemi, ki jih z nobenim končnim postopkom (t. j. algoritmom) niti ne moremo rešiti. Kaj pomeni, da z algoritmom rešimo problem in kakšen bi bil primer problema, kjer to ni mogoče?
Postov problem
Na voljo imamo domine
ki jih želimo zložiti v vrsto eno za drugo tako, da bomo zgoraj in spodaj dobili enak niz znakov. Pri tem lahko vsako domino uporabimo poljubno mnogokrat, vendar smemo uporabiti le končno mnogo domin.
Ta problem ni preveč težak in ga rešimo, recimo, tako, da dane domine zložimo v vrsto2
00	1	010	1	010	01	00	1	010	1	01	01	01
0	0	1	0	1	0101	0	0	1	0	0101	0101	0101
Enak problem pri danih dominah
100
100
1 Clanek je nastal na poletnem taboru MaRS 2013 (Matematično Raziskovalno Srečanje za srednješolce).
2Obstaja tudi krajša rešitev, ki vsebuje le štiri domine. Jo najdeš?
je mnogo težje rešiti, saj njegovo (najkrajšo) rešitev sestavlja 75 domin, pri čemer obstajata dve različni rešitvi te dolžine.
Problem lahko zastavimo za poljubno število domin:
Postov problem. Danih imamo končno mnogo domin, na zgornjem in spodnjem delu vsake domine pa je zapisan niz znakov. Ali lahko te domine zložimo v končno vrsto eno za drugo tako, da bomo zgoraj in spodaj dobili enak niz znakov? Pri tem lahko vsako domino uporabimo poljubno mnogokrat.
Ta problem je prvi zastavil ameriški matematik Emil Post leta 1946 in je zanimiv med drugim tudi zato, ker se izkaže, da ga ni mogoče rešiti z računalnikom. Ni ga mogoče rešiti z računalnikom?
www.dmfa.si
SLIKA 1.
Avtorji (iz leve): David, Anja, Vesna, Rok.
4
PRESEK 41 (2013/2014) G	4
MATEMATIKA
Zavrnitveno stanje
SLIKA 2.
Grafični prikaz Turingovega stroja M. Iz vsakega stanja, ki ni sprejemno ali zavrnitveno, gredo natanko štiri puščice - za vsak znak iz r ena. Znaki — na puščicah nam nakazujejo, da se glava stroja zmeraj premika v desno. Ko stroj v stanju A prebere znak a, glava na trak napiše a, se premakne v desno, stroj pa preide v stanje, v katerega kaže puščica iz A z znakom a. Če bi imeli tak stroj, da glava znakov na traku ne bi ohranjala, bi morali na vsako puščico dodati še nov znak.
Odločljivi in neodločljivi problemi
Church-Turingova teza
Problemom, na katere lahko odgovorimo samo z da ali ne, pravimo odločitveni problemi. Ker nas zanima predvsem Postov problem, ki je odločitveni, se bomo od tu naprej ukvarjali le s takšnimi problemi. Pravimo, daje odločitveni problem odločljiv, če ga lahko rešimo z algoritmom, t. j. če obstaja algoritem, ki nam pove, kdaj je pravilen odgovor da in kdaj ne.
Poglejmo si preprost primer odločitvenega problema.
Ime: Palindrom
Vhod: Niz ničel in enic
Vprašanje: Ali se niz iz leve proti desni prebere enako kot iz desne proti levi?
Primeri vhodov, za katere je odgovor da, so npr. nizi 110011,100001,101010101 ...
Problem Palindrom znamo rešiti z algoritmom; verjetno je vsak nadobuden braleč že ugotovil, kako. Začnemo lahko npr. s primerjavo skrajnega levega in skrajnega desnega znaka besede. Ce nista enaka, je odgovor ne. Ce pa sta, ju lahko izbrišemo in nadaljujemo na krajši besedi, vse dokler nam ne ostane le še en znak ali pa znakov zmanjka. V obeh primerih je odgovor da.
Torej je Palindrom odločljiv problem. Zanimivo pa je, da obstajajo tudi problemi, ki niso odločljivi. Takšnim pravimo neodločljivi problemi.
Ključno vlogo v definičiji odločljivosti problema ima algoritem. Problem je namreč odločljiv natanko tedaj, ko obstaja algoritem, ki ga reši. Neformalno algoritem razumemo kot končno zaporedje preprostih ukazov, ki jih moramo izvesti, da pridemo do rezultata, npr. računalniki probleme rešujejo z algoritmi. Ali lahko pomen besede algoritem tudi bolj formalno opredelimo?
Matematiki so se na več načinov trudili odgovoriti na to vprašanje, na konču pa se je izkazalo, da je bilo veliko teh načinov povsem enako dobrih. Ena izmed opredelitev pojma algoritem je s pomočjo Tu-ringovega stroja,3 tj. naprave, ki jo bomo podrobneje opisali v naslednjem razdelku.
Churčh-Turingova teza. Problem lahko rešimo z algoritmom natanko tedaj, ko obstaja Turingov stroj, ki reši ta problem.
Churčh-Turingova teza je v rabi od leta 1936 in je v teoretičnem računalništvu splošno sprejeta. Pove nam, da je Turingov stroj enako dober kot katerikoli drug model za algoritem. Ce torej najdemo algoritem za reševanje nekega problema, lahko isti problem rešimo tudi s Turingovim strojem. Zaradi teze
3Preostali dobro poznani opredelitvi algoritma sta s pomočjo lambda računa in s pomočjo rekurzivnih funkčij.

PRESEK 41 (2013/2014) 6
5
MATEMATIKA

se torej ni potrebno spuščati v podrobnosti, ki jih zahteva delo s Turingovim strojem, ampak lahko delamo na višjem nivoju abstrakcije.
Turingov stroj
Leta 1936 je angleški matematik Alan Turing zasnoval Turingov stroj, ki je preprost teoretični model računalnika.4 Sestavljajo ga v eno smer neskončen trak, glava in »program«, ki pove pravila, kako naj se glava premika po traku levo in desno ter ga spreminja. Po vsakem premiku glava prebere znak, zapisan pod njo na traku in ga prepiše z drugim znakom, lahko tudi enakim. Pri tem stroj prehaja preko različnih stanj, dokler ne pride do sprejemnega ali zavr-nitvenega stanja - takrat se ustavi. Lahko pa se zgodi tudi, da stroj nikoli ne pride v eno od teh dveh stanj in se nikdar ne ustavi.
Turingov stroj je natančno določen s:
■	končno množičo stanj Q, v kateri so tudi paroma različna stanja q0, qs in qz, ki jim pravimo začetno, sprejemno in zavrnitveno stanje,
■	končno množičo r, ki vsebuje znake, ki jih Turingov stroj lahko uporabi. Ta množiča vsebuje tudi znake, s katerimi stroju podamo vhod, ter poseben znak, ki nikoli ni del vhoda: prazen znak,
■	prehodno funkčijo (bistvo »programa«) 5 : Qxr — Q x r x {L, D}, kjer L pomeni premik v levo, D pa v desno.
Razložimo pomen prehodne funkčije 5, ki je ključen del Turingovega stroja. Denimo, da je stroj v stanju q in je pod glavo na traku zapisan znak a. Ce je 5(q,a) = (r,b,L), bo stroj izbrisal znak a in na njegovo mesto zapisal b, pri tem bo prešel v stanje r ter se premaknil v levo. Ce bi bila zadnja komponenta D, bi se stroj premaknil v desno. Vhodne podatke, oz. vhod Turingovemu stroju podamo kot niz znakov, ki se nahaja na začetku traku, preostanek traku pa je prazen, t. j. zapolnjen s praznimi znaki. Glava se na začetku nahaja na najbolj levem delu traku, torej na prvem znaku vhoda. Stroj začne
4Izkaže se, da lahko Turingov stroj zaradi neskončnega traku (v teoriji) reši prečej več problemov kot katerikoli računalnik na svetu (ki je seveda končen). Ce pa bi računalnik imel na voljo neskončno trdega diska, bi Turingov stroj rešil natanko tiste probleme kot računalnik.
v začetnem stanju in deluje tako, kot mu predpisuje prehodna funkčija 5. Takoj, ko preide v sprejemno ali zavrnitveno stanje, se ustavi.
Za boljšo predstavo bomo opisali zelo preprost Turingov stroj M, ki preveri, ali je vhod sestavljen le iz znakov 0 in 1 ter se zaključi z znakom X. Naj bo r = {0,1,X, __} množiča znakov, ki jih M lahko uporabi (__ označuje prazen znak). Prehodna funkčija deluje na sledeč način (glej tudi sliko 2):
Ce je stroj v začetnem stanju in glava prebere 0, potem glava zapiše 0, se premakne v desno in stroj ostane v začetnem stanju. Ce je stroj v začetnem stanju in glava prebere 1, potem glava zapiše 1, se premakne v desno in stroj ostane v začetnem stanju. Ce je stroj v začetnem stanju in glava prebere X, potem glava zapiše X, se premakne v desno in stroj preide v stanje q1.
Ce je stroj v stanju q1 in glava prebere prazen znak, stroj sprejme vhod, torej preide v sprejemno stanje.
Ce se zgodi karkoli razen zgornjega (npr. stroj je v začetnem stanju in glava prebere prazen znak), stroj zavrne vhod, torej preide v zavrnitveno stanje.
Izkaže se, da kljub preprosti definičiji Turingo-vega stroja, ne moremo preprosto ugotoviti, na katerih vhodih se Turingov stroj ustavi.
Zaustavitveni problem. Ali se dani Turingov stroj M ustavi na danem nizu iz ničel in enič?
Ta problem je eden najpomembnejših in najbolj znanih neodločljivih problemov. Njegova neodločlji-vost je bila dokazana že v tridesetih letih prejšnjega stoletja, a bomo zaradi poljudnosti članka dokaz izpustili.
Zakljucek
Na začetku smo trdili, da Postovega problema ne moremo rešiti z računalnikom. Kako bi sploh lahko to utemeljili?
Ker lahko s Turingovim strojem rešimo vse, kar lahko rešimo tudi z računalnikom, je dovolj pokazati, da Postovega problema ni moč rešiti s Turingovim strojem. Izkaže se, da bi v primeru, da bi nek
6
PRESEK 41 (2013/2014) 6	6
MATEMATIKA
Turingov stroj rešil Postov problem, lahko skonstruirali algoritem, ki bi rešili tudi zaustavitveni problem, kar pa ni mogoče. Dokaz lahko bralec najde v [1, pogl. 5.2].
Postov problem torej ni odločljiv in tako ni smiselno iskati algoritma, ki bi ga reševal. To pa še ne pomeni, da se s Postovim problemom ni vredno ukvarjati.
Lahko se vprašamo, ali je odgovor Postovega problema pri konkretnih naborih domin da ali ne. Izmed problemov s tremi dominami, kjer je največja dolžina niza znakov na dominah tri, so razrešeni že skoraj vsi primeri. To pomeni, da je za vsak primer znana ustrezna postavitev domin v vrsto, ali pa je dokazano, da taka postavitev ne obstaja. Zadnji odprt primer tega tipa je podan z dominami
Ko boste imeli trenutek prostega Časa, se lahko z njim pozabavate tudi vi.
Literatura
[1]	M. Sipser, Introduction to the Theory of Computation, Second Edition. Course Tehnology, 2006.
[2]	L. Zhao, PCP: a Nice Problem, http: //webdocs. cs.ualberta.ca/~games/PCP/, citirano dne 21. 8. 2013.
_ XXX
Naloga
nU vU NU
Marko Razpet
-> Izračunaj A10, A100 in A1000, ce veš, da je A1 = 4 in
An+1 =
An
1 + n3 An
(n = 1, 2, 3,...).
Bistroumi 2014
srečanje mladih matematikov, fizikov in astronomov
vU SU NU
Bočtjan Kuzman, foto: Jan Šuntajs
-> V letošnjem letu se je tekmovanj iz matematike, fizike, astronomije, razvedrilne matematike in poslovne matematike za različne stopnje osnovne in srednje šole v organizaciji DMFA Slovenije udeležilo več kot 125.000 učencev in dijakov, podeljenih pa je bilo skupaj 819 zlatih priznanj (http:// www. dmfa. si/Aktual no/Statisti ka. html). Med prejemniki zlatih priznanj je bilo 171 nagrajencev skupaj z družinskimi clani, mentorji in predstavniki šol povabljenih na tradicionalno podelitev nagrad, ki je pod naslovom Bistroumi 2014 potekala v soboto, 24. maja, v Linhartovi dvorani Cankarjevega doma v Ljubljani.
SLIKA 1.
Glasbenik in fizik Janez Dovc igra na theremin.
XXX

PRESEK 41 (2013/2014) 6
7