Turingovi strojevi i Halting problem

o: > Teoremcic: _Ne postoji_ algoritam H koji uzima kao parametar
o: > algoritam X , i na outputu uvijek daje boolean koji opisuje
o: > ima li X beskonacnu petlju ili nema...
o: >
o: > FER-varijanta:-) : Zadatak
o: > "Napisi u Cu funkciju
o: > int has_inf_loop(char* x);
o: > - kojoj je parametar string x koji predstavlja (sintakticki
o: > ispravan) komad koda u Cu, a output je 1 ako bi izvrsavanje
o: > koda x upalo u beskonacnu petlju, a 0 ako bi to izvrsavanje
o: > zavrsilo nakon konacno mnogo koraka."
o: > je toliko _bolesno_ tezak da ga se uopce ne isplati rjesavati...
o: > u idealnom smislu je nerjesiv... ako vas netko (bez sumnje
o: > matematicar:) pita da dokazete da je nerjesiv, samo recite:
o: > "trivijalno se svodi na Halting problem..." - s vjerojatnoscu
o: > 99% ce vas prestati gnjaviti (cesta nuspojava: prestat ce
o: > pricati s vama uopce...) ...
o: > (NVHF, FERovci i FERovce...:) :-)

[lesson no=11]
Dakle, za pocetak treba istaknuti jednu stvar, koju, kako
sam primijetio, information generation jako tesko prihvaca:
_kompjuteri ne postoje oduvijek_. ok:-? Zapravo, u nekom 
koliko-toliko korisnom smislu, postoje tek zadnjih 30ak godina.
Kako su ljudi racunali komplicirane stvari prije toga:-?
Uglavnom na razne nacine kojih nas se danas strah i prisjecati...:-)
No mathematicari su, kao i obicno, bili ispred svog vremena...:-)

Zanimljivo je da je pojam algoritma postojao puno prije pojma
racunala... za pricu o Al-Khawarizmiju (il kak se vec pise u latinskoj
transkripciji:) valjda znas...(:-?)
Algoritam je (u krajnje intutivnom smislu, kao uostalom i svi 
math-pojmovi u to doba:) bio jednostavno niz pravila, najcesce u 
prirodnom jeziku, s eventualno nekim skracenicama za cesto koristene
fraze (kao npr. "RDTV":)), koji je sluzio da se rijesi neki problem.
Za problem se smatralo da je rijesen ako je dan eksplicitni algoritam
za njegovo opcenito rjesavanje. Tako npr. u svojoj prvoj knjizi 
"Elemenata" Euklid navodi "algoritam za dijeljenje duzine na pola".
Time je on rijesio problem raspolavljanja duljine, jer je njegov
algoritam zaista mogao raspoloviti svaku duzinu.

E, sad na scenu stupa jedan jako vazan princip u matematici,
koji se u Veky's_Math_Presentation-stilu moze izreci npr. ovako:
"Covjek se uglavnom ne pita za striktnu definiciju nekog pojma
dok god mu je s tim pojmom intuitivno sve u skladu s intuicijom."
Da bi nesto nasla (X), uglavnom ti treba manje precizna definicija
Xa, nego da bi dokazala da X ne postoji. To je uglavnom posljedica 
toga da su mathematicari nepopravljivo optimisticna bica:-), ali
o tome jednom drugom prilikom... ima nesto i dolje.:-)

To se dogodilo i s algoritmima. Jednostavno, kroz povijest se
iskristaliziralo nekoliko "algoritamskih" problema koji se nikako
nisu mogli rijesiti... vjerojatno su najpoznatija 3 iz konstrukcija:
trisekcija kuta, kvadratura kruga i duplikacija kocke (cula?). 
Jednostavno, nakon ~e3 godina ljudima je polagano pocelo ici na
zivce to sto nesto ne znaju rijesiti, pa su poceli traziti gdje je
kvaka (nesto vrlo blizu onome tvom dolje, sto pocinje s
"a mozda je to slucajno tako", a zavrsava s "a mozda su u sumi":)).
Netko originalan poput ofce se jednom pitao "ok, mozda algoritma za
takvo nesto jednostavno nema:-?" Zaista, tko kaze da se svi problemi
moraju moci algoritamski rijesiti:-? Jedino nepopravljivi 
math-optimizam:-)... No mathematicari (za razliku od ostalih 
optimista:) svom optimizmu ne vjeruju slijepo (bar kad mogu:), vec
traze dokaze. Dakle, dokazi ti nama da algoritam ne postoji...

