Mých oblíbených autorů (David Deutsch, Roger Penrose, a Douglas Hofstadter) všechny ponořit do Church-Turingova Teze Výpočetní Teorie, a co je důležitější, jeho nejsilnější výklad: Turingův Principu. V tomto příspěvku nejprve vysvětlím Church-Turingovu tezi laicky.
když jsem pracoval na svém oboru informatiky, studoval jsem Turingovy stroje a Church-Turingovu práci v mém úvodu do třídy výpočetní teorie. Tehdy jsem si myslel, že je to velká ztráta času. Chtěl jsem jen programovat počítače a nemohl jsem se starat méně o tento dávno mrtvý Turingův chlap (ani tento církevní chlap) ani o jeho hloupé teoretické stroje.
Nyní, když chápu filozofické důsledky církevně-Turingovy teze, přál bych si, abych ve třídě věnoval pozornost! Protože Church-Turingova teze, pokud je pravdivá, má některé hluboké filozofické důsledky a může nám také říci něco o hluboké — a zvláštní-povaze reality.
konečné automaty
všechny texty a třídy o teorii výpočtu začínají něčím, co se nazývá “ konečné automaty.“Základní myšlenka za nimi je docela snadná. Jen si představte jednoduchý „stroj“, který je schopen rozhodovat a pohybovat se mezi státy. Zde je příklad velmi jednoduchého, který představuje „logiku“ turniketu ovládaného mincemi.
V jednoduché angličtině to říká, že pokud se pokusíte, aby se zasadila přes turniket, který je uzamčen, nemůžete, pokud nemáte první vhoď minci. Pokud jste vložili minci, ale ještě jste ji neprosadili, další mince ji nechte v odemčeném stavu. Pokud jste vložili minci, můžete se prosadit. Poté se znovu zamkne pro další osobu.
bylo to pravděpodobně snazší pochopit z diagramu než z popisu.
konečné automaty jsou schopny provádět mnohem složitější logiku, než je tato. Ale to by vám mělo poskytnout základní představu o tom, jak fungují konečné automaty.
Jedna věc k poznámce je, že konečný automat, jako ten výše, je čistě teoretická, protože existuje pouze jako banda bubliny a čáry na kus papíru. Není to tak, že by uvnitř turniketu byl nějaký malý „konečný automat“, který dělá tato rozhodnutí. Nebo bych měl místo toho říci, že turniket sám o sobě je konečný automat.
pokud bychom opravdu chtěli, mohli bychom pravděpodobně postavit stroj v reálném životě, který by byl konečným automatem.Tam je nic zastavit někdo od budovy je jako skutečný stroj v reálném životě, a pak instalaci do turniketu. To prostě není nejlevnější způsob, jak to udělat.
Takže jakékoliv ‚program‘ uděláte jako kresbu konečný automat může být obrácená do skutečného života „výpočet“, který opravdu funguje. Význam rozdílu mezi výpočetním strojem, který může skutečně existovat (jako konečný automat), a strojem, který je pouze hypotetický a porušuje fyzikální zákony, se stává důležitým v okamžiku.
Více Výkonné Stroje
Jako třída ve výpočetní teorie postupuje, jsou studenti uvedeni do stále složitějších ‚stroje‘, které jsou silnější než Konečných Automatů. Jak ukazuje obrázek vpravo, dalším nejsilnějším je Pushdown automaty (PDA). PDA je opravdu jen DFA s přidáním jakési „paměti“. Tato paměť umožňuje PDA vytvořit a spustit výpočty (nebo programy), které DFA nemůže.
klíčový bod je jen to, že existují určité typy programů, které mohou být napsané pro PDA, které nemohou být zapsány na Deterministický Konečný Automat (DFA). Jinými slovy Pda je ‚silnější‘ než DFAs, protože oni mohou vyjádřit tříd „programy“, které DFAs nemůže.
Takže existuje vztah mezi DFAs a Pda z hlediska „výpočetní síly.“Konkrétně je možné prokázat, že jakýkoli program napsaný na DFA může být také napsán na PDA, ale opak není pravdou.
Důkaz je Důkaz,
důkaz, že PDA lze spustit nic, že DFA mohou se provádí tím, že se schéma, které z logiky DFA mohou být mapovány na PDA. Vzhledem k tomu, že PDA je pouze DFA s pamětí — není to těžké – prostě nepoužívejte „funkci paměti“.
ale co naopak? Můžeme dokázat, že je nemožné vzít určité typy „programů“ napsaných pro PDA a přeložit je do DFA? To znamená, že existuje důkaz, že Pushdown automaty nelze mapovat na konečné automaty? Nebo jen předpokládáme, že konečné automaty jsou méně výkonné než Pushdown automaty, protože v současné době nevíme o způsobu, jak zmapovat PDA zpět na FDA? Možná existuje způsob, jak mapovat PDA na FDA a možná nikdo ještě nezjistil, jak to udělat? Není to alespoň možnost?
jak se ukázalo, je možné prokázat, že PDA může spouštět určité typy programů, které DFA nemůže. Způsob, jakým to uděláte, je, že najdete výpočet (tj. program), který můžete dokázat, že DFA nemůže vypočítat, a pak prokázat, že PDA to dokáže vypočítat.
Výpočetní Výkon Stroje
Tato skutečnost — že tam jsou silnější (PDA) a méně výkonný (DFA) logické stroje — je zajímavé samo o sobě.
ale vede to k filozofické otázce: existuje něco jako “ nejvýkonnější výpočetní stroj?“
kdyby existoval takový „nejsilnější stroj“, jak bychom věděli, že jakýkoli konkrétní navrhovaný stroj je “ nejsilnější?“Nebo jsou k dispozici jen různé typy výpočetních strojů a musíte si vybrat ten správný pro tuto práci?
Turingovy stroje
takže jaký stroj je výkonnější než PDA?
jak by to historie měla, přibližně ve stejnou dobu byly navrženy dva velmi odlišné typy „strojů“, které byly prokazatelně silnější než PDA.
jedním z nich byl Turingův stroj Alana Turinga. Druhý nebyl ani tak stroj jako chytrá sada notací vyvinutých Alonzo Churchem, která sloužila stejnému účelu jako vývoj stroje. Z těchto dvou „strojů“ je Turingův stroj koncepčně jednodušší, takže obvykle je to stroj, který se vyučuje v kurzu výpočetní teorie.
Turingovy stroje jsou zábavné malé teoretické stroje, které mají čtecí / zapisovací hlavu a (hypotetickou) papírovou pásku, ze které může číst nebo zapisovat. Na základě toho, co Turingův Stroj čte se to dá Turingův Stroj do akce státu, který provádí nějaký druh kombinace úkolů, skládající se buď pohybují čtecí/zapisovací hlavy vpřed nebo vzad, čtení z nové pozice na pásku, nebo psaní, takže nová pozice na pásku. Turingův stroj vypadá takto:
Turingovy Stroje a Moderní Počítače
Jedna zajímavá věc je, že Turingův Stroj je, i přes povrch vystoupení, vlastně docela podobně jako moderní počítač. V moderním počítači je centrální procesorová jednotka (CPU) ekvivalentní čtecí/zapisovací hlavě Turingova stroje. Paměťové čipy (RAM nebo ROM) jsou velmi podobné buňkám dlouhé papírové pásky, ze které může soustružnický stroj číst nebo zapisovat. Zdá se tedy, že moderní počítače jsou zhruba ekvivalentní stroji Turing.
moderní počítač má oproti Turingovu stroji jednu výhodu. Moderní počítač se nemusí pohybovat z jedné buňky své „paměti“ v sekvenčním pořadí, jako to dělá Turingův stroj.
skutečnost, že Turingův stroj může pohybovat pouze jednou buňkou najednou, se jeví jako významné omezení,že? Právě jsme viděli, jak jsou některé stroje logicky „výkonnější“ než jiné: PDA může provádět výpočetní úkoly, které FDA nemůže. Takže možná existují stroje, které jsou výkonnější než Turingovy stroje, které mohou provádět úkoly, které Turingovy stroje nemohou? A možná moderní počítač — díky své schopnosti skákat kolem paměti, spíše než se muset pohybovat z buňky do buňky postupně-může spustit některé programy, které Turingův stroj nemůže?
moderní počítač má ve skutečnosti méně výraznou sílu než Turingův stroj, protože Turingovy stroje byly koncipovány jako nekonečně dlouhé papírové pásky (tj. nekonečná paměť), kde jako skutečný počítač bude mít vždy konečnou paměť. Nicméně, obecně to je velmi malý rozdíl v tom, jaké typy výpočtů lze provést, protože lidské bytosti nejsou obecně všechny, které zajímá nekonečně dlouhé výpočty, které dávají nekonečně dlouho výsledky. Proto říkám, že moderní počítače a Turingovy stroje jsou „zhruba“ rovnocenné. Ve skutečnosti, pokud předpokládáte libovolnou, ale konečnou velikost paměti, jsou přesně rovnocenné, pokud jde o to, jaké typy programů mohou spustit.
Church Turing teze: Turingův stroj = Max logický výkon
ale co chudý Alonzo Kostel? Jeho ubohý malý „stroj“ zapomněl, protože Turingovy stroje se snadněji učí. Je jeho stroj možná schopen vyjádřit některé výpočty / programy, které Turingův stroj nemůže, nebo naopak?
nebyla By to hvězdná náhoda, kdyby to jen tak se stalo, že Alan Turing a Alonzo Church jen tak se stalo, vytvořit dva zcela odlišné typy teoretických výpočtů strojů a to jen tak se stalo, že byly přesně totožné, pokud jde o jaké typy výpočty mohli provést?
Takže si představte to překvapení pro všechny, když Alan Turing byl schopen předložit doklad, že každý program napsaný pro Turingův Stroj, by mohlo být také napsáno pro Církev stroj, a také důkaz, že každý program napsaný pro Kostel stroj mohl také být napsán pro Turingův stroj.
ve skutečnosti existuje řada navržených typů teoretických výpočetních strojů. Například, teoretici snažili umožňuje Turingův Stroj s více páskami na číst/psát. Dokonce se pokusili umožnit Turingovu stroji 2-dimenzionální „list“číst a psát. Teoretici zkoušeli nejrůznější vylepšení Turingových strojů (a církevních strojů).
a dosud bylo možné pro každého z nich předložit důkaz, že jsou ekvivalentní jednoduchému Turingovu stroji.
to vypadá jako divoká náhoda, že? A byla by to divoká náhoda, pokud neexistuje horní hranice omezená na to, jaké typy výpočtů lze provést.
Jestli tam je tak horní hranice, pak by to být náhoda, vůbec, že Turingův Stroj a Kostel Stroje a veškeré další výpočetní stroje navrhované náhodou mají stejnou výpočetní sílu, protože ve skutečnosti důvod, proč jsou všechny ekvivalentní, protože jsme dosáhli horní hranice výpočetní výkon.
Ale můžeme dokázat, že tam není nějaký výpočetní stroj tam — ten, který jsme ještě neobjevili — že má schopnost provádět výpočty, že Turingův Stroj nemůže?
jak přesně bychom takový důkaz předložili? Faktem je, že nemůžeme dokázat, že není nic silnějšího než Turingův stroj. Takže, kdo ví, možná existuje.
ale faktem je, že nemůžeme najít (nebo vymyslet) žádné takové stroje.
takže po značném úsilí a neúspěchu, najít způsob, jak zlepšit sílu Turingových strojů, byla nakonec Church-Turingova teze přijata, i když se neprokázalo, že je pravdivá. Church-Turing teze v podstatě říká něco takového:
To je není možné přijít s nějakou výpočetní stroj, který může vykonávat logiku programu, že starý Turingův Stroj nemůže.
Nebo jinými slovy:
Turingovy Stroje a jejich ekvivalenty jsou nejsilnější možné typy výpočetních strojů a nejsou tam žádné silnější, ty, tam venku, které jsme prostě nevím, o dosud.
po letech a letech výzkumu této práce tato práce stále v podstatě platí. Uvidíme později, že došlo k poněkud modifikaci práce se zavedením teoretických kvantových počítačů. V podstatě však teze platí dodnes. Nikdo nikdy nepřišel na způsob, jak překonat Turingovy stroje, pokud jde o logickou expresivitu. Turingovy stroje jsou stále úřadujícím šampionem.
takže nyní chápete Church-Turingovu tezi. Church-Turingova teze však není zcela ekvivalentní Turingovu principu. Takže v budoucím příspěvku budu rozvíjet, jaký je rozdíl a jaké jsou to filozofické důsledky.
Poznámky
Turingův Princip. Tak pojmenoval Roger Penrose, který tomu nevěří (alespoň ne v současné podobě). Do Turing-Deutschova principu ji vyvinul David Deutsch, který v ni věří, alespoň ve své podobě.) (Viz článek ve Wikipedii pro více informací)