Teorie výpočtu - Theory of computation

Umělecké ztvárnění Turingova stroje . Turingovy stroje se často používají jako teoretické modely pro výpočetní techniku.

V teoretické informatice a matematice je teorie výpočtu obor, který se zabývá tím, jaké problémy lze vyřešit na modelu výpočtu pomocí algoritmu , jak efektivně je lze vyřešit nebo do jaké míry (např. Přibližná řešení oproti přesným ). Pole se dělí do tří hlavních větví: teorie automatů a formálních jazyků , teorie vyčíslitelnosti a výpočetní složitosti teorie , které jsou propojeny na otázku: „Jaké jsou základní možnosti a omezení počítačů“.

Aby mohli počítačoví vědci provést rigorózní studii výpočtu, pracují s matematickou abstrakcí počítačů, která se nazývá model výpočtu . Používá se několik modelů, ale nejčastěji zkoumaným je Turingův stroj . Počítačoví vědci studují Turingův stroj, protože se snadno formuluje, lze jej analyzovat a použít k prokázání výsledků a protože představuje to, co mnozí považují za nejsilnější možný „rozumný“ model výpočtu (viz práce Church – Turing ). Mohlo by se zdát, že potenciálně nekonečná kapacita paměti je nerealizovatelný atribut, ale jakýkoli rozhodnutelný problém vyřešený Turingovým strojem bude vždy vyžadovat pouze konečné množství paměti. V zásadě tedy jakýkoli problém, který lze vyřešit (rozhodnout) pomocí Turingova stroje, může vyřešit počítač, který má omezené množství paměti.

Dějiny

Za teorii výpočtu lze považovat tvorbu modelů všeho druhu v oblasti informatiky. Proto se používá matematika a logika . V minulém století se stala nezávislou akademickou disciplínou a byla oddělena od matematiky.

Někteří průkopníci teorie výpočtu byli Ramon Llull , Alonzo Church , Kurt Gödel , Alan Turing , Stephen Kleene , Rózsa Péter , John von Neumann a Claude Shannon .

Pobočky

Teorie automatů

Gramatika Jazyky Automat Pravidla produkce (omezení)
Typ-0 Rekurzivně vyčíslitelné Turingův stroj (bez omezení)
Typ-1 Citlivý na kontext Lineárně ohraničený nedeterministický Turingův stroj
Typ-2 Bez kontextu Non-deterministický zásobníkový automat
Typ-3 Pravidelný Konečný automat
a

Teorie automatů je studium abstraktních strojů (nebo vhodněji abstraktních „matematických“ strojů nebo systémů) a výpočetních problémů, které lze pomocí těchto strojů vyřešit. Tyto abstraktní stroje se nazývají automaty. Automata pochází z řeckého slova (Αυτόματα), což znamená, že něco dělá něco samo. Teorie automatů je také úzce spjata s teorií formálních jazyků , protože automaty jsou často klasifikovány podle třídy formálních jazyků, které jsou schopni rozpoznat. Automat může být konečnou reprezentací formálního jazyka, který může být nekonečnou množinou. Automaty se používají jako teoretické modely pro výpočetní stroje a slouží k důkazům o vyčíslitelnosti.

Formální teorie jazyka

Chomského hierarchie
Nastavte inkluze popsané Chomského hierarchií

Teorie jazyka je obor matematiky zabývající se popisem jazyků jako množinou operací nad abecedou . Je úzce spojena s teorií automatů, protože automaty se používají ke generování a rozpoznávání formálních jazyků. Existuje několik tříd formálních jazyků, z nichž každý umožňuje složitější jazykovou specifikaci než ta před ním, tj. Chomského hierarchie , a každá odpovídá třídě automatů, které ji rozpoznávají. Protože jako modely pro výpočet se používají automaty, jsou upřednostňovaným způsobem specifikace pro jakýkoli problém, který je třeba vypočítat, formální jazyky.

Teorie výpočetnosti

Teorie výpočetnosti se zabývá především otázkou, do jaké míry je problém řešitelný na počítači. Tvrzení, že problém zastavení nelze vyřešit Turingovým strojem, je jedním z nejdůležitějších výsledků v teorii vyčíslitelnosti, protože je příkladem konkrétního problému, který je jak snadno formulovat, tak i nemožné vyřešit pomocí Turingova stroje. Velká část teorie vyčíslitelnosti staví na výsledku zastavení problému.

Dalším důležitým krokem v teorii vyčíslitelnosti byla Riceova věta , která uvádí, že pro všechny netriviální vlastnosti dílčích funkcí je nerozhodné, zda Turingův stroj s touto vlastností vypočítá částečnou funkci.

Teorie vyčíslitelnosti je úzce spjata s oborem matematické logiky nazývaným teorie rekurze , který odstraňuje omezení studia pouze modelů výpočtu, které jsou redukovatelné na Turingův model. Mnoho matematiků a teoretiků výpočetní techniky, kteří studují teorii rekurze, ji bude označovat jako teorii vypočítatelnosti.

Teorie výpočetní složitosti

Reprezentace vztahu mezi třídami složitosti

Teorie složitosti zvažuje nejen to, zda lze problém na počítači vůbec vyřešit, ale také to, jak efektivně lze problém vyřešit. Jsou zvažovány dva hlavní aspekty: časová složitost a složitost prostoru, což je počet kroků potřebných k provedení výpočtu a kolik paměti je k provedení tohoto výpočtu zapotřebí.

