Charakterizace algoritmů - Algorithm characterizations

Charakterizace algoritmů jsou pokusy o formalizaci algoritmu slova . Algoritmus nemá obecně přijímanou formální definici. Vědci na tomto problému aktivně pracují. Tento článek podrobněji představí některé „charakterizace“ pojmu „algoritmus“.

Problém definice

Za posledních 200 let se definice algoritmu stala komplikovanější a podrobnější, protože se vědci snažili tento pojem přesněji definovat. Ve skutečnosti může existovat více než jeden typ „algoritmu“. Ale většina souhlasí s tím, že algoritmus má něco společného s definováním zobecněných procesů pro vytváření celých „výstupních“ čísel z jiných „vstupních“ celých čísel - „vstupních parametrů“ libovolných a nekonečných v rozsahu, nebo omezených v rozsahu, ale stále proměnných - manipulací s rozlišitelné symboly (počítající čísla) s konečnými sbírkami pravidel, která může člověk provádět s papírem a tužkou.

Nejběžnější schémata manipulace s čísly - jak ve formální matematice, tak v rutinním životě - jsou: (1) rekurzivní funkce vypočítané osobou s papírem a tužkou a (2) Turingův stroj nebo jeho Turingovy ekvivalenty - primitivní registr - model stroje nebo „pultového stroje“, model stroje s náhodným přístupem (RAM), model stroje s náhodným přístupem s uloženým programem (RASP) a jeho funkční ekvivalent „ počítač “.

Když děláme „aritmetiku“, skutečně počítáme pomocí „rekurzivních funkcí“ v zkratkových algoritmech, které jsme se naučili na základní škole, například sčítáním a odčítáním.

Důkazy, že každou „rekurzivní funkci“, kterou můžeme vypočítat ručně, můžeme vypočítat strojem a naopak - všimněte si použití slov vypočítat versus vypočítat - jsou pozoruhodné. Ale tato ekvivalence spolu s tezí (neprokázaným tvrzením), která zahrnuje každý výpočet / výpočet, naznačuje, proč byl při definici konkrétních algoritmů kladen tak velký důraz na použití Turingových ekvivalentních strojů a proč samotná definice „algoritmu“ často odkazuje zpět na „ Turingův stroj “. Toto je podrobněji popsáno v rámci charakterizace Stephena Kleena .

Následuje shrnutí slavnějších charakterizací (Kleene, Markov, Knuth) spolu s těmi, které zavádějí nové prvky - prvky, které dále rozšiřují definici nebo přispívají k přesnější definici.

[ Matematický problém a jeho výsledek lze považovat za dva body v prostoru a řešení se skládá z posloupnosti kroků nebo cesty, která je spojuje. Kvalita řešení je funkcí cesty. Pro cestu může být definováno více než jeden atribut, např. Délka, složitost tvaru, snadnost zobecnění, obtížnost atd . ]

Chomského hierarchie

Existuje větší shoda ohledně „charakterizace“ pojmu „jednoduchý algoritmus“.

Všechny algoritmy je třeba specifikovat ve formálním jazyce a „pojem jednoduchosti“ vychází z jednoduchosti jazyka. Hierarchie Chomsky (1956) je hierarchie omezování tříd formálních gramatik , které vytvářejí formální jazyky . Používá se pro klasifikaci z programovacích jazyků a abstraktními strojů .

Z hlediska Chomského hierarchie , pokud lze algoritmus specifikovat pro jednodušší jazyk (než neomezený), lze jej charakterizovat tímto druhem jazyka, jinak se jedná o typický „neomezený algoritmus“.

Příklady: „obecný“ makro jazyk, jako je M4, je neomezený ( Turing dokončen ), ale makro jazyk preprocesoru C není, takže jakýkoli algoritmus vyjádřený v preprocesoru C je „jednoduchý algoritmus“.

Viz také Vztahy mezi třídami složitosti .

Vlastnosti dobrého algoritmu

Níže jsou uvedeny vlastnosti dobrého algoritmu;

  • Přesnost: dobrý algoritmus musí mít určité nastíněné kroky. Kroky by měly být dostatečně přesné a neměly by se lišit.
  • Jedinečnost: každý krok provedený v algoritmu by měl poskytnout definitivní výsledek, jak uvádí autor algoritmu. Výsledky by neměly v žádném případě kolísat.
  • Proveditelnost: Algoritmus by měl být možný a proveditelný v reálném životě. Nemělo by to být abstraktní ani imaginární.
  • Vstup: dobrý algoritmus musí být schopen přijmout sadu definovaných vstupů.
  • Výstup: dobrý algoritmus by měl být schopen produkovat výsledky jako výstup, nejlépe řešení.
  • Konečnost: algoritmus by měl mít zastavení po určitém počtu pokynů.
  • Obecnost: algoritmus musí platit pro sadu definovaných vstupů.

1881 Negativní reakce Johna Venna na Logický stroj W. Stanleyho Jevonsa z roku 1870

Na začátku roku 1870 W. Stanley Jevons představil „Logický stroj“ (Jevons 1880: 200) pro analýzu sylogismu nebo jiné logické formy, např. Argument redukovaný na booleovskou rovnici . Prostřednictvím toho, co Couturat (1914) nazval „jakýmsi logickým klavírem [,] ... se na klávesnici jako na psacím stroji„ hrají “rovnosti, které představují prostor ... Když jsou všechny prostory byly "přehrány", panel zobrazuje pouze ty složky, jejichž součet se rovná 1, tj. ... její logický celek. Tato mechanická metoda má výhodu oproti geometrické metodě VENN ... "(Couturat 1914: 75).

Pro jeho část John Venn , logik soudobé na Jevons, bylo méně než nadšený, opining že „Nezdá se mi, že všechny contrivances v současné době známo, nebo může být objeven opravdu zaslouží název logických strojů“ (kurzíva přidána, Venn 1881: 120). Historické využití rozvíjejícího se pojmu „algoritmus“ má však jeho vysvětlení jeho negativní reakce na stroj, který „může zasloužit opravdu cenný účel tím, že nám umožní vyhnout se jinak nevyhnutelné práci“:

(1) „Zaprvé je zde prohlášení o našich datech v přesném logickém jazyce“,
(2) „Pak zadruhé, musíme uvést tato tvrzení do formy vhodné pro práci s motorem - v tomto případě redukce každého návrhu na jeho elementární popření“,
(3) „Zatřetí, došlo k kombinaci nebo další úpravě našich prostor po takové redukci,“
(4) „Konečně musí být výsledky interpretovány nebo přečteny. To poslední obecně vede k velkému otevření dovednosti a bystrosti.“

Dochází k závěru, že „nevidím, že by jakýkoli stroj mohl doufat, že nám pomůže, kromě třetího z těchto kroků; takže se zdá velmi pochybné, zda si něco takového skutečně zaslouží název logického motoru.“ (Venn 1881: 119 –121).

1943, 1952 Stephen Kleene je charakterizace

Tato část je delší a podrobnější než ostatní, protože jeho význam pro téma: Kleene byl první, kdo navrhl, aby všechny výpočty / výpočty, z každého druhu se celek of-mohou ekvivalentně být (i) vypočte s použitím pěti " primitivní rekurzivní operátory “plus jeden speciální operátor zvaný mu-operátor , nebo být (ii) vypočítán akcemi Turingova stroje nebo ekvivalentního modelu.

Dále se domníval, že jeden z nich bude fungovat jako definice algoritmu .

