Galerie Turingova stroje - Turing machine gallery

Následující článek je doplňkem článku Turingův stroj.
Turingův stroj jako mechanické zařízení
Zde zobrazený Turingův stroj se skládá ze speciálu papírová páska které lze vymazat i zapsat „známkou“. Možná je TABULKA vyrobena z podobné čtečky papírových pásků „jen pro čtení“, nebo snad čte děrné štítky. Turingův životopisec Andrew Hodges (1983) napsal, že Turing jako dítě měl rád psací stroje. „Zázračný stroj“ - mechanický proces, který by mohl fungovat Hilbert problém s rozhodnutím "(Hodges str. 98) navrhl G. H. Hardy, jeden z Turingových učitelů. „Jeho stroj však neměl žádný zjevný model v ničem, co existovalo v roce 1936, kromě obecných pojmů nový elektrotechnický průmysl s jejich dálnopisů, televize 'snímání ', a automatická telefonní ústředna připojení. Byl to jeho vlastní vynález. “(Hodges str. 109)
Davis (2000) říká, že Turing postavil a binární multiplikátor mimo elektromechanické relé (str. 170). Jak je uvedeno v sekci historie algoritmus děrované nebo potištěné papírové pásky a děrované papírové karty byly ve 30. letech běžné.
Boolos a Jeffrey (1974, 1999) poznamenávají, že „být v tak či onakém stavu může být otázkou mít jeden nebo druhý zub určitého stupně nahoře ...“ (s. 21).
Turingův stroj jako „špatný hrnek“ uvnitř krabice táhnoucí krabici podél kolejnice
- „Nezajímá nás mechanika ani elektronika věci. Snad nejjednodušší způsob, jak si to představit, je celkem surové: Uvnitř skříňky je muž, který dělá všechno čtení a psaní, mazání a pohyb. nemá dno: chudák hrnek jen kráčí mezi kravaty a táhne s sebou krabici.) Ten muž má na kus papíru napsaný seznam instrukcí m. Je ve stavu qi, když provádí číslo instrukce i [atd.] “(Boolos a Jeffrey (1974, 1999), s. 21)
Tento popis pečlivě následuje Emil Post „Formulace I“ pro „konečný kombinovaný proces“: muž, který je vybaven „pevnou nezměnitelnou sadou instrukcí“ a řídí se jím, pohybem doleva nebo doprava přes „nekonečný sled mezer nebo krabic“ a v krabici buď tisk na kus papíru jediným "svislým tahem" nebo jeho vymazání (příspěvek 1936 přetištěn v roce 2006) Nerozhodnutelné str. 289). Postova formulace byla první svého druhu, která byla zveřejněna; předcházelo to Turingovu otázkou několika měsíců.
Oba popisy - Post a Boolos a Jeffrey - používají k definování „m-konfigurací“ (instrukcí) svých procesů jednodušší 4-tice.
Pokyny provádí robot
Tento model navrhl Stone (1972):
- „Pojďme si osvojit názor, že počítač je robot, který bude provádět jakýkoli úkol, který lze popsat jako posloupnost pokynů“ (str. 3).
Stone používá robota k rozvoji své představy o algoritmus. To ho zase vede k jeho popisu Turingova stroje a jeho prohlášení:
- „Důkazy podle všeho naznačují, že každý algoritmus pro jakékoli výpočetní zařízení má ekvivalentní Turingův strojový algoritmus ... pokud je [Churchova teze] pravdivá, je jistě pozoruhodné, že Turingovy stroje jsou se svými extrémně primitivními operacemi schopné provádět jakýkoli výpočet které může provádět jakékoli jiné zařízení, bez ohledu na to, jak složité zařízení zvolíme. “ (str. 13)
Reference
Viz hlavní článek Turingův stroj pro reference.