Aby bylo možné analyzovat, kolik času a prostoru daný algoritmus vyžaduje, počítačoví vědci vyjadřují čas nebo prostor potřebný k vyřešení problému jako funkci velikosti vstupního problému. Například nalezení konkrétního čísla v dlouhém seznamu čísel se stává obtížnějším, protože seznam čísel se zvětšuje. Pokud řekneme, že v seznamu je n čísel, pak pokud seznam není nijak seřazen nebo indexován, možná se budeme muset podívat na každé číslo, abychom našli číslo, které hledáme. Říkáme tedy, že k vyřešení tohoto problému musí počítač provést řadu kroků, které lineárně rostou s velikostí problému.

Aby se tento problém zjednodušil, počítačoví vědci přijali notaci Big O , která umožňuje porovnávat funkce způsobem, který zajišťuje, že není třeba zvažovat konkrétní aspekty konstrukce stroje, ale spíše jen asymptotické chování, protože problémy se stávají velkými. V našem předchozím příkladu bychom tedy mohli říci, že problém vyžaduje kroky k vyřešení.

Snad nejdůležitějším otevřeným problémem celé informatiky je otázka, zda lze určitou širokou třídu problémů označovaných NP efektivně řešit. Toto je dále diskutováno ve třídách složitosti P a NP a problém P versus NP je jedním ze sedmi problémů s cenou tisíciletí, které uvedl Clay Mathematics Institute v roce 2000. Oficiální popis problému poskytl vítěz Turingovy ceny Stephen Cook .

Modely výpočtu

Kromě Turingova stroje se používají další ekvivalentní (viz: Church – Turingova teze ) modely výpočtu.

Lambda kalkul
Výpočet se skládá z počátečního výrazu lambda (nebo dvou, pokud chcete oddělit funkci a její vstup) plus konečné sekvence lambda výrazů, z nichž každý je odvozen z předchozího výrazu jednou aplikací redukce beta .
Kombinační logika
je koncept, který má mnoho podobností s -calculus, ale také existují důležité rozdíly (např. kombinátor pevného bodu Y má normální formu v kombinační logice, ale ne v -calculus). Kombinační logika byla rozvíjena s velkými ambicemi: porozumět povaze paradoxů, učinit základy matematiky ekonomičtějšími (koncepčně), eliminovat pojem proměnných (vyjasnit tak jejich roli v matematice).
μ-rekurzivní funkce
výpočet se skládá z rekurzivní funkce mu, tj. z její definující sekvence, libovolných vstupních hodnot a sekvencí rekurzivních funkcí, které se objevují v definující sekvenci se vstupy a výstupy. Pokud tedy v definující posloupnosti rekurzivní funkce fungují funkce a objeví se, pak by se mohly objevit termíny tvaru 'g (5) = 7' nebo 'h (3,2) = 10'. Každý záznam v této sekvenci musí být aplikací základní funkce nebo musí vyplývat z výše uvedených záznamů pomocí kompozice , primitivní rekurze nebo μ rekurze . Pokud například pro zobrazení 'f (5) = 3' musí nastat výrazy jako 'g (5) = 6' a 'h (5,6) = 3'. Výpočet končí pouze v případě, že konečný výraz udává hodnotu rekurzivní funkce aplikované na vstupy.
Markovův algoritmus
řetězec přepisování systém , který používá gramatiky like pravidla pro provoz na řetězce symbolů.
Zaregistrujte stroj
je teoreticky zajímavá idealizace počítače. Existuje několik variant. Ve většině z nich může každý registr obsahovat přirozené číslo (neomezené velikosti) a pokyny jsou jednoduché (a málo), např. Existuje pouze dekrementace (kombinovaná s podmíněným skokem) a inkrementace (a zastavení). Nedostatek nekonečného (nebo dynamicky rostoucího) externího úložiště (viděný u Turingových strojů) lze pochopit nahrazením jeho role Gödelovými číslovacími technikami: skutečnost, že každý registr obsahuje přirozené číslo, umožňuje představovat složitou věc (např. sekvence nebo matice atd.) příslušným obrovským přirozeným číslem - jednoznačnost reprezentace a interpretace lze stanovit pomocí číselně teoretických základů těchto technik.

Kromě obecných výpočetních modelů jsou pro speciální omezené aplikace užitečné některé jednodušší výpočetní modely. Regulární výrazy například určují vzory řetězců v mnoha kontextech, od softwaru pro kancelářskou produktivitu až po programovací jazyky . Další formalismus matematicky ekvivalentní regulárním výrazům, konečné automaty se používají při návrhu obvodů a při některých druzích řešení problémů. Gramatiky bez kontextu určují syntaxi programovacího jazyka. Non-deterministické zásobníkové automaty jsou další formalizmus ekvivalentní bezkontextových gramatik. Primitivní rekurzivní funkce jsou definovanou podtřídou rekurzivních funkcí.

Různé modely výpočtu mají schopnost provádět různé úkoly. Jedním ze způsobů, jak změřit sílu výpočetního modelu, je studovat třídu formálních jazyků, které model dokáže generovat; tak se získá Chomského hierarchie jazyků.

Reference

Další čtení

Učebnice zaměřené na informatiky

(V této oblasti existuje mnoho učebnic; tento seznam je nutně neúplný.)

Knihy o teorii vyčíslitelnosti z (širší) matematické perspektivy
Historická perspektiva

externí odkazy