"Hm... a kak da to dokazem? Jedino sto mi pada na pamet je metoda
kontradikcije... ono, pretpostavim da algoritma ima, pa vucem neke 
zakljucke i na kraju dodem do neceg sto je toliko blesavo da mi je
teze povjerovati u to nego da algoritma nema... ;-)
((ovo gore treba uzeti cum grano salis, /da ne pomislis kako je
metoda kontradikcije stvar vjere:/, ali ideja je ta))
No da, a kak da vucem zakljucke kad nemam neki konkretan algoritam?
Imam samo fiktivnu tvorevinu za koju znam sto bi trebala raditi:
trisecirati proizvoljni kut ravnalom i sestarom (npr.). No niti znam
kako ona izgleda, niti joj znam strukturu, ne znam zapravo nista iz 
cega bih mogao vuci neke zakljucke. Aaaa! Ja, iako sam vidio ~e3
algoritama u zivotu, jos uvijek zapravo ne znam sto je
algoritam opcenito! :-/"

I u tom trenutku covjek obicno shvati da mu treba prava, mathematicki
stroga definicija pojma "algoritam", ciji su svi dosad zapisani 
algoritmi samo specijalni slucajevi... I onda se covjek baci na to, i
nakon 5~30 minuta (ovisno o inteligenciji/lijenosti:) shvati da radi
Sizifov posao. Ljudi pisu algoritme vec tisucama godina, i to na
_jako_ razlicite nacine. Jedina suvisla definicija pod koju se sve
to skupa da podtrpati je "niz simbola", no to ocito (preslaba rijec:)
nije dovoljno ekskluzivno. Idemo drugim putom: naci matematicku
definiciju
u kojoj ce se moci napisati par osnovnih akcija, i koja ce biti 
dovoljno otvorena prema prosirenjima da ce se u njoj moci iz 
jednostavnih akcija graditi slozenije, dok na kraju ne shvatimo da,
iako bi eksplicitno prevodenje svih dosad zapisanih algoritama pod
tu novu definiciju i dalje bilo Sizifov posao, ono nam i ne treba;
na neki nacin, ponovo cemo izgraditi sve sto nam treba.

Ok. Sad je glavno pitanje kako izabrati osnovne akcije, i kako
smisliti pravila za gradnju novih iz vec dobivenih. Prvi 
(i vjerojatno ne bas najspretniji:-/, ali cesto mu se daje prednost
upravo zato sto je prvi) uspjeli takav pokusaj bio je onaj Alana
Turinga (cula za njega? Ma zapravo nije bitno...:), koji je bio
izraden u formi specifikacije nekog zamisljenog stroja... nesto
poput GIMa:-), samo dosta opcenitije...
(Mnoge stvari ovdje ce ti se ciniti kao da ih je radio 10ogodisnjak,
a ne jedan od vodecih svjetskih logicara tog doba:-), ali uzmi u
obzir 1) da je to oilo 20 godina prije nego sto je zazujao prvi 
ENIAC:-), i 2) da je to upravo omogucilo da prvi ENIAC nesto 
"korisno" radi kad je zazujao 20 godina kasnije:))...

Dakle, Turingov stroj ima "glavu" i ima "traku". Traka je beskonacna
u oba smjera, s diskretno rasporedenim celijama, numeriranim
cijelim brojevima, nesto ovakvo (fixedwidth font, please:) :
   -+-+-+-+-+-+-+-+-
....| | |o|v|c|a| |....
   -+-+-+-+-+-+-+-+-
    -2-1 0 1 2 3 4
Na svakoj celiji trake moze u odredenom trenutku biti zapisan 
tocno jedan znak (TS moze pisati po traci, ali tako da svaki znak
koji se zapisuje u nekom trenutku u neku celiju brise onaj koji je 
tamo bio u prethodnom trenutku). Postoji jedan poseban znak, 
Space (razmak), kojim je
u pocetku popunjena skoro cijela traka (dakle, samo u konacno
mnogo celija zapisano je nesto osim Spacea). (Pisanje Spacea u neku
celiju od strane TSa znaci jednostavno brisanje te celije.)
Skup simbola koji se mogu zapisati na traku (tzv. abeceda stroja)
je konacan i specificiran unaprijed (TS ne moze u toku rada 
izmisljati nove simbole).

