Postovo slovo

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Kreativní množiny.
Benjamin Hejda
Matfyz(ák|ačka) level I
Příspěvky: 29
Registrován: 24. 9. 2006 12:01

Postovo slovo

Příspěvek od Benjamin Hejda »

Nevite nekdo, co znamenaji jednotliva pismenka v Postove slove.

h jsou konce
q je aktualni stav(snad),
ale co reprezentuje 'U' 's' 'V'?

Diky
Vzdycky to nejak dopadne
MrCooper
Matfyz(ák|ačka) level II
Příspěvky: 59
Registrován: 17. 1. 2006 17:54

Příspěvek od MrCooper »

Konfigurace turingace je UqsV:
U jsou vsechna pismena na psana na pasce od zacatku az po cteci hlavu
q je stav stroje
s je znak na pasce pod cteci hlavou
V je zbytek pismen na pasce napravo od cteci hlavy

Viz zapisky od Lenky, strana 3 uprostred. Postovo slovo znamena, ze se to jen obali zarazkama h. Ty ti zarucuji, ze ta jedna lokalni zmena 1 kroku nebude nekonecna, ze nebude cestovat po pasce nekam do pryc. Viz zapisky od Lenky, strana 20.

Kdyby jeste cokoliv, ptej se. Preju hodne stesti.
Benjamin Hejda
Matfyz(ák|ačka) level I
Příspěvky: 29
Registrován: 24. 9. 2006 12:01

Příspěvek od Benjamin Hejda »

Diky, stranu 3 zapisku sem preskocil, na strane 20 sem narazil na Postovo slovo a nevedel, co to je.
Ve skriptech sem ho sice nasel, ale moc mi nepomohlo.
Vzdycky to nejak dopadne
Odpovědět

Zpět na „TIN064 Vyčíslitelnost I“