Matematické Fórum

No a chtel bych se jeste zeptat, jestli nahodou nekdo tady nema obrazek turingova stroje. mam za ukol jeste dodelat nejaky jednoduchy prevod z ram na turinga. v RAM staci jen par ukazkovych prikazu, napriklad cyklus, ketry bude delat cyklus od 0 do 10 s navysneim o jednicku, a pak to chce prevest na turinga, aby to delalo tu stejnou funkci.
pro ten ram stroj jsem vymyslel tenhle algoritmus

1.  LOAD  =0
2.  STORE  2
3.  LOAD   2
4.  ADD   =1
5.  JUMP   2

ale ma jednu chybku, a to, ze je to nekonecny cyklus, a ja netusim jak mam udelat, aby se zastavil na jakemkoliv cisle.
pokud na to nekdo rpijde, a prijde i na to, jak z toho udelat turinguv stroj, tak bych mu byl hrozne moc vdecny.
predem diky

↑ Sha-a-kaa:RAM má nějakou instrukci podmíněného skoku, JZ nebo JE (http://en.wikipedia.org/wiki/Random_access_machine).
Zkus pohledata ve vašich materiálech, s jakou sadou instrukcí  jste si ho zavedli.

↑ Sha-a-kaa:

No hele nepochopil sem co presne v tom cyklu jakoze chces delat... Z tech instrukci co tam mas chapu, ze nactes 10, coz je asi 10 iteraci cyklu, pak mas jako telo cyklu a tam nactes dvojku a ulozis ji zpatky ?? odectes jednicku od ty iteracni promenny a bud koncis kdyz si na nule nebo skaces na zacatek...

Tady mas ten TS ve forme kompozitniho diagramu



tady je to rozkresleny na bubliny :)





Jak to funguje? Stroj je na začátku na první pozici kde má pod čtecí hlavou Δ na dalších pozicích má a-čka a má jich tam za sebou tolik kolikrát se má provést ten cyklus. Stroj se teda posune doprava, kdyz tam neni zadny a-čko ale je tam Δ (tomu jsme říkali blank) tak skončí a skončí tak, že ne pásku zapíše Y. Jakože Yes, prostě tak sem vždycky dělal konec, ale může tam být cokoli. Jinak přečte to jedno a-čko, smaže ho tím, že ho přepíše Δ posunuje se doprava dokud nenarazí na konec těch a-ček a pak se vrátí na začátek. Buď zas čte a-čka jestli tam ještě jsou, nebo už tam nic neni a zapíše na pásku Y a konec.
Takže z jinýho pohledu to prostě dělá cyklus o n iteracích ve kterym se nic nedělá :) a šmitec :)

Edit: jo ještě kdyby ses ptal proč tam sou na ty pasce a-čka a ne třeba b-čka, tak je to prostě protože sem to tak udělal, zas můžeš na tu pásku dát cokoli. Aby to bylo komplet tak bys ještě měl formálně napsat definici toho stroje, teda vypsat stavy, páskovou abecedu, vstupní abecedu, množinu stavů, počáteční stav, koncový stav, a přechodovou funkci.

↑ Sha-a-kaa:
Heh...
rek bych, ze tohle po vas ucitel urcite nechce jelikoz to nejde :)
Strucne ti vysvetlim co to je TS... Je to matematicky model pocitace, ktery je formálně definován takhle:



Q ... značí množinu stavů
Sigma ... vstupní abeceda
Gama ... pásková abeceda
delta ... přechodová funkce
q0 ... počáteční stav
qf ... koncový stav

O co jde? Víš co to je konečnej automat? Jestli jo tak tohle je něco podobnýho, jenom to má větší výpočetní sílu...
TS je stroj, kterej má v základu jednu pásku což je jako jeho paměť, (je definovaná jako nekonečná, prostě si představ třeba nekonečně dlouhou pásku papíru) a má čtecí/zápisovou hlavu.
Co může TS dělat?
TS může přečíst symbol pod čtecí hlavou a na záklaě toho co přečte buď posunout čtecí hlavu o jednu pozici doprava, nebo doleva, nebo symbol pod čtecí hlavou přepsat. Toť vše.
Teď tu nekonečnou pásku si představ, že neni až tak úplně prázdná. Na místě, kde nic neni je právě ten symbol Δ (což prostě značí, že tam nic neni).

Teď k tomu prvnímu diagramu
Tomu se řiká kompozitní diagram protože to je zjednodušenej zápis TS, který je složený z několika TS (v mym případě z 5ti - každý písmenu = jeden Turinguv stroj) do jednoho většího TS. To si můžeš představit jako program, který má několik podprogramů. Ten podprogram je vlastně taky program sám o sobě že jo...
Co znamenají ty písmena v tom diagramu?
R...stroj se posune o jednu pozici doprava, bez ohledu na to co je pod čtecí hlavou, to R je jakože z Right :)
Δ...stroj zapíše na pozici čtecí hlavy Δ. Nikam se neposunuje, to znamená, že po zápisu Δ má pod čtecí hlavou Δ :) Neni to teda jako na psacim stroji, že po zápisu písmene automaticky skočíš na další pozici.
RΔ...R s indexem delta. Stroj posouvá čtecí hlavu doprava dokud nenarazí na pásce na Δ.
LΔ...L s indexem delta. Stroj posouvá čtecí hlavu doleva dokud nenarazí na pásce na Δ.
Y...stroj zapíše na pozici čtecí hlavy Y.

