Ekvivalenty Turingova stroje - Turing machine equivalents

Turingův stroj je hypotetická výpočetní zařízení, nejprve koncipovaný podle Alan Turing v roce 1936. Turingovy stroje manipulovat se symboly na potenciálně nekonečného pásu pásky podle konečné tabulce pravidel, a poskytují teoretické základy pro pojem počítačového algoritmu.

Přestože se u žádného z následujících modelů neprokázalo, že by měl větší sílu než jednovrstvý, jednosměrný nekonečný, vícesymbolový model Turingova stroje, jejich autoři je definovali a používali je ke zkoumání otázek a řešení problémů snadněji, než by mohli mít kdyby zůstal s Turing je -Obráběcí modelu.

Stroje ekvivalentní modelu Turingova stroje

Turingova ekvivalence

Mnoho strojů, o kterých by se dalo předpokládat, že mají více výpočetních schopností než jednoduchý univerzální Turingův stroj, může být prokázáno, že nemají větší výkon. Mohou počítat možná rychleji, nebo používat méně paměti nebo jejich instrukční sada může být menší, ale nemohou počítat výkonněji (tj. Více matematických funkcí). ( Teze Church – Turingova hypotéza předpokládá, že je to pravda: že cokoli, co lze „vypočítat“, může vypočítat nějaký Turingův stroj.)

Modely sekvenčních strojů

Všechny následující položky se nazývají „sekvenční modely strojů“, aby se odlišily od „modelů paralelních strojů“.

Turingovy stroje na bázi pásky

Turing -Obráběcí modelu

Turingův a-stroj (jak mu říkal) byl levý, nekonečný pravý. Poskytl symboly əə k označení levého konce. Byl povolen konečný počet páskových symbolů. Pokyny (pokud jde o univerzální stroj) a „vstup“ a „ven“ byly napsány pouze na „F-čtverce“ a značky se měly objevit na „E-čtvercích“. V podstatě rozdělil svůj stroj na dvě kazety, které se vždy pohybovaly společně. Pokyny se objevily v tabulkové podobě s názvem „5-tice“ a nebyly prováděny postupně.

Jednopáskové stroje s omezenými symboly a/nebo omezenými pokyny

Následující modely jsou Turingovy stroje s jednou páskou, ale omezené (i) omezenými symboly pásek {značka, prázdné} a/nebo (ii) sekvenčními instrukcemi podobnými počítači a/nebo (iii) strojními akcemi plně atomizovanými.

Post je model výpočtu "Formulace 1"

Emil Post v nezávislém popisu výpočetního procesu redukoval povolené symboly na ekvivalentní binární sadu značek na pásce {"značka", "prázdné" = not_mark}. Změnil pojem „páska“ z jednosměrného nekonečna doprava na nekonečnou sadu místností, z nichž každá měla list papíru v obou směrech. Atomizoval Turingovy 5-tice na 4-tice-pohybové instrukce oddělené od instrukcí pro tisk/mazání. Ačkoli jeho model z roku 1936 je v tomto ohledu nejednoznačný, Postův model z roku 1947 nevyžadoval sekvenční provádění instrukcí.

Jeho extrémně jednoduchý model může napodobit jakýkoli Turingův stroj, a přestože jeho formulace 1 z roku 1936 nepoužívá slovo „program“ nebo „stroj“, ve skutečnosti jde o formulaci velmi primitivního programovatelného počítače a přidruženého programovacího jazyka , přičemž krabice fungují jako neomezenou paměť bitových řetězců a sadu instrukcí tvořících program.

Wang stroje

Ve vlivném článku Hao Wang redukoval Postovu „ formulaci 1 “ na stroje, které stále používají obousměrný nekonečný binární pásek, ale jejichž instrukce jsou jednodušší-jsou „atomovými“ komponentami Postových instrukcí-a jsou standardně prováděny sekvenčně (jako „počítačový program“). Jeho hlavním cílem bylo nabídnout jako alternativu k Turingově teorii teorii, která „je ekonomičtější v základních operacích“. Jeho výsledky byly „programové formulace“ různých takových strojů, včetně 5-instrukčního Wangova stroje s instrukční sadou

{SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, ERASE-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx}

a jeho nejzávažněji redukovaný 4-instrukční Wang B-stroj ("B" pro "základní") s instrukční sadou

{SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx}

který nemá ani instrukci ERASE-SQUARE.

Mnoho autorů později představilo varianty strojů diskutovaných Wangem:

Minsky rozvinul Wangovu představu pomocí své verze (vícepásmového) modelu „pultového stroje“, který umožňoval pohyb oddělených hlav SHIFT-LEFT a SHIFT-RIGHT, ale vůbec žádný tisk. V tomto případě by pásky měly levý konec, každý konec by byl označen jednou „značkou“, která by znamenala konec. Dokázal to zredukovat na jedinou pásku, ale na úkor zavedení vícepásmového čtvercového pohybu ekvivalentního násobení a dělení, než mnohem jednoduššího {SHIFT-LEFT = DECREMENT, SHIFT-RIGHT = INCREMENT}.

Davis, který k jednomu ze strojů diskutovaných Wangem přidal explicitní instrukci HALT, použil model s instrukční sadou

{SHIFT-LEFT, SHIFT-RIGHT, ERASE, MARK, JUMP-IF-SQUARE-MARKED-to xxx, JUMP-to xxx, HALT}

a také považovány za verze s páskovými abecedami o velikosti větší než 2.

Böhmův teoretický strojový jazyk P "

V souladu s Wangovým projektem hledat teorii ekvivalentu Turinga „ekonomickou v základních operacích“ a přát si vyhnout se bezpodmínečným skokům, je pozoruhodným teoretickým jazykem 4-instrukční jazyk P „ zavedený Corrado Böhmem v roce 1964-první„ GOTO -less“imperativ‚ strukturované programování ‘jazyk, který bude prokázáno Turing-kompletní .

Vícepáskové Turingovy stroje

V praktické analýze se často používají různé typy Turingových strojů s více páskami. Vícepáskové stroje jsou podobné jako single-páskových strojů, ale tam je nějaká konstanta k množství nezávislých pásek.

Deterministické a nedeterministické Turingovy stroje

Pokud tabulka akcí obsahuje maximálně jeden záznam pro každou kombinaci symbolu a stavu, pak je strojem „deterministický Turingův stroj“ (DTM). Pokud tabulka akcí obsahuje více záznamů pro kombinaci symbolu a stavu, pak je stroj „nedeterministický Turingův stroj“ (NDTM). Ty dva jsou výpočetně ekvivalentní, to znamená, že je možné z libovolného NDTM udělat DTM (a naopak ) , i když obvykle mají různé doby běhu. To lze prokázat konstrukcí.

Oblivious Turingovy stroje

Nevšímavý Turingův stroj je Turingův stroj, kde pro každou délku vstupu je pohyb různých hlav pevnou funkcí času, nezávislou na vstupu. Jinými slovy, existuje předem stanovená sekvence, ve které jsou různé pásky skenovány, rozšířeny a zapsány. Skutečné hodnoty, které jsou zapsány na pásku v kterémkoli kroku, se mohou stále lišit pro každý vstup této délky. Pippenger a Fischer ukázali, že jakýkoli výpočet, který může být prováděn vícepáskovým Turingovým strojem v n krocích, může být prováděn zapomnětlivým Turingovým strojem se dvěma páskami v krocích. ${\ Displaystyle O (n \ log n)}$

Zaregistrujte modely strojů

Peter van Emde Boas zahrnuje všechny stroje tohoto typu v jedné třídě, „registrační stroj“. Historicky však literatura také nazývala nejprimitivnějšího člena této skupiny, tj. „Počítač pultu“ - „stroj rejstříku“. A nejprimitivnějšímu provedení „pultového stroje“ se někdy říká „Minskyho stroj“.

„Počítadlo“, nazývané také model „registrační stroj“

Registrační stroj primitivního modelu je ve skutečnosti vícepásmový 2-znakový Post-Turingův stroj s omezeným chováním, takže jeho pásky fungují jako jednoduché „čítače“.