Čtenář, který nejprve konfrontuje následující slova, může být zmatený, takže je na místě krátké vysvětlení. Výpočtové prostředky prováděné ručně, výpočetní prostředky prováděné Turingovým strojem (nebo ekvivalentem). (Autor někdy sklouzne a zamění slova). „Funkci“ lze chápat jako „vstupní-výstupní pole“, do kterého člověk vloží přirozená čísla zvaná „argumenty“ nebo „parametry“ (ale pouze početní čísla včetně 0 - nezáporná celá čísla) a dostane jednu nezápornou hodnotu celé číslo (běžně se nazývá „odpověď“). Představte si „funkční skříňku“ jako malého muže, který buď počítá ručně pomocí „obecné rekurze“, nebo počítá Turingovým strojem (nebo rovnocenným strojem).

„Efektivně vypočítatelný / vypočítatelný“ je obecnější a znamená „vypočítatelný / vypočítatelný pomocí nějakého postupu, metody, techniky ... ať už…“. „Obecná rekurzivní“ byl Kleenův způsob psaní toho, čemu se dnes říká jen „rekurze“; „primitivní rekurze“ - výpočet pomocí pěti rekurzivních operátorů - je však menší formou rekurze, která postrádá přístup k šestému, dalšímu, operátoru mu, který je potřebný pouze ve výjimečných případech. Většina života tedy vyžaduje pouze „primitivní rekurzivní funkce“.

1943 „Diplomová práce I“, 1952 „Diplomová práce církve“

V roce 1943 Kleene navrhl to, co se stalo známým jako Churchova teze :

Teze I. Každá efektivně vypočítatelná funkce (efektivně rozhodnutelný predikát) je obecně rekurzivní“ (Nejprve uvedl Kleene v roce 1943 (přetištěno na stránce 274 v Davis, ed. Nerozhodnutelné ; je také doslovně uvedeno v Kleene (1952) str.300)

Stručně řečeno: k výpočtu jakékoli funkce jsou jedinými operacemi, které člověk potřebuje (technicky, formálně) 6 primitivních operátorů „obecné“ rekurze (dnes nazývaných operátory mu rekurzivních funkcí ).

Kleeneovo první prohlášení o tom bylo pod názvem sekce „ 12. Algoritmické teorie “. Později to ve svém textu (1952) zesílí takto:

„Teze I a její obrácení poskytují přesnou definici pojmu výpočetní (rozhodovací) procedury nebo algoritmu pro případ funkce (predikátu) přirozených čísel“ (str. 301, pro zvýraznění přidáno tučně)

(Jeho použití slov „rozhodnutí“ a „predikát“ rozšiřuje pojem vypočítatelnosti na obecnější manipulaci se symboly, jaké se vyskytují v matematických „důkazech“.)

To není tak skličující, jak to může znít - „obecná“ rekurze je jen způsob, jak podle potřeby provádět naše každodenní aritmetické operace od pěti „operátorů“ primitivních rekurzivních funkcí spolu s dalším mu-operátorem . Kleene ve skutečnosti uvádí 13 příkladů primitivních rekurzivních funkcí a Boolos – Burgess – Jeffrey přidává některé další, z nichž většina bude čtenáři obeznámena - např. Sčítání, odčítání, násobení a dělení, umocňování, funkce CASE, zřetězení atd., atd.; pro seznam viz Některé běžné primitivní rekurzivní funkce .

Proč spíše obecné rekurzivní funkce než primitivní rekurzivní funkce?

Kleene a kol. (viz § 55 Obecné rekurzivní funkce str. 270, Kleene 1952) musel přidat šestý operátor rekurze zvaný minimalizační operátor (psaný jako μ-operátor nebo mu-operátor ), protože Ackermann (1925) vytvořil nesmírně rostoucí funkci - Ackermann funkce - a Rózsa Péter (1935) vytvořil obecnou metodu vytváření rekurzivních funkcí pomocí Cantorova úhlopříčného argumentu , z nichž ani jeden nemohl být popsán 5 operátory primitivní rekurzivní funkce. S ohledem na Ackermannovu funkci:

„... v jistém smyslu délka výpočtového algoritmu rekurzivní funkce, která není také primitivní rekurzivní, roste s argumenty rychleji než hodnota jakékoli primitivní rekurzivní funkce“ (Kleene (1935) přetištěno na str. 246 v The Nerozhodnutelné , plus poznámka pod čarou 13, pokud jde o potřebu dalšího operátora, doplněno tučně).

Potřeba operátora mu je ale vzácností. Jak je naznačeno výše v Kleenově seznamu běžných výpočtů, člověk si spokojeně počítá s primitivními rekurzivními funkcemi, aniž by se bál setkat s počty příšer vytvořených Ackermannovou funkcí (např. Superexponenciace ).

1952 „Turingova práce“

Turingova práce předpokládá vypočítatelnost „všech vypočítatelných funkcí“ modelem Turingova stroje a jeho ekvivalenty.

Aby to udělal efektivním způsobem, Kleene rozšířil pojem „vypočítatelný“ tím, že síť vrhl širší - tím, že do pojmu „funkce“ umožnil „celkové funkce“ i „částečné funkce“. Funkce celkem je definována pro všechna přirozená čísla (kladná celá čísla včetně 0). Částečná funkce je definována pro některá přirozená čísla, ale ne pro všechna - specifikace „některé“ musí přijít „dopředu“. Zahrnutí „částečné funkce“ tedy rozšiřuje pojem funkce na „méně dokonalé“ funkce. Celkové a částečné funkce lze vypočítat ručně nebo vypočítat strojem.

Příklady:
„Funkce“: zahrnuje „běžné odčítání m  -  n “ a „sčítání m  +  n
"Partial function": "Common subtraction" m  -  n není definováno, pokud jsou jako vstup povolena pouze přirozená čísla (kladná celá čísla a nula) - např. 6-7 je nedefinováno
Celková funkce: „Sčítání“ m  +  n je definováno pro všechna kladná celá čísla a nulu.


Nyní sledujeme Kleeneovu definici „počítatelné“ ve formálním smyslu:

Definice: „Dílčí funkce φ je vypočítatelná , pokud existuje stroj M, který ji počítá“ (Kleene (1952), s. 360)
"Definice 2.5. N -ary funkce f ( x 1 , ..., x n ) je částečně vypočítatelná, pokud existuje Turingův stroj Z takový, že
f ( x 1 , ..., x n ) = Ψ Z ( n ) ( x 1 , ..., [ x n )
V tomto případě říkáme, že [stroj] Z počítá f . Pokud je navíc f ( x 1 , ..., x n ) celková funkce, pak se nazývá vypočítatelná "(Davis (1958), s. 10)

Tak jsme dospěli k Turingově práci :

„Každá funkce, která by přirozeně byla považována za vypočítatelnou, je vypočítatelná ... jedním z jeho strojů ...“ (Kleene (1952) str. 376)

Ačkoli Kleene neuvedl příklady „vypočítatelných funkcí“, jiné mají. Například Davis (1958) uvádí Turingovy tabulky pro funkce Konstanta, Nástupce a Identita, tři z pěti operátorů primitivních rekurzivních funkcí :

Vypočítatelné Turingovým strojem:
Sčítání (je také funkcí Konstanta, pokud je jeden operand 0)
Přírůstek (nástupnická funkce)
Společné odčítání (definováno, pouze pokud x y ). „ X  -  y “ je tedy příkladem částečně vypočítatelné funkce.
Správné odčítání x y (jak je definováno výše)
Funkce identity: pro každé i existuje funkce U Z n = Ψ Z n ( x 1 , ..., x n ), která vytrhne x i ze sady argumentů ( x 1 , ..., x n )
Násobení

Boolos – Burgess – Jeffrey (2002) uvádí následující jako prozaické popisy Turingových strojů pro:

Zdvojnásobení: 2 str
Parita
Přidání
Násobení

Pokud jde o pultový stroj , abstraktní model stroje ekvivalentní stroji Turing:

Příklady vypočítatelné strojem Abacus (srov Boolos – Burgess – Jeffrey (2002))
Přidání
Násobení
Exponence: (a flow-chart / block diagram description of the algorithm)

Demonstrace vypočítatelnosti pomocí počítadla (Boolos – Burgess – Jeffrey (2002)) a počítadla (Minsky 1967):

Šest operátorů rekurzivních funkcí:
  1. Nulová funkce
  2. Nástupnická funkce
  3. Funkce identity
  4. Funkce složení
  5. Primitivní rekurze (indukce)
  6. Minimalizace

Skutečnost, že modely počítadla / pultového stroje mohou simulovat rekurzivní funkce, poskytuje důkaz, že: Pokud je funkce „strojově vypočítatelná“, pak je „ručně vypočítatelná částečnou rekurzí“. Kleeneova věta XXIX:

Věta XXIX:„ Každá vypočítatelná parciální funkce φ je částečná rekurzivní ... “(kurzíva v originále, s. 374).

Konverzace se jeví jako jeho Věta XXVIII. Společně tvoří důkaz jejich rovnocennosti, Kleeneova věta XXX.

1952 Církev – Turingova práce

S jeho Věta XXX Kleene dokazuje na ekvivalenci ze dvou „Práce,“ což znamenalo církevní práce a Turingova práce. (Kleene může pouze hypotetizovat (dohadovat) pravdivost obou tezí - tyto neprokázal ):

VĚRA XXX: Následující třídy dílčích funkcí ... mají stejné členy: (a) částečné rekurzivní funkce, (b) vypočítatelné funkce ... “ (str. 376)
Definice „parciální rekurzivní funkce“: „Parciální funkce φ je parciální rekurzivní v [parciálních funkcích] ψ 1 , ... ψ n, pokud existuje systém rovnic E, který definuje φ rekurzivně z [parciálních funkcí] ψ 1 , ... ψ n "(str. 326)

Kleenova věta XXX: buď metoda vytváření čísel ze vstupních čísel - rekurzivní funkce počítané ručně nebo počítaná Turingovým strojem nebo ekvivalentem - vede k „ efektivně vypočítatelné / vypočítatelné funkci“. Pokud přijmeme hypotézu, že každý výpočet / výpočet lze provést kteroukoli metodou ekvivalentně, přijali jsme jak Kleeneovu větu XXX (ekvivalenci), tak Church-Turingovu tezi (hypotéza „každého“).

Poznámka nesouhlasu: „Algoritmus má více ...“ Blass a Gurevič (2003)

Pojem oddělení církevních a Turingových tezí od „teze Church-Turing“ se objevuje nejen v Kleene (1952), ale také v Blass-Gurevich (2003). Ale i když existují dohody, existují i ​​neshody:

„... nesouhlasíme s Kleeneem, že pojem algoritmu je tak dobře pochopen. Ve skutečnosti je pojem algoritmu v dnešní době bohatší, než tomu bylo za Turingových dnů. A existují algoritmy moderních i klasických odrůd, které nejsou přímo pokryty Turingova analýza například algoritmy, které interagují s jejich prostředím, algoritmy, jejichž vstupy jsou abstraktní struktury, a geometrické nebo obecněji diskrétní algoritmy. “(Blass-Gurevich (2003), s. 8, tučně přidáno)

1954 Charakterizace AA Markova mladšího

Andrey Markov Jr. (1954) poskytl následující definici algoritmu:

„1. V matematice se„ algoritmu “běžně rozumí přesný předpis, který definuje výpočetní proces vedoucí od různých počátečních dat k požadovanému výsledku ...“
„Následující tři vlastnosti jsou charakteristické pro algoritmy a určují jejich roli v matematice:
„a) přesnost předpisu, která neponechává žádné místo svévole, a jeho univerzální srozumitelnost - jednoznačnost algoritmu;
„b) možnost začít s počátečními daty, která se mohou v daných mezích lišit - obecnost algoritmu;
„c) orientace algoritmu směrem k získání nějakého požadovaného výsledku, který se nakonec získá se správnými počátečními údaji - přesvědčivostí algoritmu.“ (str.1)

