Poštovní stroj

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. ledna 2019; kontroly vyžadují 5 úprav .

Stroj Post je abstraktní počítačový stroj navržený Emilem Postem v roce 1936 , vytvořený nezávisle na Turingově stroji , ale příspěvek o stroji Post byl publikován o několik měsíců později. Od Turingova stroje se liší větší jednoduchostí, navíc jsou oba stroje algoritmicky „ekvivalentní“ a oba jsou navrženy tak, aby formalizovaly koncept algoritmu a řešily problémy algoritmické řešitelnosti , tedy demonstrovaly algoritmické řešení problémů ve formě sekvence instrukcí pro stroj Post.

Jak to funguje

Postův stroj se skládá z vozíku (neboli čtecí a zapisovací hlavy) a pásky, rozdělené na buňky, nekonečné na obou stranách. Každá buňka na pásce může být ve 2 stavech – buď prázdná – 0nebo označená štítkem 1. Během cyklu stroje se vozík může posunout o jednu pozici doleva nebo doprava, počítat, měnit znak v aktuální pozici.

Činnost stroje Post je určena programem skládajícím se z konečného počtu řádků. Aby stroj fungoval, musíte nastavit program a jeho počáteční stav (tedy stav pásky a polohu vozíku). Vozík je řízen programem sestávajícím z očíslovaných, ne nutně uspořádaných řádků příkazů, pokud každý příkaz určuje řádek, na který se má přejít. Obvykle se akceptuje, že pokud není přechod v příkazu uveden, dojde k přechodu na další řádek. Každý příkaz má následující syntaxi:

i. K j

kde i je číslo příkazu, K je akce vozíku, j je číslo dalšího příkazu (odeslat).

Celkem existuje šest typů příkazů pro stroj Post:

V j - vložte popisek, přejděte na j-tý řádek programu;
X j — vymazat štítek, přejít na j-tý řádek;
← j - pohyb doleva, přechod na j-tý řádek;
→ j - posuňte se doprava, přejděte na j-tý řádek;
? j1; j2 - pokud v buňce není žádný štítek, přejděte na j1-tý řádek programu, jinak přejděte na j2-tý řádek;
! - konec programu ("stop", stop).

V příkazu "stop" není přechod na další řádek indikován.

Po spuštění programu jsou možnosti:

práce může skončit neproveditelným příkazem (smazání neexistujícího štítku nebo zápis do označeného pole);
práce může skončit příkazem stop;
práce nikdy neskončí.

Příklad

Pro sčítání a odčítání přirozených (nezáporných celých) čísel P a Q mohou být na pásce reprezentována sadou jednotek P a Q , vzájemně oddělených jednou nulou; nechť je počáteční pozice stříšky na levé straně "1" skupiny jednotek Q (označené symbolem " "): ⇓

⇓ …0010010010110… ╚═══╝ ╚═╝ P Q

Sečtení dvou čísel je triviální - stačí vložit " 1" mezi čísla a vymazat jeden krajní pravý " 1" ze znázornění Q .

Program pro odečítání takových čísel sestává z postupné změny " " " 1" nejvíce vlevo v reprezentaci Q a " " zcela vpravo v zobrazení P . Na začátku programu je vozík nastaven na "1" zcela vlevo na Q : 1

1. ← - krok doleva 2. ? 1; 3 - pokud je buňka prázdná, přejděte na 1-krok, pokud ne - přejděte na3 3. X - odstranit štítek 4. → - krok doprava 5. ? 4; 6 - pokud je buňka prázdná, přejděte na 4-krok, pokud ne - přejděte na6 6. X - odstranit štítek 7. → - krok doprava 8. ? 9; 1 - pokud je buňka prázdná, přejděte ke 9kroku, pokud ne - přejděte na1 9. ! - konec

V 5. řádku je smyčka možná, pokud . $Q>P$

Literatura

Uspenskij Vladimír Andrejevič Poštovní stroj / Ch. vyd. Fyzikální matematika lit.. - 2. vyd., opraveno - M .: Nauka , 1988 . — 96 str. - ( Populární přednášky o matematice ). — ISBN 5-02-013735-9 .