Phenquestions
Turingův stroj je ústřední teoretický konstrukt v počítačové vědě. Turingův stroj je abstraktní matematický model výpočtu. Použití Turingových strojů pomáhá vysvětlit, co je výpočet, vymezením takzvaných „vypočítatelných funkcí.“
Počáteční výzkum logiky Alana Turinga se zaměřil na slavný nevyřešený problém známý jako Entscheidungsproblem. Entscheidungsproblem (hrubě přeložený z němčiny jako rozhodovací problém) navrhl filozof a matematik David Hilbert v roce 1928. Problém se zeptal, zda existuje algoritmus, který by rozhodoval o každém výroku ve formálním jazyce.
Formální jazyk je systém axiomů a odvozovacích pravidel, jako jsou pravidla v aritmetice nebo logice prvního řádu. Axiomy mohou být jakékoli symboly a odvozovacími pravidly může být libovolný seznam pravidel pro manipulaci s těmito symboly. „Rozhodování o každém výroku“ znamenalo buď výstup, zda byl výrok pravdivý / nepravdivý, nebo výstup, zda byl výrok odvozitelný / nerozdělitelný. Věta o úplnosti Kurta Godla dokázala, že algoritmus rozhodující o platnosti je ekvivalentní efektivnímu postupu rozhodujícímu pro odvoditelnost. Článek Alana Turinga z roku 1936 „O vypočítatelných číslech s aplikací na problém Entscheidungs“ ukázal negativní výsledek, že nebylo možné algoritmicky rozhodnout o každém výroku ve formálním systému.
Alan Turing
Aby Turing dokázal negativní výsledek pro problém Entscheidungs, potřeboval formalizovat představu algoritmu. Turingova formalizace algoritmu byl matematický model výpočtu, který se později stal známým jako Turingův stroj. Turingův stroj má konečnou sadu stavů, ve kterých může být stroj. Turingův stroj má nekonečně dlouhou pásku, která je rozdělena na čtverce. Na každém čtverci pásky je symbol nakreslený z konečné sady symbolů. Turingův stroj kdykoli ve výpočtu čte symbol na jednom čtverci pásky. Turingův stroj může tento symbol nahradit jiným symbolem a přesunout se na čtverec vpravo nebo na čtverec vlevo. Akce, kterou Turingův stroj provede, je automaticky určena stavem, ve kterém se stroj nachází. Poté, co proběhne náhradní symbol a přesun na jinou čtvercovou akci, může Turingův stroj přejít do jiného stavu. Každý jiný stát má jinou sadu pravidel o tom, jak nahradit symboly a kterým směrem se pohybovat.
Vzácná fyzická implementace návrhu Turingova stroje (bez nekonečné pásky)
Kanonická formulace Turingova stroje se obvykle skládá z binární abecedy výhradně s 0 a 1 s. Tato formulace odpovídá intuici moderních počítačových programátorů, protože všechny moderní počítače používají binární. Ve skutečnosti jsou Turingovy stroje neutrální, pokud jde o velikost abecedy symbolů. Turingův stroj může také použít jakýkoli symbol, ať už číselný nebo nakreslený z jakéhokoli jiného typu abeced, jako jsou obrazové symboly nebo latinka. Jakákoli formulace každé možné konečné abecedy je prokazatelně redukovatelná na binární Turingův stroj.
Turingovy stroje předpokládají, že je k dispozici nekonečné množství paměti. Žádný skutečný fyzicky vytvořený stroj nedokáže splnit tento požadavek být Turingovým strojem. Turingův stroj také předpokládá, že výpočtem funkce lze strávit potenciálně nekonečné množství času. Tyto předpoklady byly vytvořeny ke generování nejrozsáhlejší třídy možných funkcí pro Turingovu definici vypočítatelných funkcí. Turingovy vypočítatelné funkce jsou jakékoli funkce, které lze vypočítat pomocí Turingova stroje. Mnoho z těchto vypočítatelných funkcí nemusí být nikdy vypočítatelné žádným fyzicky vytvořeným strojem, protože vyžadují příliš mnoho času nebo paměti.
Církevní Turingova práce tvrdí rovnocennost vypočítatelných funkcí a funkcí, které lze vypočítat pomocí Turingova stroje. To znamená, že všechny funkce, které nelze vypočítat Turingovými stroji, nelze vypočítat jinou metodou. David Hilbert očekával kladnou odpověď na problém Entscheidungs, což by znamenalo, že všechny problémy lze vypočítat. Výsledek Turinga vedl k objevení mnoha nepočitatelných problémů.
Nejznámějším nepočítatelným problémem je problém zastavení. Problém zastavení je problém vytvoření algoritmu, který může obecně rozhodnout, zda se počítačový program s jeho vstupem zastaví nebo bude pokračovat navždy. I když existují konkrétní případy, kdy lze problém zastavení zastavit, nelze jej vyřešit u každého počítačového programu s jakýmkoli vstupem. Tento výsledek měl důležité důsledky pro počítačové programování, protože počítačoví programátoři si musí být vědomi možnosti nekonečných smyček a nemožnosti detekovat všechny nekonečné smyčky před spuštěním svých programů.
Dalším důsledkem Turingova stroje je možnost univerzálních Turingových strojů. Implicitní v Turingově designu je koncept ukládání programu, který upravuje data vedle dat, která upravuje. To navrhlo možnost univerzálních a přeprogramovatelných počítačů. Moderní počítače jsou obvykle univerzální Turingovy stroje v tom smyslu, že je lze naprogramovat tak, aby provozovaly jakýkoli algoritmus. To eliminovalo potřebu jiného hardwaru pro každý potenciální počítačový program a zavedlo rozlišení hardware / software.
Model Turingova stroje přímo vedl k vynálezu počítačů, ale nejedná se o stejný plán, jaký se používá při konstrukci moderních počítačů. Architektura von Neumann použitá jako plán pro moderní počítače využívá koncept uloženého programu implicitně v modelu Turingova stroje, ale liší se od zbytku modelu Turingova stroje několika důležitými způsoby. Největší rozdíly spočívají v tom, že architektura von Neumann nepoužívá čtecí a zapisovací hlavu a místo toho obsahuje více registrů, paměť s náhodným přístupem, datové sběrnice, malou sadu základních strojových instrukcí a možnosti zpracování několika bitů. Architektura von Neumann také výslovně umožňuje speciální vstupní a výstupní zařízení, jako jsou klávesnice a monitory.
Model Turingova stroje byl prvním matematickým modelem výpočtu. Vedlo to přímo k vynálezu fyzických počítačů. Fyzické počítače mají všechny stejné schopnosti, jaké mají Turingovy stroje, za předpokladu omezené paměti a časových omezení skutečného výpočtu. Turingova formulace stále hraje ústřední roli ve studiu výpočtu. Počítačoví vědci se stále aktivně podílejí na výzkumu, zda jsou konkrétní funkce vypočítatelné Turingovými stroji.