Teď se podivej jaká je počáteční konfigurace pásky. To je důležitý...
Je tam jedno Δ (to podtržítko pod tim znamená, že úplně na začátku je čtecí hlava na týhle pozici). Dál je tam celkem n a-ček (což udává kolikrát cyklus poběží). No a na zbytku pásky jsou už jenom symboly Δ což znamená jakože tam nic neni. To se zapisuje tim Δ^omega - tak se prostě značí, že je na pásce nějaký symbol nekonečně-krát.

Jestli si tohle pochopil tak by ti mělo být jasný jak to funguje (alespoň z toho prvního diagramu).
Dejme tomu, že chceš aby cyklus běžel 2x. Takže na začátku bude na pásce, ΔaaΔΔΔΔ.... čtecí hlava bude na první pozici.
Na začátku se stroj posune o jednu pozici doprava (to dělá ten TS R). Pokud je pod čtecí hlavou a-čko a to v našem případě je tak ho přepíše na Δ (což je ekvivalent toho že inkrementuješ nebo dekrementuješ iterační proměnnou) a bude se posouvat doprava tak dlouho dokud nenarazí na Δ. Prostě přeskočí všechny ty a-čka. Po tomhle bude stav vypadat takhle ΔΔaΔΔΔΔ...
Proč to bude dělat? No tohle je to tělo toho cyklu...prostě tělo cyklu je, že posunu hlavu a vrátim jí zpátky páč mi nebylo jasný co chceš aby se dělo...V dalším kroku se bude posouvat hlava doleva dokud nenarazí na Δ. Takže pak to bude vypadat takhle ΔΔaΔΔΔΔ...Zase posunu se o jednu doprava. Pokud je pod čtecí hlavou a-čko (což bude), tak ho přepíšu na Δ a budu se posouvat zas doprava dokud nenarazim na symbol Δ. Což teď bude už jenom o jednu pozici!!! Následně se budu posouvat doleva dokud nenarazim na Δ, což bude zas už jenom o jednu pozici. Pak se posunu o jednu doprava a protože v tuhle chvíli je pod čtecí hlavou Δ (vyčerpal sem všechny a-čka), tak na tuhle pozici zapíšu Y (jako Yes) a skončim.

No a to je všechno...Prostě cyklus poběží tolikrát kolik tam je a-ček a to tělo cyklu je prostě to, že posouvám čtecí hlavu doprava a zpátky. Jo klidně by se dalo udělat, že bych někam překopíroval ten počet a-ček pak ho jako překopíroval zpátky a jedno umazal, ale na to prdim. Ono možná něco co vypadá jednoduše jako jedna instrukce někde jinde může být kua složitý udělat v TS. Je nesmysl si myslet, že jakoby jednu instrukci budeš mít jako jednu "bublinu" v TS. Možná se ptáš proč tam píšu na tu pásku a-čka tolikrát kolikrát má ten cyklus běžet, proč tam prostě nenapíšu 10tku což by zabíralo na pásce jenom dvě místa. No uvědom si, že "podstroj" co by jenom inkrementoval nebo dekrementoval tohle číslo by byl kua složitej.
To co teď napíšu neni žádná definice takže mě nechytej za slovo :) TS je prostě ten nejprimitivnější počítač, kterej má ale zároveň výpočetní sílu dnešních univerzálních počítačů. Jinak řečeno dá se na něm spustit jakýkoli program. Klidně by na něm šel pustit třeba Unreal :))

No ještě rychle k tomu druhýmu diagramu co sem tam hodil. Teď sem si všimnul, že tam je malá chybka, místo toho Y, tam má být Δ/Y tak si to oprav jestli to budeš chtít použít.
Když se podiváš na tu formální definici co sem psal vejš tak tam je něco o tom, že TS může být v různých stavech. Ten druhej diagram teda zahrnuje i informaci o tom v jakých stavech se TS postupně nachází. Prakticky se ale spíš používá ten první protože ten druhej vede jaksi na kapku větší schémata.

Heh...no to neni vicepaskovej TS nikde si nepsal,ze to ma byt vicepaskovej...navíc jednopáskovej TS má stejnou výpočetní sílu jako vícepáskovej, dá se to nějak dokázat.
Takže muj návrh: s každou iterací na tu druhou pásku udělám jeden nějakej symbol a je vymalováno ok?
Jo a nebude to dřív jak v pondělí páč na to teď neni čas, takže se zatim můžeš snažit sám a pak to porovnáme :)