V době Melzak, Lambek a Minsky vytvořil pojem „počítačový program“ jiný typ jednoduchého stroje s mnoha levostrannými páskami odstřiženými z pásky Post-Turing. Ve všech případech modely povolují pouze dva symboly na pásku {značka, prázdné}.

Některé verze představují kladná celá čísla pouze jako řetězce/hromady značek povolených v „registru“ (tj. Páska s levým koncem) a prázdná páska reprezentovaná číslem „0“. Minsky odstranil instrukci PRINT na úkor toho, že svému modelu poskytl povinnou jedinou značku na levém konci každé kazety.

V tomto modelu jsou jednorázové pásky jako registry považovány za "čítače", jejich instrukce jsou omezeny pouze na dva (nebo tři, pokud je instrukce TEST/DECREMENT atomizována). Dvě běžné instrukční sady jsou následující:

(1): {INC (r), DEC (r), JZ (r, z)}, tzn

{INCrement obsah registru #r; DECrement obsah registru #r; KDYŽ obsah #r = nula, PAK přejít na instrukci #z}

(2): {CLR (r); INC (r); JE (r _i , r _j , z)}, tj

{CLeaR obsah registru r; INCrement obsah r; porovnat obsah r _i s r _j a pokud je rovný, pak Přejít na instrukci z}

Přestože je jeho model komplikovanější než tento jednoduchý popis, Melzakův „oblázkový“ model rozšířil tuto představu o „počitadle“, aby umožňoval sčítání a odčítání více oblázků.

Model stroje s náhodným přístupem (RAM)

Melzak rozpoznal několik vážných vad svého modelu registr/počítač: (i) Bez formy nepřímého adresování by nebyl schopen „snadno“ ukázat, že model je Turingův ekvivalent , (ii) Program a registry byly v různých „mezery“, takže samoobslužné programy by nebyly jednoduché. Když Melzak přidal do svého modelu nepřímé adresování, vytvořil model stroje s náhodným přístupem.

(Nicméně s Gödelovým číslováním pokynů Minsky nabídl důkaz, že s takovým číslováním byly obecné rekurzivní funkce skutečně možné; nabízí důkaz, že μ rekurze je skutečně možná).

Na rozdíl od modelu RASP model RAM neumožňuje akci stroje upravit jeho pokyny. Někdy model funguje pouze pro registraci bez registrace, ale většina modelů zřejmě obsahuje akumulátor.

van Emde Boas rozděluje různé modely RAM do několika podtypů:

SRAM, „nástupnická RAM“ s jedinou aritmetickou instrukcí, nástupce (INCREMENT h). Mezi ostatní patří "CLEAR h" a IF equality-between-register THEN jump-to xxx.
RAM: standardní model s přidáváním a odčítáním
MRAM: RAM rozšířená o násobení a dělení
BRAM, MBRAM: Bitové booleovské verze RAM a MRAM
N ****: Nedeterministické verze kteréhokoli z výše uvedených s N před jménem

Model stroje s uloženým programem s náhodným přístupem (RASP)

RASP je RAM s instrukcemi uloženými společně s jejich daty ve stejném „prostoru“ - tj. Posloupnosti registrů. Pojem RASP byl popsán přinejmenším již v Kiphengst. Jeho model měl „mlýn“-akumulátor, ale nyní byly pokyny v registrech s daty-takzvaná von Neumannova architektura . Když má RASP střídající se sudé a liché registry - sudé držící „operační kód“ (instrukce) a liché držící jeho „operand“ (parametr), pak je nepřímého adresování dosaženo jednoduše úpravou operandu instrukce.

Původní RASP model Elgot a Robinson měl pouze tři instrukce ve stylu modelu registračního stroje, ale umístili je do prostoru registru společně se svými daty. (Zde COPY nahrazuje CLEAR, když jeden registr, např. „Z“ nebo „0“ začíná na a vždy obsahuje 0. Tento trik není neobvyklý. Hodí se také jednotka 1 v registru „unit“ nebo „1“.)

{INC (r), COPY (r _i , r _j ), JE (r _i , r _i , z)}

Modely RASP umožňují nepřímé i přímé adresování; některé umožňují i „okamžité“ pokyny, např. „Načíst akumulátor s konstantou 3“. Pokyny mohou být velmi omezené sady, například následujících 16 pokynů společnosti Hartmanis. Tento model používá akumulátor A. Mnemotechnické pomůcky jsou ty, které autoři použili (jejich CLA je „load akumulátor“ s konstantou nebo z registru; STO je „akumulátor akumulace“). Jejich syntaxe je následující, kromě skoků: „n, <n>, <<n>>“ pro „okamžité“, „přímé“ a „nepřímé“). Skoky se provádějí dvěma TRA „Přenosovými instrukcemi“ - bezpodmínečným skokem přímo „n“ nebo nepřímo „<n>“ zaseknutím obsahu registru n do čítače instrukcí, TRZ (podmíněný skok, pokud je Akumulátor nulový stejným způsobem jako TRA):

