chtěl jsem se zeptat, zda je z definice TS páska opravdu nekonečná z obou stran od hlavy TS. Já jsem se kupříkladu setkal s popisem TS takového, že páska je sice nekonečná, ale má počátek (v podstatě polopřímka). Při startu programu je hlava na prvním symbolu na pásce a zastavení se neprovádí instrukcí STOP ale tím, že hlava z pásky "vypadne", tj. na prvním symbolu dostane příkaz L.
Asi takto
> . . . . . . . . . .
^
L
PS: vypadá to, že obě pojetí TS jsou ekvivalentní (už jen tím, že vícepáskový TS lze simulovat na jednopáskovém, takže dvě polonekonečné pásky by také šly simulovat)
Bezne se pouzivaji obe pojeti Turingova stroje - s pravostranne nekonecnou a oboustranne nekonecnou paskou. Lze pomerne jednoduse dokazat ze obe pojeti jsou ekvivalentni.
Existuje mnoho modelu TS - stroj s vice hlavami, s vice paskami, s omezenym poctem stavu, omezenym poctem symbolu, omezenym mazanim, jednostranne nekonecnou paskou... Lze ukazat, ze zasobnikovy automat se dvema zasobniky je uz ekvivalentni TS, existuji jeste horsi vymysly, ktere pres svou blaznivost jsou ekvivalentni TS. Jakmile dokazete ekvivalenci sveho formalismu s TS, tak mate vyhrano, muzete si pouzit formalismus, ktery vam vice vyhovuje, vsechno pro TS vude platit i pro vas a naopak. Napr. ve vycislitenosti se pracuje misto s TS typicky s castecne rekurzivnimi funkcemi, coz je mnohem abstraktnejsi formalismus nez TS, ale je ekvivalentni a pro mnohe veci elegantnejsi.
Ano, to vim. Celkem zajimavou zabavou jsou ruzne postupy a dukazy na "redukci" ruznych stroju (napr. vicepaskove) na jednopaskovy TS. Me jen zajimalo, ktera z techto verzi TS je svym zpusobem minimalisticka, tj. obsahuje co nejmensi mnozstvi pasek/hlav/vnitrnich stavu/symbolu, ale pritom ji zustavaji vyjadrovaci schopnosti plneho TS.
Co jsem zatim videl, tak "nejmensi" je TS s jednostranne nekonecnou paskou, jednou hlavou, ktera umi pouze operace L a R a na pasce mohou byt pouze binarni symboly 0 a 1. Samozrejme ze prvni veci, ktere tento TS musi umet je simulace TS s rozsirenou sadou symbolu na pasce.
Obavam se, ze nelze rici, ktera verze je nejminimalistictejsi. Napr. lze udelat TS s pouze dvema aktivnimi stavy, ale zase na ukor nafouknuti abecedy, a naopak lze udelat TS pouze s jednim symbolem (kdyz nepocitam lambda = prazdny symbol), nicmene s mnoha stavy. Dokonce jak jsem zminoval TS s omezenym mazanim, tak to je TS, ktery ma povoleno pouze "kankovani" na pasku, kde kanky uz nesmi po sobe mazat nebo prepisovat na neco jineho nez kanky.
Pro me osobne asi nejdabelstejsi verze TS, o niz jsem slysel, byla "ctyri pocitadla", kde pocitadlo si lze predstavit jako jednostrane nekonecnou pasku, na ktere lze hlavou jezdit vpravo i vlevo, ale nelze na ni zapisovat. A mam pocit (ale tohle uz je ber s rezervou), ze dokonce je snad mozna konstrukce pouze se dvema takovymi pocitadly.
Ten TS s počitadly mi trošku připomíná BBPL - Bare Bone Programming Language. To je progamovací jazyk, který zná jenom konstrukce ++, -- a while !0 (inkrementaci, dekrementaci a smyčka s testem na nulo). Tam se například přiřazení musí udělat pomocí dvou smyček apod. Napsat v něm lze všechny algoritmy, ale pouze za předpokladu, že buňky buď mají neomezený rozsah hodnot, nebo je nekonečný počet buňek...
... stroj s vice hlavami, vice paskami, ... s omezenym mazanim - se podle mého zastaví, protože se zadře :-)
A jinak díky za článek, alespoň se člověk vrátí zase na zem a zjistí, že vlastně z těch počítačů nerozumí skoro ničemu.