Připustil, že tato definice „nepředstírá matematickou přesnost“ (s. 1). Jeho monografie z roku 1954 byla jeho pokusem přesněji definovat algoritmus; viděl svou výslednou definici - svůj „normální“ algoritmus - jako „ekvivalentní konceptu rekurzivní funkce “ (str. 3). Jeho definice zahrnovala čtyři hlavní složky (kapitola II.3, str. 63 a násl.):

"1. Samostatné základní kroky, z nichž každý bude proveden podle jednoho z [substitučních] pravidel ... [pravidel uvedených na začátku]
„2. ... kroky místní povahy ... [Algoritmus se tedy nezmění více než určitý počet symbolů nalevo nebo napravo od pozorovaného slova / symbolu]
"3. Pravidla pro substituční vzorce ... [nazval jejich seznam" schématem "algoritmu]
„4. ... prostředek k rozlišení„ závěrečné substituce “[tj. Rozlišitelný„ koncový / konečný “stav nebo stavy]

Ve svém úvodu Markov poznamenal, že „veškerý význam pro matematiku“ v přesnější definici algoritmu bude „ve spojení s problémem konstruktivního základu pro matematiku“ (s. 2). Ian Stewart (srov Encyklopedie Britannica) sdílí podobné přesvědčení: „... konstruktivní analýza je do značné míry ve stejném algoritmickém duchu jako počítačová věda ...“. Více viz konstruktivní matematika a intuicionismus .

Rozlišitelnost a lokalizace : Oba pojmy se poprvé objevily u Turinga (1936–1937) -

„Nové pozorované čtverce musí být počítačem okamžitě rozpoznatelné [ sic : počítačem byla osoba v roce 1936]. Považuji za rozumné předpokládat, že to mohou být pouze čtverce, jejichž vzdálenost od nejbližších okamžitě pozorovaných čtverců nepřesahuje určité pevné množství. Zůstaňme, že každý z nových pozorovaných čtverců je v rámci čtverců L jednoho z dříve pozorovaných čtverců. “ (Turing (1936) str. 136, Davis ed. Nerozhodnutelné )

Lokalita se objevuje prominentně v díle Gureviče a Gandyho (1980) (které Gurevič cituje). Gandyho „Čtvrtým principem pro mechanismy“ je „The Principle of Local Causality“:

„Nyní se dostáváme k nejdůležitějšímu z našich principů. V Turingově analýze požadavek, že akce závisí pouze na ohraničené části záznamu, byl založen na lidském omezení. Nahradíme to fyzickým omezením, které nazýváme princip lokálního příčina. Jeho ospravedlnění spočívá v konečné rychlosti šíření efektů a signálů: současná fyzika odmítá možnost okamžitého působení na dálku. “ (Gandy (1980) str. 135 v J. Barwise a kol.)

1936, 1963, 1964 Gödelova charakteristika

1936 : Poměrně slavný citát Kurta Gödla se objevuje v „poznámce přidané jako důkaz [původní německé publikace] v jeho článku„ O délce důkazů “přeloženého Martinem Davisem, který vyšel na str. 82–83 z Nerozhodnutelného . řada autorů - Kleene, Gurevich, Gandy atd. - uvedli následující:

„Pojem„ vypočítatelný “je tedy v určitém definitivním smyslu„ absolutní “, zatímco prakticky všechny ostatní známé metamatematické pojmy (např. Prokazatelné, definovatelné atd.) Závisí zcela zásadně na systému, ve vztahu k němuž jsou definovány.“ (str.83)

1963 : V poznámce ze dne 28. srpna 1963 přidané ke svému slavnému článku O formálně nerozhodnutelných propozicích (1931) Gödel uvádí (v poznámce pod čarou) své přesvědčení, že „ formální systémy “ mají „charakteristickou vlastnost, kterou v nich v zásadě uvažuje: lze zcela nahradit mechanickými zařízeními “(str. 616 in van Heijenoort). „… díky„ práci AM Turinga lze nyní uvést přesnou a nepochybně adekvátní definici obecného pojmu formální systém [a] nyní je možná zcela obecná verze vět VI a XI. “(s. 616). V poznámce k jinému dílu z roku 1964 vyjadřuje stejný názor důrazněji a podrobněji.