Toliko o traci (samoj). "Glava" TSa u svakom trenutku nalazi se
nad nekom celijom na traci i kazemo da "cita" znak koji je zapisan
u toj celiji. Glava se u pocetku nalazi na celiji 
oznacenoj s 0 (dakle, na gornjoj traci, cita znak "o").
Glava sa sobom vuce i tzv. "stanje" i tzv. "program".
Stanje je apstraktni pojam i sluzi tome da glava pomocu njega
zapamti neke informacije koje prenosi na drugi dio trake. 
U odredenom trenutku glava moze (i mora) biti u tocno jednom
stanju. Postoji jedno posebno stanje, Start, u kojem se glava
nalazi na pocetku. 
Skup stanja u kojima se glava moze nalaziti je konacan i 
specificiran unaprijed (TS ne moze u toku rada izmisljati nova
stanja).

Dosad je TS samo staticka tvorevina. Program je ono sto mu
"udahnjuje dusu". Program je funkcija koja svakoj kombinaciji 
stanja (q1) i znaka koji moze biti procitan s trake (x1)
(sad ti je jasno zasto moraju biti specificirani unaprijed:)
pridruzuje 3 stvari: novi znak (x2),
novo stanje (q2) i tzv. "akciju". Akcija je jedno od 3 slova:
L (pomakni glavu za jednu celiju lijevo), R (pomakni glavu za
jednu celiju desno) ili S (zaustavi stroj).
Gornje pridruzivanje se interpretira na nacin:
"Ako se glava nalazi u stanju q1 i s trake cita znak x1 ,
do sljedeceg trenutka glava mora: zapisati x2 u celiju gdje
je bila (brisuci time x1), prijeci u stanje q2 i uciniti akciju.
npr. ako program gornjeg TSa kombinaciji (Start,"o") pridruzuje
("o",q1,R), a kombinaciji (q1,"v") pridruzuje ("f",q2,S), pogodi
kako ce traka izgledati na kraju... :-).
E sad, treba puno pisati da se covjek uvjeri da TS, ispravno
programiran, zaista moze "sve", ie, moze izvrsiti bilo sto sto
mi smatramo algoritmom, u smislu da preko trake u pocetku
pokupi input, a po zavrsetku rada (kad izvrsi akciju S)
nam na traci stoji output... ali moze se. Naravno, sve ovisi o
tome koliko je netko "picky" u definiciji algortima, ali mislim
da ti je dovoljno sljedece:

Uzmimo za abecedu skup svih ASCII znakova, zajedno s jos dva znaka,
Space i Eof (naravno, to _nisu_ ASCII znakovi 32 i 4 , vec se samo
tako zovu u nedostatku boljih imena - kad je ASCII vec pokupio
sve zanimljive znakove...:). Tada za _svaki_ C (ili Pascal, if you
really like it:) program koji je pisan kao filefilter (cita input iz
datoteke npr. "in.txt" i pise output u datoteku "out.txt")
_postoji_ TS s gore specificiranom abecedom, takav da, ako ga 
startamo na traci na kojoj pocevsi od celije 0 zapisana datoteka
"in.txt" nakon koje je znak Eof, on staje akko staje pripadni C
program, i u tom slucaju na traci se na kraju nalazi 
datoteka "out.txt", byte per byte identicna onome sto je C program
proizveo, s Eofom na kraju. 

Tko bi to rekao, uzevsi u obzir jednostavnost akcija koje TS moze
izvoditi:-? Naravno, ono sto stoji na strani TSa je da ga nije
briga za kompleksnost, kako programa, tako i samog izvrsavanja -
ne bih se zacudio da minimalni TS za sortiranje datoteke ima
npr. e4 stanja, i da radi prakticki neusporedivo sporije od 
pripadnog C programa, mozda cak i u nad-eksponencijalnom vremenu...
(kuzis sto pricam:-?)
ali za to nas nije briga ako nas zanima opcenita teorija kojom
cemo dokazati da za nesto _ne postoji_ algoritam...
Got it:-? Ako za nesto ne postoji TS, tada znamo da se to ne moze 
napisati ni u kojem programskom jeziku, pa niti u bilo kojoj
drugoj formalizaciji algoritma od onih (a ima ih puno:) koje su
napravljene od Turinga naovamo. I to je najpametniji moguci odgovor
na pitanja tipa "postoji li algoritam za...", u slucaju da je
odgovor negativan.

