Postikone

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30. tammikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Postikone  on Emil Postin vuonna 1936 ehdottama abstrakti laskentakone , joka luotiin Turingin koneesta riippumattomasti , mutta Post-konetta koskeva postaus julkaistiin muutamaa kuukautta myöhemmin. Se eroaa Turingin koneesta suuremmalla yksinkertaisuudella, lisäksi molemmat koneet ovat algoritmisesti "ekvivalentteja" ja molemmat on suunniteltu formalisoimaan algoritmin käsite ja ratkaisemaan algoritmisia ratkottavuusongelmia , eli osoittamaan ongelmien algoritmista ratkaisua ohjesarja postikoneelle.

Kuinka se toimii

Postin kone koostuu vaunusta (tai luku- ja kirjoituspäästä) ja nauhasta, joka on jaettu soluihin, molemmin puolin loputon. Jokainen nauhan solu voi olla kahdessa tilassa - joko tyhjä - 0tai merkitty etiketillä 1. Koneen jakson aikana vaunu voi liikkua yhden asennon vasemmalle tai oikealle, laskea, muuttaa merkkiä nykyisessä asemassaan.

Postikoneen toiminta määritellään ohjelmalla , joka koostuu äärellisestä määrästä rivejä. Jotta kone toimisi, sinun on asetettava ohjelma ja sen alkutila (eli nauhan tila ja kelkan sijainti). Kuljetusta ohjaa ohjelma, joka koostuu numeroiduista, ei välttämättä järjestetyistä komentoriveistä, jos jokainen komento määrittää rivin, jolle hypätään. Yleensä hyväksytään, että jos siirtymää ei ole määritetty komennossa, siirtyminen tapahtuu seuraavalle riville. Jokaisella komennolla on seuraava syntaksi:

i. K j

missä i on komennon numero, K on kuljetustoiminto, j on seuraavan komennon (lähetä) numero.

Postikoneelle on yhteensä kuusi erityyppistä komentoa:

• V j - laita etiketti, siirry ohjelman -: jnnelle riville;
• X j — poista tarra, siirry -: jnnelle riville;
• ← j - siirry vasemmalle, siirry -: jnnelle riville;
• → j - siirry oikealle, mene -: jnnelle riville;
• ? j1; j2 - jos solussa ei ole otsikkoa, siirry ohjelman -: j1nnelle riville, muussa tapauksessa -: j2nnelle riville;
• ! - ohjelman loppu ("stop", stop).

"Stop"-komennossa siirtymistä seuraavalle riville ei ilmoiteta.

Ohjelman käynnistämisen jälkeen vaihtoehdot ovat:

• työ voi päättyä suorittamattomaan komentoon (olemattoman tarran poistaminen tai merkittyyn kenttään kirjoittaminen);
• työ voi päättyä pysäytyskäskyyn;
• työ ei lopu koskaan.

Esimerkki

Luonnollisten (ei-negatiivisten kokonaislukujen) P ja Q yhteen- ja vähennyslaskua varten ne voidaan esittää nauhalla joukolla P - yksikköä ja Q , jotka on erotettu toisistaan ​​yhdellä nollalla; olkoon pisteen alkusijainti yksikköryhmän Q vasemmanpuoleisimman "1" kohdalla (merkitty symbolilla " "): ⇓

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

Kahden luvun lisääminen on triviaalia - riittää, että laitat " 1" numeroiden väliin ja pyyhitään yksi äärioikeisto " " Q1 :n esityksestä .

Ohjelma tällaisten lukujen vähentämiseksi koostuu peräkkäin Q1 -esityksen vasemmanpuoleisimman " " ja P -esityksen oikeanpuoleisimman " " muuttamisesta . Ohjelman alussa vaunu on asetettu vasemmanpuoleisimpaan "1" kohtaan Q : 1

1. ←      -askel vasemmalle 2. ? 1; 3 - jos solu on tyhjä, siirry 1-vaiheeseen, jos ei - siirry kohtaan3 3. X      - poista etiketti 4. →      -askel oikealle 5. ? 4; 6 - jos solu on tyhjä, siirry 4-vaiheeseen, jos ei - siirry kohtaan6 6. X      - poista etiketti 7. →      -askel oikealle 8. ? 9; 1 - jos solu on tyhjä, siirry 9vaiheeseen, jos ei - siirry kohtaan1 9. !      - loppu

5. rivillä silmukka on mahdollinen, jos .

Kirjallisuus

• Uspenski Vladimir Andreevich Postikone / Ch. toim. Fys.-Math. lit.. - 2. painos, korjattu - M .: Nauka , 1988 . - 96 s. - ( Suosittuja matematiikan luentoja ). — ISBN 5-02-013735-9 .