1964 : V Postscriptu z roku 1964 k článku předloženému Ústavu pro pokročilé studium na jaře 1934 Gödel zesílil své přesvědčení, že „formální systémy“ jsou systémy, které lze mechanizovat:

„V důsledku pozdějších pokroků, zejména skutečnosti, že díky práci AM Turinga lze nyní uvést přesnou a nepochybně adekvátní definici obecného pojmu formálního systému.. Turingova práce poskytuje analýzu pojmu„ mechanický postup "(alias" algoritmus "nebo" výpočetní postup "nebo" konečný kombinatorický postup "). Ukázalo se, že tento koncept je ekvivalentní konceptu" Turingova stroje ". * Formální systém lze jednoduše definovat jako jakýkoli mechanický postup pro výrobu vzorců, nazývaných prokazatelné vzorce ... “ (str. 72, Martin Davis ed. The Undecidable : „Postscriptum“ to „On Undecidable Propositions of Formal Mathematical Systems“, uvedené na str. 39, loc. cit.)

* Označuje poznámku pod čarou, ve které Gödel cituje články Alana Turinga (1937) a Emila Posta (1936) a poté uvádí následující zajímavé prohlášení:

„Pokud jde o předchozí ekvivalentní definice vypočítatelnosti, které jsou však pro náš účel mnohem méně vhodné, viz Alonzo Church , Am. J. Math., Sv. 58 (1936) [objevující se v The Undecidable str. 100-102].

Církevní definice zahrnují takzvanou „ rekurzi “ a „ lambda kalkul “ (tj. Funkce definované lambda). Jeho poznámka pod čarou č. 18 uvádí, že s Gödelem diskutoval o vztahu „efektivní kalkulovatelnosti“ a „rekurzivity“, ale že nezávisle zpochybňoval „efektivní kalkulovatelnost“ a „definici λ“:

„Nyní definujeme pojem ... efektivně vypočítatelné funkce kladných celých čísel tím, že ji identifikujeme s pojmem rekurzivní funkce kladných celých čísel 18 (nebo funkce definující λ kladných celých čísel.
„Již bylo zdůrazněno, že pro každou funkci kladných celých čísel, kterou lze účinně vypočítat v právě definovaném smyslu, existuje algoritmus pro výpočet její hodnoty.
„Naopak je to pravda.“ (str. 100, Nerozhodnutelný).

Z toho a z následujícího vyplývá, že pokud jde o Gödela, Turingův stroj byl dostačující a lambda kalkul byl „mnohem méně vhodný“. Dále uvádí, že s ohledem na omezení lidského rozumu je porota stále mimo:

(„Všimněte si, že otázka, zda existují konečné nemechanické postupy **, které nejsou ekvivalentní žádnému algoritmu, nemá vůbec nic společného s adekvátností definice„ formálního systému “a„ mechanického postupu. “) (Str. 72, loc. Cit.)
„(U teorií a postupů v obecnějším smyslu uvedených v poznámce pod čarou ** může být situace odlišná. Všimněte si, že výsledky zmíněné v postscriptu nestanoví žádné hranice pro síly lidského rozumu, ale spíše pro možnosti čistého formalismu z matematiky.) (str.
Poznámka pod čarou **: „Tj. Zahrnují použití abstraktních termínů na základě jejich významu. Viz můj příspěvek v Dial. 12 (1958), s. 280.“ (tato poznámka pod čarou se objevuje na str. 72, cit. výše).

1967 Minskyho charakterizace

Minsky (1967) plešatě tvrdí, že „algoritmus je„ efektivní postup “a odmítá ve svém textu dále používat slovo„ algoritmus “; jeho index ve skutečnosti jasně ukazuje, co si myslí o„ Algoritmu, synonymu pro efektivní postup “( 311):

„V pokračování použijeme druhý termín [ efektivní postup ]. Termíny jsou zhruba synonymní, ale existuje řada významových odstínů používaných v různých kontextech, zejména pro„ algoritmus ““ (kurzíva v originále, s. 105 )

Jiní autoři (viz Knuth níže) používají slovo „efektivní postup“. To vede k zamyšlení: Jaký je Minsky pojem „účinného postupu“? Začíná s:

„... soubor pravidel, která nám od okamžiku k okamžiku přesně říkají, jak se máme chovat“ (str. 106)

Uznává však, že to podléhá kritice:

„... kritika, že výklad pravidel je ponechán na nějaké osobě nebo agentovi“ (str. 106)

Jeho upřesnění? „Specifikovat spolu s prohlášením pravidel podrobnosti mechanismu, který je má interpretovat “. Aby se vyhnul „těžkopádnému“ procesu „nutnosti opakovat to u každého jednotlivého postupu“, doufá, že identifikuje „přiměřeně jednotnou skupinu mechanismů dodržujících pravidla“. Jeho „formulace“:

"(1) jazyk, ve kterém mají být vyjádřeny soubory pravidel chování, a
„(2) jediný stroj, který dokáže interpretovat příkazy v jazyce a provádět tak kroky každého specifikovaného procesu.“ (kurzíva v originále, všechny citáty z tohoto odstavce str. 107)

Nakonec se však stále obává, že „v této věci zůstává subjektivní aspekt. Různí lidé se nemusí shodnout na tom, zda by měl být určitý postup označen za účinný“ (str. 107)

Minsky je to však neodradilo. Okamžitě představuje „Turingovu analýzu výpočetního procesu“ (jeho kapitola 5.2). Cituje to, co nazývá „Turingova teze

„Turingův stroj může realizovat jakýkoli proces, který lze přirozeně nazvat účinným postupem.“ (Str. 108. (Minsky poznamenává, že v obecnější podobě se tomu říká „ církevní teze “).

Po analýze „Turingova argumentu“ (jeho kapitola 5.3) podotýká, že „ekvivalence mnoha intuitivních formulací“ Turinga, Churche, Kleene, Posta a Smullyana “... nás vede k domněnce, že zde skutečně existuje„ cíl „nebo„ absolutní “pojem. Jak uvedl Rogers [1959]:

„V tomto smyslu je pojem efektivně vypočítatelné funkce jedním z mála„ absolutních “konceptů vytvořených moderní prací v základech matematiky.“ “(Minsky str. 111 cituje Rogerse, Hartley Jr (1959) Současná teorie Turingova stroje vypočitatelnost , J. SIAM 7, 114-130.)

1967 Rogersova charakteristika

Ve své teorii rekurzivních funkcí a efektivní vypočítatelnosti z roku 1967 charakterizuje Hartley Rogers „algoritmus“ zhruba jako „administrativní (tj. Deterministický, účetní) postup… aplikovaný na… symbolické vstupy, které nakonec přinesou pro každý takový vstup , odpovídající symbolický výstup "(str. 1). Dále popisuje pojem „přibližně a intuitivně“, který má 10 „znaků“, z nichž 5 tvrdí, že „prakticky všichni matematici by souhlasili [s]“ (s. 2). Zbylých 5, které tvrdí, „je méně zřejmých než * 1 až * 5 a o kterých bychom mohli najít méně obecnou shodu“ (str. 3).

5 „zřejmých“ je:

  • 1 Algoritmus je sada instrukcí konečné velikosti,
  • 2 Existuje schopný výpočetní agent,
  • 3 „Existují zařízení pro vytváření, ukládání a načítání kroků ve výpočtu“
  • 4 Vzhledem k tomu, že # 1 a # 2 agent počítá „diskrétním způsobem“ bez použití kontinuálních metod nebo analogových zařízení “,
  • 5 Výpočetní agent přenáší výpočet dopředu „bez použití náhodných metod nebo zařízení, např. Kostek“ (v poznámce pod čarou si Rogers klade otázku, zda jsou č. 4 a č. 5 skutečně stejné)

Zbývajících 5, které otevírá k debatě, jsou:

  • 6 Žádná pevná vazba na velikost vstupů,
  • 7 Žádná pevná vazba na velikost sady pokynů,
  • 8 Žádná pevná vazba na dostupné množství paměti,
  • 9 Pevná konečná vazba na kapacitu nebo schopnost výpočetního agenta (Rogers ilustruje na příkladu jednoduché mechanismy podobné Post-Turingovu stroji nebo počítadlu ),
  • 10 Omezeno na délku výpočtu - „měli bychom mít nějakou představu,„ předem “, jak dlouho bude výpočet trvat?“ (str. 5). Rogers vyžaduje „pouze to, aby výpočet skončil po určitém konečném počtu kroků; netrváme na apriorní schopnosti odhadnout tento počet.“ (str. 5).

1968, 1973 Knuthova charakteristika

Knuth (1968, 1973) uvedl seznam pěti vlastností, které jsou široce přijímány jako požadavky na algoritmus:

  1. Konečnost : „Algoritmus musí vždy skončit po konečném počtu kroků ... velmi konečné číslo, přiměřené číslo“
  2. Definitivita : "Každý krok algoritmu musí být přesně definován; akce, které mají být provedeny, musí být pro každý případ přesně a jednoznačně specifikovány."
  3. Vstup : "... veličiny, které jsou mu dány původně před zahájením algoritmu. Tyto vstupy jsou převzaty ze specifikovaných sad objektů"
  4. Výstup : "... množství, která mají specifikovaný vztah ke vstupům"
  5. Účinnost : „... všechny operace, které mají být provedeny v algoritmu, musí být dostatečně základní, aby je v zásadě bylo možné provést přesně a v konečném čase pomocí papíru a tužky“

Knuth nabízí jako příklad euklidovský algoritmus pro určení největšího společného dělitele dvou přirozených čísel (srov. Knuth sv. 1 s. 2).

Knuth připouští, že i když jeho popis algoritmu může být intuitivně jasný, postrádá formální přísnost, protože není zcela jasné, co znamená „přesně definovaný“ nebo „přísně a jednoznačně specifikovaný“ znamená nebo „dostatečně základní“, a tak dále. V tomto směru usiluje ve svém prvním svazku, kde podrobně definuje, co nazývá „ strojovým jazykem “ pro svůj „mýtický MIX ... první polynenasycený počítač na světě“ (str. 120 a dále). Mnoho algoritmů v jeho knihách je napsáno v jazyce MIX. Používá také stromové diagramy , vývojové diagramy a stavové diagramy .

„Dobrota“ algoritmu, „nejlepší“ algoritmy : Knuth uvádí, že „V praxi nechceme jen algoritmy, chceme dobré algoritmy…“ Navrhuje, aby některými kritérii dobroty algoritmu byl počet kroků, které je třeba provést algoritmus, jeho „přizpůsobivost počítačům, jeho jednoduchost a elegance atd.“ Vzhledem k řadě algoritmů pro provádění stejného výpočtu, který z nich je „nejlepší“? Tento druh dotazu nazývá „algoritmická analýza: daný algoritmus k určení jeho charakteristik výkonu“ (všechny citáty z tohoto odstavce: Knuth Vol. 1 str. 7)

1972 Stoneova charakteristika

Stone (1972) a Knuth (1968, 1973) byli současně profesory na Stanfordské univerzitě, takže není divu, že v jejich definicích existují podobnosti (pro zvýraznění přidáno tučně):

„Abychom to shrnuli ... definujeme algoritmus jako sadu pravidel, která přesně definuje posloupnost operací tak, aby každé pravidlo bylo účinné a určité a aby posloupnost skončila v konečný čas.“ (tučně přidáno, str. 8)

Stone je pozoruhodný díky své podrobné diskusi o tom, co představuje „efektivní“ pravidlo - jeho robot nebo osoba jednající jako robot musí mít v sobě určité informace a schopnosti , a pokud ne, musí být tyto informace a schopnosti uvedeny v "algoritmus":

„Aby lidé mohli dodržovat pravidla algoritmu, musí být pravidla formulována tak, aby je bylo možné sledovat robotickým způsobem , tj. Bez nutnosti přemýšlet ... pokud však pokyny [k vyřešení kvadratické rovnice, jeho příklad] má se řídit někým, kdo ví, jak provádět aritmetické operace, ale neví, jak extrahovat druhou odmocninu, pak musíme také poskytnout soubor pravidel pro extrahování druhé odmocniny, abychom splnili definici algoritmus “(str. 4-5)

Kromě toho „... ne všechny pokyny jsou přijatelné , protože mohou vyžadovat, aby robot měl schopnosti nad rámec těch, které považujeme za rozumné .“ Uvádí příklad robota konfrontovaného s otázkou „Jindřich VIII. Anglický král?“ a vytisknout 1, pokud ano, a 0, pokud ne, ale robotovi tyto informace nebyly dříve poskytnuty. A co je horší, pokud se robot zeptá, zda byl Aristoteles anglickým králem a robot dostal pouze pět jmen, by nevěděl, jak odpovědět. Tedy:

„Intuitivní definice přijatelné posloupnosti instrukcí je definice, ve které je každá instrukce přesně definována tak, aby ji robot zaručeně dokázal dodržet “ (str. 6)

Poté, co nám poskytl svoji definici, Stone představuje model Turingova stroje a uvádí, že sada pěti n-tic, které jsou instrukcemi stroje, je „algoritmus ... známý jako program Turingova stroje“ (str. 9). Ihned poté pokračuje a říká, že „ výpočet Turingova stroje je popsán konstatováním:

"1. Abeceda pásky
"2. Forma, ve které jsou [vstupní] parametry prezentovány na pásku
"3. Počáteční stav Turingova stroje
"4. Forma, ve které odpovědi [výstup] bude na pásku zastoupena, když se Turingův stroj zastaví
"5. Program stroje" (přidána kurzíva, s. 10)

Tento přesný předpis toho, co je požadováno pro „výpočet“, je v duchu toho, co bude následovat v práci Blassa a Gurevicha.

1995 Soareova charakteristika

Výpočet je proces, při kterém postupujeme od původně daných objektů, nazývaných vstupy , podle pevné sady pravidel, nazývaných program, procedura nebo algoritmus , skrz řadu kroků a na konec těchto kroků dojdeme konečným Výsledek, který se nazývá výstup . Algoritmus , jako soubor pravidel postupujících od vstupů k výstupu, musí být přesný a určitý, přičemž každý postupný krok musí být jasně určen. Koncept vyčíslitelnosti se týká těch objektů, které lze v zásadě specifikovat výpočty ... "(kurzíva v originále, tučně přidáno str. 3)

2000 charakteristika Berlinského

David Berlinski, který byl studentem v Princetonu v polovině 60. let, byl studentem Alonzo Church (srov. S. 160). Jeho kniha The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer obsahuje následující definici algoritmu :

Hlasem logika:
" algoritmus je
konečný postup,
napsáno pevnou symbolickou slovní zásobou,
řídí se přesnými pokyny,
pohyb v diskrétních krocích, 1, 2, 3,. . .,
jehož provedení nevyžaduje vhled, chytrost,
intuice, inteligence nebo nadhled,
a to dříve či později skončí. "(tučné písmo a kurzíva v originále, s. xviii)

2000, 2002 Gurevichova charakteristika

Pečlivé čtení Gureviče 2000 vede člověka k závěru, že věří, že „algoritmus“ je ve skutečnosti „Turingův stroj“ nebo „ ukazatelový stroj “ provádějící výpočet. „Algoritmus“ není jen tabulka symbolů, která řídí chování stroje, ani to není jen jedna instance stroje, který provádí výpočet s ohledem na konkrétní sadu vstupních parametrů, ani to není vhodně naprogramovaný stroj s vypnutým napájením ; spíše algoritmus je stroj ve skutečnosti dělá jakýkoli výpočet, který je schopen . Gurevič nevychází správně a neřekne to, takže jak je uvedeno výše, tento závěr (závěr?) Je jistě otevřený debatě:

„... každý algoritmus může být simulován Turingovým strojem ... program může být simulován a proto mu Turingův stroj může dát přesný význam.“ (str. 1)
„Často se předpokládá, že problém formalizace pojmu sekvenční algoritmus vyřešili Church [1936] a Turing [1936]. Například podle Savage [1987] je algoritmus výpočetní proces definovaný Turingovým strojem. Church a Turing nevyřešili problém formalizace pojmu sekvenční algoritmus. Místo toho dali (odlišné, ale ekvivalentní) formalizace pojmu vypočítatelné funkce a algoritmus má více než funkci, kterou vypočítává. (Kurzíva přidána str. 3)
„Pojmy algoritmus a vypočítatelná funkce samozřejmě úzce souvisí: podle definice je vypočítatelná funkce funkcí vypočítatelnou algoritmem ... (str. 4)


V publikaci Blass a Gurevich 2002 se autoři dovolávají dialogu mezi „Quisani“ („Q“) a „autory“ (A), přičemž jako folii používají Yiannis Moshovakis, kde vycházejí rovně a jasně:

Odpověď: Abychom lokalizovali neshodu, nejprve se zmíníme o dvou bodech dohody. Za prvé, existují věci, které jsou očividně algoritmy podle definice kohokoli - Turingovy stroje, ASM v sekvenčním čase [Abstract State Machines] a podobně ... Za druhé, v druhém extrému jsou specifikace, které by podle definice nikoho nebyly považovány za algoritmy, protože neposkytují žádný údaj o tom, jak cokoli vypočítat ... Jde o to, jak podrobné informace musí být, aby se mohly počítat jako algoritmus ... Moshovakis povoluje některé věci, které bychom nazvali pouze deklarativní specifikací, a pravděpodobně by použil slovo „implementace“ pro věci, které nazýváme algoritmy. “ (odstavce spojené pro snazší čitelnost, 2002: 22)

Toto použití slova „implementace“ se dostává přímo k jádru otázky. Na začátku článku Q uvádí své čtení Moshovakis:

„... [Pravděpodobně by si myslel, že vaše praktická práce [Gurevich pracuje pro Microsoft] vás nutí myslet na implementace více než na algoritmy. Je docela ochotný identifikovat implementace se stroji, ale říká, že algoritmy jsou něco více Obecně. Spadá to na to, že říkáte, že algoritmus je stroj a Moschovakis říká, že není. “ (2002: 3)

Ale autoři se zde vaří a říkají „[L] et se drží„ algoritmu “a„ stroje “a čtenář je opět zmatený. Musíme si počkat, až Dershowitz a Gurevich 2007 získají následující poznámku pod čarou:

„… Pokud však někdo přijme Moshovakisovo stanovisko, pak je to„ implementace “algoritmů, které jsme si stanovili charakterizovat.“ (Srov. Poznámka pod čarou 9 2007: 6)

2003 Blass a Gurevichova charakteristika

Blass a Gurevič popisují svou práci, která se vyvinula z úvah o Turingových strojích a ukazatelích , konkrétně o strojích Kolmogorov-Uspensky (stroje KU), Schönhage Storage Modification Machines (SMM) a propojovacích automatech, jak je definoval Knuth. Práce Gandyho a Markova jsou také popisována jako vlivní předchůdci.

Gurevič nabízí „silnou“ definici algoritmu (doplněno tučně):

„... Turingův neformální argument ve prospěch jeho práce ospravedlňuje silnější tezi: každý algoritmus může být simulován Turingovým strojem .... V praxi by to bylo směšné ... [Přesto] [c] jeden zobecňuje Turingovy stroje tak, aby jakýkoli algoritmus, bez ohledu na to, jak abstraktní, lze modelovat zobecněným strojem? ... Ale předpokládejme, že takové zobecněné Turingovy stroje existují. Jaké by byly jejich stavy? ... struktura prvního řádu ... konkrétní ve všech případech postačuje malá instrukční sada ... výpočet jako vývoj stavu ... může být nedeterministický ... může interagovat s jejich prostředím ... [může být] paralelní a multiagentní ... [může mít] dynamická sémantika ... [dvě opory jejich práce jsou:] Turingova teze ... [a] pojem (prvního řádu) struktury [Tarski 1933] “(Gurevich 2000, s. 1-2)

Výpočet výše uvedené fráze jako evoluce státu se výrazně liší od definice Knutha a Stonea - „algoritmu“ jako Turingova strojového programu. Spíše odpovídá tomu, co Turing nazval úplnou konfigurací (srovnej Turingovu definici v Undecidable, str. 118) - a zahrnuje jak aktuální instrukci (stav), tak stav pásky. [srov Kleene (1952) str. 375, kde ukazuje příklad pásky se 6 symboly - všechny ostatní čtverce jsou prázdné - a jak Gödelize její kombinovaný stav tabulky pásky].

V příkladech algoritmu vidíme vývoj stavu z první ruky.

1995 - Daniel Dennett: evoluce jako algoritmický proces

Filozof Daniel Dennett ve své knize Darwinova nebezpečná myšlenka z roku 1995 analyzuje význam evoluce jako algoritmického procesu . Dennett identifikuje tři klíčové vlastnosti algoritmu:

  • Neutralita substrátu : algoritmus se spoléhá na svou logickou strukturu. Konkrétní forma, v níž se algoritmus projevuje, tedy není důležitá (Dennettův příklad je dlouhé dělení: funguje stejně dobře na papíře, na pergamenu, na obrazovce počítače, při použití neonových světel nebo při psaní skywritingu). (str.51)
  • Základní bezduchost : bez ohledu na to, jak komplikovaný může být konečný produkt algoritmického procesu, každý krok v algoritmu je dostatečně jednoduchý na to, aby jej provedlo mechanické zařízení, které není vnímavé. Algoritmus nevyžaduje „mozek“, aby jej udržoval nebo provozoval. „Standardní analogie učebnice konstatuje, že algoritmy jsou svého druhu recepty , které mají následovat začínající kuchaři.“ (Str. 51)
  • Zaručené výsledky : Pokud je algoritmus proveden správně, bude vždy produkovat stejné výsledky. „Algoritmus je spolehlivý recept.“ (str.51)

Na základě této analýzy dospěl Dennett k závěru, že „podle Darwina je evoluce algoritmickým procesem“. (str. 60).

Na předchozí stránce se však vydal na mnohem větší končetinu. V rámci své kapitoly s názvem „Procesy jako algoritmy“ uvádí:

„Ale pak ... existují vůbec nějaká omezení toho, co lze považovat za algoritmický proces? Myslím, že odpověď je NE; pokud byste chtěli, můžete s jakýmkoli procesem na abstraktní úrovni zacházet jako s algoritmickým procesem ... Pokud co zaráží vás, že záhadná je uniformita [oceánských] pískových zrn nebo síla čepele z [temperované oceli], algoritmické vysvětlení je to, co uspokojí vaši zvědavost - a bude to pravda ...
„Bez ohledu na to, jak působivé produkty algoritmu, základní proces se vždy skládá z ničeho, ale množina individuálně [ sic ] bezduché krocích následných navzájem bez pomoci jakéhokoli inteligentního dozoru, jsou‚automatické‘a priori: fungování automat. “ (str. 59)

Z výše uvedeného není jasné, zda Dennett tvrdí, že fyzický svět sám o sobě a bez pozorovatelů je skutečně algoritmický (výpočetní), nebo zda pozorovatel zpracovávající symboly přidává pozorování „smysl“.

2002 John Searle přidává k charakteristice Dennetta objasňující upozornění

Daniel Dennett je zastáncem silné umělé inteligence : myšlenka, že logická struktura algoritmu je dostatečná pro vysvětlení mysli . John Searle , tvůrce čínského experimentu s myšlenkou na pokoj , tvrdí, že „ syntax [tj. Logická struktura] sama o sobě nepostačuje pro sémantický obsah [tj. Znamená]“ ( Searle 2002 , s. 16). Jinými slovy, „význam“ symbolů je relativní k mysli, která je používá; algoritmus - logický konstrukt - sám o sobě pro mysl nestačí.

Searle varuje ty, kteří tvrdí, že algoritmické (výpočetní) procesy jsou přirozené v přírodě (například kosmologové, fyzici, chemici atd.):

Výpočet [...] je relativní k pozorovateli, a to proto, že výpočet je definován z hlediska manipulace se symboly, ale pojem „symbol“ není pojmem fyziky nebo chemie. Něco je symbolem, pouze pokud je použito, považováno nebo považováno za symbol. Argument čínské místnosti ukázal, že sémantika není vlastní syntaxi. Z toho ale vyplývá, že fyzika nemá vlastní syntaxi. [...] Něco je symbolem pouze ve vztahu k nějakému pozorovateli, uživateli nebo agentovi, který tomu přiřadí symbolickou interpretaci [...] můžete výpočtové interpretaci přiřadit cokoli. Pokud se však otázka zeptá: „Je vědomí skutečně výpočetní?“ odpověď je: nic není skutečně výpočetní [kurzíva přidána pro zdůraznění]. Výpočet existuje pouze ve vztahu k nějakému agentovi nebo pozorovateli, který vnucuje výpočetní interpretaci nějakého jevu. To je zřejmý bod. Měl jsem to vidět před deseti lety, ale ne.

-  John Searle, Searle 2002 , s. 17

2002: Boolos-Burgess-Jeffrey specifikace výpočtu Turingova stroje

Příklady této metody specifikace použité na sčítací algoritmus „m + n“ viz příklady algoritmu .

Příklad v Boolos-Burgess-Jeffrey (2002) (str. 31–32) ukazuje přesnost požadovanou v úplné specifikaci algoritmu, v tomto případě k přidání dvou čísel: m + n. Je to podobné jako u kamenných požadavků výše.

(i) Diskutovali o úloze „číselného formátu“ při výpočtu a vybrali „shodnou notaci“, která představuje čísla:

„Určitě může být výpočet v praxi s některými notacemi těžší než s jinými ... Ale ... je to v zásadě možné udělat v jakémkoli jiném zápisu, pouhým překladem dat ... Pro účely formování přísně definované představy o vypočítatelnosti , je vhodné použít monadickou nebo shodnou notaci “(str. 25–26)

(ii) Na začátku svého příkladu specifikují stroj, který má být použit při výpočtu jako Turingův stroj . Dříve specifikovali (str. 26), že Turingův stroj bude spíše odrůda 4-tice než 5-tice. Více o této konvenci najdete v Turingově stroji .

(iii) Dříve autoři určili, že poloha hlavy pásky bude označena indexem napravo od naskenovaného symbolu. Více o této konvenci najdete v Turingově stroji . (V následujícím textu je zvýraznění přidáno tučně):

„Nedostali jsme oficiální definici toho, co je to, aby numerická funkce byla vypočítatelná Turingovým strojem , specifikující, jak mají být vstupy nebo argumenty reprezentovány na stroji a jak jsou reprezentovány výstupy nebo hodnoty. Naše specifikace pro k- funkce place od kladných celých čísel po kladná celá čísla jsou následující:
„(a) [ Formát počátečního čísla: ] Argumenty m 1 , ... m k , ... budou reprezentovány v monadické [unární] notaci bloky těchto počtů tahů, přičemž každý blok bude oddělen od dalšího jediným prázdný, na jinak prázdnou pásku.
Příklad: 3 + 2, 111B11
„(b) [ Počáteční umístění hlavy, počáteční stav: ] Zpočátku bude zařízení skenovat levou 1 na pásku a bude ve svém původním stavu, stavu 1.
Příklad: 3 + 2, 1 1 111B11
„(c) [ Úspěšný výpočet - formát čísla na Halt: ] Pokud funkce, která má být vypočítána, přiřadí hodnotu n argumentům, které jsou zpočátku zobrazeny na pásce, pak se stroj nakonec zastaví na pásce obsahující blok tahů , a jinak prázdné ...
Příklad: 3 + 2, 11111
„(d) [ Úspěšný výpočet - umístění hlavy na Halt: ] V tomto případě [c] stroj zastaví skenování nejvíce vlevo 1 na pásku ...
Příklad: 3 + 2, 1 n 1111
„(e) [ Neúspěšný výpočet - selhání funkce Halt nebo Halt s nestandardním formátem čísel: ] Pokud funkce, která má být vypočítána, nepřidělí žádnou hodnotu argumentům, které jsou původně na pásku zastoupeny, pak stroj buď nikdy zastavit, nebo se zastaví v nějaké nestandardní konfiguraci ... “(tamtéž)
Příklad: B n 11111 nebo B11 n 111 nebo B11111 n

Tato specifikace je neúplná: vyžaduje umístění umístění pokynů a jejich formát v zařízení -

(iv) v tabulce konečných stavových strojů nebo v případě univerzálního Turingova stroje na pásku a
(v) Tabulka pokynů ve stanoveném formátu

Tento pozdější bod je důležitý. Boolos-Burgess-Jeffrey předvádějí (str. 36), že předvídatelnost položek v tabulce umožňuje „zmenšit“ tabulku uvedením položek v pořadí a vynecháním vstupního stavu a symbolu. Příklad výpočtu Turingova stroje vyžadoval pouze 4 sloupce, jak je uvedeno v tabulce níže (ale pozor: tyto byly stroji prezentovány v řádcích ):

Stát qk
Naskenovaný symbol
Akce
Další stav qk
Stát qn
Naskenovaný symbol
Akce
Další stav qk
Stát qk
B-akce
B-další stav qkB
1-akce
1: další stav qk1
1 B R H 1 1 R 2 1 R H R 2
2 B P 3 2 1 R 2 2 P 3 R 2
3 B L 4 3 1 R 3 3 L 4 R 3
4 B L 5 4 1 E 4 4 L 5 E 4
5 B R H 5 1 L 5 5 R H L 5

2006: Sipserovo tvrzení a jeho tři úrovně popisu

Příklady této metody specifikace použité na sčítací algoritmus „m + n“ viz příklady algoritmu .

Sipser začíná definováním „algoritmu“ následovně:

„Neformálně řečeno, algoritmus je soubor jednoduchých pokynů k provedení určitého úkolu. V běžném životě se algoritmům někdy říká procedury nebo recepty (kurzíva v originále, s. 154).
„... naše skutečné zaměření se od nynějška zaměřuje na algoritmy. To znamená, že Turingův stroj slouží pouze jako přesný model pro definici algoritmu ... musíme jen dostatečně pohodlně pracovat s Turingovými stroji, abychom věřili, že zachycují všechny algoritmy “(str. 156)

Znamená Sipser, že „algoritmus“ je pouze „instrukce“ pro Turingův stroj, nebo jde o kombinaci „instrukcí + (specifická paleta) Turingova stroje“? Například definuje dvě standardní varianty (vícepásmové a nedeterministické) své konkrétní varianty (ne stejné jako Turingův originál) a ve svých Problémy (strany 160-161) pokračuje popisem dalších čtyř variant ( jednorázový zápis, dvojnásobně nekonečná páska (tj. levá a pravá nekonečná), resetování vlevo a „zůstaňte na místě místo doleva“. Kromě toho ukládá určitá omezení. Nejprve musí být vstup zakódován jako řetězec (str. 157) a říká o numerických kódováních v kontextu teorie složitosti:

„Ale všimněte si, že unární notace pro kódování čísel (jako u čísla 17 kódovaného unárním číslem 111111111111111111) není rozumná, protože je exponenciálně větší než skutečně rozumná kódování, jako je základní k notace pro libovolné k ≥ 2.“ (str. 259)

Van Emde Boas komentuje podobný problém s ohledem na abstraktní model výpočtu stroje s náhodným přístupem (RAM), který se někdy používá místo Turingova stroje při provádění „analýzy algoritmů“: „Absence nebo přítomnost multiplikativní a paralelní bitové manipulace operace je relevantní pro správné pochopení některých výsledků při analýze algoritmů.

„… [T] zde sotva existuje něco jako„ nevinné “rozšíření standardního modelu RAM v jednotných časových měřítcích; buď jeden má pouze aditivní aritmetiku, nebo může obsahovat všechny rozumné multiplikativní a / nebo bitové Booleovské pokyny pro malé operandy. “ (Van Emde Boas, 1990: 26)

Pokud jde o „jazyk popisu“ pro algoritmy, Sipser dokončí práci, kterou Stone a Boolos-Burgess-Jeffrey zahájili (tučně přidáno). Nabízí tři úrovně popisu algoritmů Turingova stroje (str. 157):

Popis na vysoké úrovni : "kde používáme ... prózu k popisu algoritmu, ignorujeme podrobnosti implementace. Na této úrovni nemusíme zmínit, jak stroj spravuje svoji pásku nebo hlavu."
Popis implementace : "ve kterém používáme ... prózu k popisu způsobu, jakým Turingův stroj pohybuje hlavou a způsobu, jakým ukládá data na svou pásku. Na této úrovni neposkytujeme podrobnosti o stavech nebo přechodových funkcích."
Formální popis : „... nejnižší, nejpodrobnější, úroveň popisu ..., která podrobně vysvětluje stavy Turingova stroje, přechodovou funkci atd.“

Poznámky

Reference

  • David Berlinski (2000), The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer , Harcourt, Inc., San Diego, ISBN   0-15-601391-6 (pbk.)
  • George Boolos , John P. Burgess , Richard Jeffrey (2002), Computability and Logic: Fourth Edition , Cambridge University Press, Cambridge, UK. ISBN   0-521-00758-5 ( PBK ).
  • Andreas Blass a Yuri Gurevich (2003), Algorithms: A Quest for Absolute Definitions , Bulletin of European Association for theoretical Computer Science 81, 2003. Zahrnuje vynikající bibliografii 56 odkazů.
  • Burgin, M. Super-rekurzivní algoritmy , Monografie v informatice, Springer, 2005. ISBN   0-387-95569-0
  • Davis, Martin (1958). Vyčíslitelnost a neřešitelnost . New York: McGraw-Hill Book Company, Inc. . Zdroj důležitých definic a některých Turingových strojových algoritmů pro několik rekurzivních funkcí.
  • Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions . New York: Raven Press. Davis dává komentář před každým článkem. Zahrnuty jsou papíry Gödel , Alonzo Church , Turing , Rosser , Kleene a Emil Post .
  • Dennett, Daniel (1995). Darwinova nebezpečná myšlenka . New York: Touchstone / Simon & Schuster.
  • Robin Gandy , Church's Thesis and principy pro mechanismy , J. Barwise , HJ Keisler a K. Kunen , eds., The Kleene Symposium , North-Holland Publishing Company 1980), str. 123–148. Mezi slavné Gandyho „4 principy [výpočetních] mechanismů“ patří „Princip IV - Princip lokální kauzality“.
  • Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), str. 77–111. Zahrnuje bibliografii 33 zdrojů.
  • Kleene C., Stephen (1943). Msgstr "Rekurzivní predikáty a kvantifikátory" . Transakce americké matematické společnosti . Transakce Americké matematické společnosti, sv. 53, č. 1. 54 (1): 41–73. doi : 10,2307 / 1990131 . JSTOR   1990131 . Přetištěno v The Undecidable , str. 255ff. Kleene upřesnil svoji definici „obecné rekurze“ a pokračoval ve své kapitole „12. Algoritmické teorie“ k domněnce „teze I“ (s. 274); on by později opakoval tuto práci (v Kleene 1952: 300) a pojmenoval to “církevní práce” (Kleene 1952: 317) (tj. církevní práce ).
  • Kleene, Stephen C. (1991) [1952]. Úvod do metamatematiky (desáté vydání). Nakladatelská společnost North-Holland. Vynikající - přístupný, čitelný - referenční zdroj pro matematické „základy“.
  • Knuth, Donald E. (1973) [1968]. The Art of Computer Programming Second Edition, Volume 1 / Fundamental Algorithms (2nd ed.). Nakladatelská společnost Addison-Wesley. První z Knuthovy slavné série tří textů.
  • Lewis, HR a Papadimitriou, CH Prvky teorie výpočtu , Prentice-Hall, Uppre Saddle River, NJ, 1998
  • AA Markov (1954) Teorie algoritmů . [Přeložili Jacques J. Schorr-Kon a zaměstnanci PST] Otisk Moskva, Akademie věd SSSR, 1954 [tj. Jeruzalém, Izrael Program pro vědecké překlady, 1961; dostupné od Office of Technical Services, US Dept. of Commerce, Washington] Popis 444 str. 28 cm. Přidáno tp v ruském překladu prací Matematického ústavu Akademie věd SSSR, v. 42. Originální název: Teoriya algerifmov. [QA248.M2943 Knihovna Dartmouth College. US Department of Commerce, Office of Technical Services, number OTS 60-51085.]
  • Minsky, Marvin (1967). Výpočet: Konečné a nekonečné stroje (první vydání). Prentice-Hall, Englewood Cliffs, NJ. Minsky rozšiřuje svoji „... představu o algoritmu - efektivní postup ...“ v kapitole 5.1 Vyčíslitelnost, efektivní postupy a algoritmy. Nekonečné stroje.
  • Hartley Rogers, Jr , (1967), Teorie rekurzivních funkcí a efektivní vypočítatelnosti , MIT Press (1987), Cambridge MA, ISBN   0-262-68052-1 ( str .)
  • Searle, John (2002). Vědomí a jazyk . Cambridge UK: Cambridge University Press. ISBN   0-521-59744-7 .
  • Robert Soare (1995, sborník z 10. mezinárodního kongresu logiky, metodologie a filozofie vědy , 19. – 25. Srpna 1995, Florencie, Itálie), Computability and Recursion ), na webu na ??.
  • Michael Sipser , (2006), Introduction to the Theory of Computation: Second Edition , Thompson Course Technology div. společnosti Thompson Learning, Inc. Boston, MA. ISBN   978-0-534-95097-2 .
  • Ian Stewart , Algoritmus , Encyklopedie Britannica 2006.
  • Stone, Harold S.Úvod do počítačové organizace a datových struktur (ed. 1972). McGraw-Hill, New York. Srovnej zejména první kapitolu nazvanou: Algoritmy, Turingovy stroje a programy . Jeho stručná neformální definice: „... jakákoli posloupnost pokynů, které lze robotem dodržet, se nazývá algoritmus “ (str. 4).
  • Peter van Emde Boas (1990), „Modely strojů a simulace“, s. 3–66, účinkující v Jan van Leeuwen (1990), Příručka teoretické informatiky. Svazek A: Algorithms & Complexity , The MIT Press / Elsevier, 1990, ISBN   0-444-88071-2 (svazek A)