Naravno, sad treba vidjeti da smo to zaista radili s nekom svrhom,
tj. da postoje razumno definirani problemi za koje TS ne postoji.
Takvi postoje (naravno:), i jedan od njih, 
vrlo popularan, je Halting Problem. On se odnosi na to da se za 
dani TS i dani input algoritamski odredi staje li taj TS s tim 
inputom ili ne.
(primjecujes slicnost s "algoritmom" H iz gornjeg Teorema:-?)

Do toga (dokaza da je algoritamski Halting Problem nerjesiv)
ima jako puno tehnickih stvari, no probajmo ih zaobici
i pricati samo ideje:
Prvo se pokaze da je dovoljno od TSa traziti da ima samo 3 znaka
u abecedi, recimo 0, 1 i Space, s tim da se Space koristi samo za
ona dva beskonacna "repa" na traci... To se napravi npr. kodirajuci
znakove abecede prirodnim brojevima, i prikazujuci prirodne brojeve
kao nizove jedinica, razdvojene nulama (npr. ako je abeceda gore
a c f o v , gornje stanje na traci bi se moglo kodirati s
....SpaceSpace01111011111011010SpaceSpace.... ok:-?)
Onda se pokaze da postoji tzv. univerzalna specifikacija TSa,
sto bi znacilo nacin da se samo pomocu 0 i 1 kodira program bilo kojeg
TSa sa abecedom 0 1 Space ... relativno jednostavno
(iako prilicno painful za raspisivanje:), naprave se
escape-patterni nula i jedinica koji znace "stanje", "akcija", 
"pridruzi" itd..., i onda se program vise-manje prevodi rijec po 
rijec...
Sad vec mozda pogadas sto je sljedeci korak: UTS, Univerzalni 
Turingov Stroj, koji na traci ima 2 stvari (npr. zapisane lijevo i
desno od nulte celije): univerzalnu specifikaciju nekog TSa (T),
i {0,1}-kod nekog inputa (x). UTS s inputom (T,x) staje akko T s
inputom x staje, i u tom slucaju daje isti output na traci.
(UTS za Turingove strojeve je nesto poput C-kompajlera napisanog
u C-u, ili bolje, s obzirom na to da je TS interpreter,
intrepreter BASICa napisan u BASICu... probaj se uvjeriti da se
takvo nesto moze napisati ako covjek ima dovoljno volje...:-)
a uoci i slicnost sa "skr. je skr. za skr."...(:-!) :)
UTS je vrlo kompliciran za napraviti, ali jednom kad njega imamo,
mozemo raditi razne zanimljive stvari... npr. UTSom se Halting 
problem za sve TSove svodi na problem za samo jednoga: 
za koje inpute UTS staje? (jer je u inputu za UTS sadrzana i 
potpuna informacija o tome o kojem se TSu radi... ok?)

Sad da razjasnimo jednu stvar koja ti se mozda mota po glavi(ci:) :
"Pa nije li UTS upravo rjesenje Halting Problema?" _Nije_ - UTS
staje (s nekim inputom) ako pripadni TS staje (s nekim inputom),
i to je ok, ali ako se pripadni TS zaglavi u beskonacnoj petlji,
to ce se isto dogoditi i s UTSom... dakle, UTS je na neki nacin
"polovicno" rjesenje - daje odgovor ako je odgovor "da", ali ako
je odgovor "ne", to nikad necemo saznati (ovo je jako bitno, toliko
da cu riskirati:-) i pitati te: jel jasno:-? :). Za "pravo" rjesenje
HPa htjeli bismo nesto sto staje uvijek, i daje konacan da/ne 
odgovor...

Ok, sad pretpostavimo da je HP rjesiv algoritamski, dakle,
da postoji TS, nazovimo ga HTS, koji prima isti input kao UTS, 
dakle (T,x) (T - neki TS (zapravo, na lijevoj strani trake
stoji njegov kod), x - njegov input),
_uvijek staje_, i na kraju na traci stoji samo 1 ili 0, u ovisnosti
o tome staje li T s inputom x ili ne.

Jos nam treba jedan TS, nazovimo ga CTS (Check TS:),
koji dobiva na inputu niz nula i jedinica (recimo desno od 
0. celije, lijevu stranu ne dira - ovaj detalj je bitan,
vidjet ces poslije zasto:), i vraca 1 ili 0 na nultoj celiji
u ovisnosti o tome predstavlja li taj niz 
univerzalnu specifikaciju nekog TSa (naravno, ne moraju svi 
nizovi biti univerzalne specifikacije nekih meaningful:-) TSova...)
To se dobije lagano kad se univerzalna specifikacija potpuno
raspise, ali buduci da to nismo radili, necemo ni ovo;-)...

