Postagép

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. január 30-án felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Postagép  egy Emil Post által 1936 -ban javasolt absztrakt számítástechnika , amelyet a Turing-géptől függetlenül hoztak létre , de a postagépről szóló bejegyzést néhány hónappal később tették közzé. Nagyobb egyszerűségben különbözik a Turing-géptől, ráadásul mindkét gép algoritmikusan „egyenértékű”, és mindkettőt arra tervezték, hogy formalizálja az algoritmus fogalmát és megoldja az algoritmikus megoldhatósági problémákat , vagyis hogy demonstrálja a problémák algoritmikus megoldását utasítássorozat a Postagéphez.

Hogyan működik

A Posta gépe egy kocsiból (vagy egy olvasó- és írófejből) és egy cellákra osztott, mindkét oldalon végtelenített szalagból áll. A szalag minden cellája 2 állapotú lehet - lehet üres - 0vagy címkével megjelölve 1. A gép ciklusa során a kocsi egy pozíciót balra vagy jobbra mozoghat, számolhat, megváltoztathatja a karaktert az aktuális pozíciójában.

A Postagép működését egy véges számú sorból álló program határozza meg. A gép működéséhez be kell állítani a programot és annak kezdeti állapotát (vagyis a szalag állapotát és a kocsi helyzetét). A kocsit egy program vezérli, amely számozott, nem feltétlenül rendezett parancssorokból áll, ha minden parancs megad egy sort, amelyre ugorjon. Általában elfogadott, hogy ha az átmenet nincs megadva a parancsban, akkor az áttérés a következő sorba történik. Minden parancsnak a következő szintaxisa van:

i. K j

ahol i a parancs száma, K a kocsi művelet, j a következő parancs (küldés) száma.

Összesen hatféle parancs létezik a Postagéphez:

• V j - tegyen egy címkét, lépjen ja program -edik sorába;
• X j — törölje a címkét, lépjen a j-edik sorra;
• ← j - balra, menjen a j-edik sorra;
• → j - jobbra, menjen a j-edik sorra;
• ? j1; j2 - ha nincs címke a cellában, akkor menjen j1a program -edik sorába, ellenkező esetben lépjen a j2-edik sorba;
• ! - a program vége ("stop", stop).

A "stop" parancsban a következő sorra való áttérés nincs feltüntetve.

A program elindítása után a következő lehetőségek állnak rendelkezésre:

• a munka nem végrehajtható paranccsal végződhet (nem létező címke törlése vagy megjelölt mezőbe írás);
• a munka leállítási paranccsal fejeződhet be;
• a munka soha nem ér véget.

Példa

A természetes (nem negatív egész) P és Q számok összeadására és kivonására egy szalagon ábrázolhatók P egységek és Q halmazával , amelyeket egymástól egy nullával választanak el; legyen a mérőpont kezdeti helyzete a Q egységcsoport bal szélső "1"-jén (" " szimbólummal jelölve ): ⇓

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

Két szám összeadása triviális - elég a " 1" számok közé tenni és kitörölni egy jobb szélsőt a Q1 ábrázolásából .

Az ilyen számok kivonására1 szolgáló program a Q reprezentáció bal szélső " " és a P reprezentáció jobb szélső " " szekvenciális megváltoztatásából áll . A program elején a kocsi a bal szélső "1"-re áll Q : 1

1. ←      - lépj balra 2. ? 1; 3 - ha a cella üres, ugorjon a 1-lépésre, ha nem - menjen a következőre3 3. X      - távolítsa el a címkét 4. →      - lépj jobbra 5. ? 4; 6 - ha a cella üres, ugorjon a 4-lépésre, ha nem - menjen a következőre6 6. X      - távolítsa el a címkét 7. →      - lépj jobbra 8. ? 9; 1 - ha a cella üres, menjen a 9lépésre, ha nem - menjen tovább1 9. !      - vége

Az 5. sorban akkor lehetséges a ciklus, ha .

Irodalom

• Uszpenszkij Vlagyimir Andrejevics Postagép / Ch. szerk. Fiz.-Matek. lit.. - 2. kiadás, javítva - M . : Nauka , 1988 . — 96 p. - ( Népszerű matematikai előadások ). — ISBN 5-02-013735-9 .