ali.. jel to znaci da moras imat unaprijed specificirane sve moguce kombinacije stanja i znakova?
da.
to je malo naporno, nije li?
hm... vrlo slicna "greska" kao i kod neshvacanja mojih zadataka iz Pascala kao mathematickih zadataka... ie, malo previse "prakticno" gledas na stvari... :-)
TSovi nam ne sluze primarno tome da bismo pomocu njih nalazili algoritme, vec da bismo dokazali da ih nema...
a cak i za "pozitivne" rezultate, kroz mukotrpno programiranje moramo proci samo jednom, da bismo dokazali onaj teorem dolje (o simulaciji Ca unutar TSa) - nakon toga samo pisemo file-filtere u Cu... got me:-?na kraju krajeva, programiranje jest komplicirana stvar... samo sto ga ti uvijek gledas s "vedrije" strane, odnosno, "stojis na ramenima divova", kako se Newton jednom jako lijepo izrazio...
(hint: jesi li ikad probala napisati C kompajler? U Cu? U Pascalu? U BASICu? U assembleru? U strojnom kodu? Busenim karticama? Klikanjem po mikroprekidacima? Usmjeravanjem elektrona u koherentne tokove? Kuzis o cem pricam:-? Odnosno, bolje receno, kuzis sto hocu reci;-? :)
- Teorem:
- 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.