Konstruirajmo tada jedan jako cudan TS, nazovimo ga ATS, 
na sljedeci nacin: on na desnoj strani trake dobiva neki 
niz nula i jedinica, (nazovimo ga x) i sto radi? Sljedece korake:
(sekvencijalno izvrsavanje naredbi, kao i if, nisu problem za TS...
naravno:)
1) Prekopira x i slijeva od 0. celije (lako za napraviti)
2) Pozove CTS, da provjeri je li x kod nekog TSa
3) Ako CTS vrati 0 (x nije kod nikakvog TSa), Stop (ATS staje).
   Inace (CTS je vratio 1, dakle x je kod nekog TSa, 
          oznacimo ga s Tx):
4) Brise desnu stranu trake (trivijalno...:)
5) Kopira x slijeva i na desnu stranu trake (zbog onog "bitnog 
   detalja" /CTS ne dira lijevu stranu/ x je ostao netaknut
   na lijevoj strani trake, ok?)
6) Poziva HTS s tako dobivenom trakom... HTS ima istu specifikaciju
   inputa kao i UTS, dakle na lijevoj strani ocekuje kod TSa, dobiva
   x pa ga interpretira kao kod od Tx , dok na desnoj strani ocekuje
   input za Tx , dobiva x . Dakle, taj HTS sad treba provjeriti
   staje li Tx na inputu x ili ne. (smijem pitat jel jasno:-? :)
7) Ako HTS vrati 0 (dakle, Tx _ne bi_ stao na x), Stop. (ATS staje).
   (ovo je korak koji iskoristava "nedozvoljenu" snagu HTSa... ok?)
8) Ako HTS vrati 1 (Tx bi stao na x), ATS se namjerno zapetlja u
   neku trivijalnu beskonacnu petlju (npr. non-stop se prebacuje
   izmedu dva stanja u kojima izvrsava akcije L i R naizmjence,
   neovisno o procitanim znakovima - to je bar lako:)

E sad... jesi jos ziva:-? :-)... ide fun-part:
ATS je TS kao i svaki drugi (ie, bio bi kad bi postojao HTS,
no to je kao fol pretpostavka:),
pa ima svoju univerzalnu specifikaciju - oznacimo je s xa .
U skladu s onim oznakama gore, Txa=ATS ... ok:-?

Pitanje dana:-) glasi: staje li ATS s inputom xa :-?
Naravno... zato i imamo HTS... samo pozovemo HTS sa
inputom (ATS,xa) (dakle, xa i lijevo i desno od trake),
i procitamo rezultat... zar ne:-? Pa... ne bas - gle ovo:

Za pocetak, pretpostavimo da ATS staje na xa - dakle, HTS bi 
gore vratio 1 . No, staje li zaista:-? Pa imamo detaljno opisano
kako radi ATS... prodimo kroz gornjih 8 koraka sa inputom xa :
1) ATS prekopira xa i slijeva i zdesna od 0. celije.
2) ATS pozove CTS s inputom xa... CTS mu vrati 1 (jer xa zaista
   jest neciji kod, namely ATSov:), i ostavi mu xa netaknut na
   lijevoj strani.
3) Nista (jer CTS nije vratio 0).
4) ATS obrise desnu stranu trake.
5) ATS prekopira xa s lijeve strane i na desnu.
6) ATS poziva HTS da otkrije staje li Txa(=ATS) s inputom xa... 
   sto smo ono rekli gore - staje:-? ok... HTS vraca 1 .
7) Nista. (jer HTS nije vratio 0).
8) Jer je HTS vratio 1, ATS se trivijalno zapetlja... naravno:-/.

Hm, izgleda da tom ATSu bas nije stalo:-) do toga da stane
na xa... No dobro, dakle, HTS bi morao vratiti 0 , zar ne:-?.
A sad budi tako dobra i proleti kroz ATS jos jednom i vidi da
ovaj put on uredno stane u 7. koraku... ups. :-))

Dakle, kontradikcija. Do na hrpetinu presutnih pretpostavki
(koje su ok, ali to mi zasad moras vjerovat na rijec:) i
neraspisanih stvari, jedina neutemeljena pretpostavka je bila
ona o postojanju HTSa...
Dakle, HTS ne postoji. It can never exist.
Dakle, ne postoji algoritam za Halting problem...
Dakle, onaj gore Teorem je dokazan.
QED.
Laku noc.
Aaa!
[/lesson]