Phenquestions
Turingov stroj je ústredný teoretický konštrukt v informatike. Turingov stroj je abstraktný matematický model výpočtu. Používanie Turingových strojov pomáha vysvetliť, čo je výpočet, vymedzením takzvaných „vypočítateľných funkcií“.“
Počiatočný výskum logiky Alana Turinga sa zameral na slávny nevyriešený problém známy ako Entscheidungsproblem. Entscheidungsproblem (zhruba preložený z nemčiny ako problém rozhodnutia) navrhol filozof a matematik David Hilbert v roku 1928. Problém sa pýtal, či existuje algoritmus, ktorý rozhoduje o každom výroku vo formálnom jazyku.
Formálny jazyk je systém axiómov a odvodzovacích pravidiel, aké sú napríklad v aritmetike alebo logike prvého rádu. Axiómy môžu byť akékoľvek symboly a odvodzovacími pravidlami môže byť akýkoľvek zoznam pravidiel pre manipuláciu s týmito symbolmi. „Rozhodovanie o každom výroku“ znamenalo buď výstup, či bol výrok pravdivý / nepravdivý, alebo výstupný údaj, či je výrok odvoditeľný / nedefinovateľný. Veta o úplnosti Kurta Godla dokázala, že algoritmus rozhodujúci o platnosti je ekvivalentný s efektívnym postupom rozhodujúcim o odvoditeľnosti. Dokument Alana Turinga z roku 1936 „O vypočítateľných číslach s aplikáciou na problém Entscheidungs“ ukázal negatívny výsledok, že nebolo možné algoritmicky rozhodnúť o každom výroku vo formálnom systéme.
Alan Turing
Aby Turing dokázal negatívny výsledok pre problém Entscheidungs, bolo potrebné formalizovať predstavu algoritmu. Turingovou formalizáciou algoritmu bol matematický model výpočtu, ktorý sa neskôr stal známym ako Turingov stroj. Turingov stroj má konečnú množinu stavov, v ktorých sa stroj môže nachádzať. Turingov stroj má nekonečne dlhú pásku, ktorá je rozdelená na štvorce. Na každom štvorci pásky je symbol nakreslený z konečnej sady symbolov. Kedykoľvek vo výpočte Turingov stroj číta symbol na jednom štvorci pásky. Turingov stroj môže nahradiť tento symbol iným symbolom a presunúť sa buď na štvorec napravo alebo na štvorec vľavo. Činnosť, ktorú Turingov stroj vykonáva, je automaticky určená stavom, v ktorom sa nachádza. Po uskutočnení náhradného symbolu a prechode na inú štvorcovú akciu môže Turingov stroj prejsť do iného stavu. Každý iný štát má inú sadu pravidiel, ako nahradiť symboly a ktorým smerom sa posunúť.
Zriedkavé fyzické prevedenie návrhu Turingovho stroja (bez nekonečnej pásky)
Kanonická formulácia Turingovho stroja sa zvyčajne skladá z binárnej abecedy výlučne s 0 a 1 s. Táto formulácia zodpovedá intuícii moderných počítačových programátorov, pretože všetky moderné počítače používajú binárne súbory. Turingove stroje sú v skutočnosti neutrálne, pokiaľ ide o veľkosť abecedy symbolov. Turingov stroj môže tiež používať akýkoľvek symbol, či už číselný, alebo nakreslený z iného typu abecedy, ako sú napríklad obrazové symboly alebo latinská abeceda. Akákoľvek formulácia každej možnej konečnej abecedy je dokázateľne redukovateľná na binárny Turingov stroj.
Turingove stroje predpokladajú, že je k dispozícii nekonečné množstvo pamäte. Žiadny skutočný fyzicky inštančný stroj nemôže splniť túto požiadavku byť Turingovým strojom. Turingov stroj tiež predpokladá, že výpočtom funkcie možno stráviť potenciálne nekonečné množstvo času. Tieto predpoklady boli urobené na vygenerovanie najrozsiahlejšej triedy možných funkcií pre Turingovu definíciu vypočítateľných funkcií. Vypočítateľné funkcie Turinga sú akékoľvek funkcie, ktoré môže vypočítať Turingov stroj. Mnohé z týchto vypočítateľných funkcií nemusí byť možné vypočítať na žiadnom fyzicky vytvorenom stroji, pretože vyžadujú príliš veľa času alebo pamäte.
Cirkevná Turingova práca tvrdí rovnocennosť vypočítateľných funkcií a funkcií, ktoré je možné vypočítať Turingovým strojom. To znamená, že všetky funkcie, ktoré nie sú vypočítateľné Turingovými strojmi, nemožno vypočítať inou metódou. David Hilbert očakával kladnú odpoveď na problém Entscheidungs, čo by znamenalo, že všetky problémy sú vypočítateľné. Výsledok Turinga viedol k objaveniu mnohých nevypočítateľných problémov.
Najznámejším nepočítateľným problémom je Halting Problem. Problém zastavenia je problém vytvorenia algoritmu, ktorý vo všeobecnom prípade môže rozhodnúť, či sa počítačový program s jeho vstupom zastaví alebo bude pokračovať navždy. Aj keď existujú konkrétne prípady, keď je možné problém zastavenia vyriešiť, nie je možné ho vyriešiť pre každý počítačový program s akýmkoľvek vstupom. Tento výsledok mal dôležité dôsledky na počítačové programovanie, pretože počítačoví programátori si musia byť vedomí možnosti nekonečných slučiek a nemožnosti detekovať všetky nekonečné slučky pred spustením svojich programov.
Ďalším dôsledkom Turingovho stroja je možnosť univerzálnych Turingových strojov. V Turingovom dizajne je implicitný koncept ukladania programu, ktorý upravuje údaje, spolu s údajmi, ktoré upravuje. To naznačovalo možnosť univerzálnych a preprogramovateľných počítačov. Moderné počítače sú zvyčajne univerzálne Turingove stroje v tom zmysle, že je možné ich naprogramovať na vykonávanie ľubovoľných algoritmov. To eliminovalo potrebu iného hardvéru pre každý potenciálny počítačový program a zaviedlo rozlíšenie medzi hardvérom a softvérom.
Model Turingovho stroja priamo viedol k vynálezu počítačov, nejde však o rovnaký návrh, aký sa používal pri konštrukcii moderných počítačov. Von Neumannova architektúra použitá ako plán pre moderné počítače využíva koncept uloženého programu implicitne obsiahnutý v modeli Turingovho stroja, ale od ostatných modelov Turingovho stroja sa líši niekoľkými dôležitými spôsobmi. Najväčšie rozdiely spočívajú v tom, že architektúra von Neumann nepoužíva čítaciu a zapisovaciu hlavu a namiesto toho obsahuje viac registrov, pamäť s náhodným prístupom, dátové zbernice, malú sadu základných inštrukcií o stroji a možnosti spracovania viacerých bitov. Architektúra von Neumann tiež výslovne umožňuje špeciálne vstupné a výstupné zariadenia, ako sú klávesnice a monitory.
Model Turingovho stroja bol prvým matematickým modelom výpočtu. To viedlo priamo k vynálezu fyzických počítačov. Fyzické počítače majú všetky rovnaké schopnosti ako Turingove stroje, za predpokladu obmedzenej pamäte a časového obmedzenia skutočného výpočtu. Turingova formulácia stále zohráva ústrednú úlohu pri štúdiu výpočtu. Počítačoví vedci sa stále aktívne podieľajú na výskume, či sú Turingovými strojmi vypočítateľné konkrétne funkcie.
