Post maskine

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. januar 2019; checks kræver 5 redigeringer .

Post-maskinen  er en abstrakt computermaskine foreslået af Emil Post i 1936 , skabt uafhængigt af Turing-maskinen , men indlægget om Post-maskinen blev offentliggjort et par måneder senere. Den adskiller sig fra Turing-maskinen i større enkelhed, desuden er begge maskiner algoritmisk "ækvivalente", og begge er designet til at formalisere begrebet en algoritme og løse algoritmiske løselighedsproblemer , det vil sige at demonstrere den algoritmiske løsning af problemer i form af en række instruktioner til postmaskinen.

Sådan virker det

Postens maskine består af en vogn (eller et læse- og skrivehoved) og et bånd, opdelt i celler, endeløse på begge sider. Hver celle på båndet kan være i 2 tilstande - enten være tom - 0eller markeret med en etiket 1. Under maskinens cyklus kan vognen bevæge sig en position til venstre eller højre, tælle, ændre karakteren i sin nuværende position.

Postmaskinens funktion bestemmes af et program bestående af et begrænset antal linjer. For at maskinen skal fungere, skal du indstille programmet og dets starttilstand (det vil sige båndets tilstand og vognens position). Vognen styres af et program bestående af nummererede, ikke nødvendigvis ordnede kommandolinjer, hvis hver kommando angiver en linje at springe til. Det er normalt accepteret, at hvis overgangen ikke er angivet i kommandoen, så sker overgangen til næste linje. Hver kommando har følgende syntaks:

i. K j

hvor i er kommandonummeret, K er vognhandlingen, j er nummeret på den næste kommando (afsendelse).

I alt er der seks typer kommandoer til Post-maskinen:

• V j - sæt en etiket, gå til den j-th linje i programmet;
• X j — slet etiketten, gå til j-th linje;
• ← j - flyt til venstre, gå til j-th linje;
• → j - flyt til højre, gå til j-th linje;
• ? j1; j2 - hvis der ikke er nogen etiket i cellen, så gå til den j1-th linje i programmet, ellers gå til den j2-th linje;
• ! - programslut ("stop", stop).

I "stop"-kommandoen er overgangen til næste linje ikke angivet.

Efter start af programmet er mulighederne:

• arbejdet kan ende med en ueksekverbar kommando (sletning af en ikke-eksisterende etiket eller skrivning til et markeret felt);
• arbejdet kan afsluttes med en stopkommando;
• arbejdet vil aldrig ende.

Eksempel

Til addition og subtraktion af naturlige (ikke-negative heltal) tal P og Q kan de repræsenteres på et bånd med et sæt P - enheder og Q , adskilt fra hinanden med et nul; lad indgangspositionen af ​​feltet være længst til venstre i gruppen af ​​enheder Q (markeret med symbolet " "): ⇓

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

At tilføje to tal er trivielt - det er nok at sætte " 1" mellem tallene og slette den ene yderste højre " 1" fra repræsentationen af ​​Q .

Programmet til at subtrahere sådanne tal består af sekventiel ændring af den længst venstre " 1" af Q -repræsentationen og den længst til højre " " af P -repræsentationen . I starten af ​​programmet er vognen sat til længst til venstre ved Q : 1

1. ←      - gå til venstre 2. ? 1; 3 - hvis cellen er tom, gå til 1-trin, hvis ikke - gå til3 3. X      - Fjern etiketten 4. →      - Træd til højre 5. ? 4; 6 - hvis cellen er tom, gå til 4-trin, hvis ikke - gå til6 6. X      - Fjern etiketten 7. →      - Træd til højre 8. ? 9; 1 - hvis cellen er tom, gå til 9trin, hvis ikke - gå til1 9. !      - slutningen

I 5. linje er en løkke mulig, hvis .

Litteratur

• Uspensky Vladimir Andreevich Postmaskine / Ch. udg. Fysisk.-Matematik. lit.. - 2. udg., rettet - M . : Nauka , 1988 . — 96 s. - ( Populære foredrag om matematik ). — ISBN 5-02-013735-9 .