{ADD n, ADD <n>, ADD << n >>, SUB n, SUB <n>, SUB << n >>, CLA n, CLA <n>, CLA << n >>, STO <n> , STO << n >>, TRA n, TRA <n>, TRZ n, TRA <n>, HALT}

Model stroje Pointer

Relativním zpožděním je Schönhage's Storage Modification Machine nebo pointer machine . Další verzí je stroj Kolmogorov-Uspensii a návrh Knuth „spojovací automat“. (Reference viz stroj s ukazatelem ). Podobně jako diagram stavového stroje vysílá uzel alespoň dva označené „okraje“ (šipky), které směřují k jinému uzlu nebo uzlům, které zase směřují k jiným uzlům atd. Vnější svět ukazuje na středový uzel.

Stroje se vstupem a výstupem

Kterýkoli z výše uvedených páskových strojů může být vybaven vstupními a výstupními páskami; kterýkoli z výše uvedených strojů na bázi registrů může být vybaven vyhrazenými vstupními a výstupními registry. Například model ukazovacího stroje Schönhage má dvě instrukce nazvané „ vstup λ ₀ , λ ₁ “ a „ výstup β “.

Je obtížné studovat sublineární prostorovou složitost na vícepáskových strojích s tradičním modelem, protože vstup velikosti n již zabírá místo n . Abychom mohli studovat malé třídy DSPACE , musíme použít jiný model. V jistém smyslu, pokud nikdy „nepíšeme“ na vstupní pásku, nechceme se za tento prostor nabíjet. A pokud nikdy nečteme z naší výstupní kazety, nechceme se za tento prostor nabíjet.

My tento problém vyřešit zavedením K -string Turingův stroj se vstupem a výstupem. To je stejné jako u běžného Turingova stroje s k -řetězcem, kromě toho, že přechodová funkce $δ$ je omezena, takže vstupní pásku nelze nikdy změnit a výstupní hlava se nikdy nemůže pohybovat doleva. Tento model nám umožňuje definovat deterministické třídy prostoru menší než lineární. Turingovy stroje se vstupem a výstupem mají také stejnou časovou náročnost jako ostatní Turingovy stroje; slovy Papadimitriou 1994 Prop 2.2:

Pro jakýkoli k -strunovací Turingův stroj M pracující v časovém limitu existuje Tringův Turingův stroj M ' se vstupem a výstupem, který pracuje v časovém limitu .

{\ Displaystyle f (n)}

{\ displaystyle (k+2)}

{\ Displaystyle O (f (n))}

k -string Turingovy stroje se vstupem a výstupem lze použít ve formální definici zdroje složitosti DSPACE .

Jiné ekvivalentní stroje a metody

Multidimenzionální Turingův stroj: Například model od Schönhage používá čtyři příkazy pro pohyb hlavy { N orth, S outh , E ast, W est}.
Jednopáskový, vícehlavý Turingův stroj: Jako důkaz nerozhodnutelnosti „problému štítku“ popsali Minsky a Shepherdson a Sturgis stroje s jedinou páskou, která dokázala číst podél pásky s jednou hlavou a psát dále po pásce s jinou .

Markovův algoritmus je další pozoruhodně jednoduchý výpočetní model založený na přepisování řetězců, ekvivalentní Turingovým strojům.
Lambda kalkul
Automat na frontě

Languages

In other projects