Algorithmus-Charakterisierungen - Algorithm characterizations

Algorithmus Charakterisierungen sind Versuche , das Wort zu formalisieren Algorithmus . Der Algorithmus hat keine allgemein akzeptierte formale Definition. Forscher arbeiten aktiv an diesem Problem. In diesem Artikel werden einige der "Charakterisierungen" des Begriffs "Algorithmus" ausführlicher vorgestellt.

Das Problem der Definition

In den letzten 200 Jahren ist die Definition des Algorithmus komplizierter und detaillierter geworden, da Forscher versucht haben, den Begriff zu bestimmen. In der Tat kann es mehr als einen Typ von "Algorithmus" geben. Die meisten sind sich jedoch einig, dass der Algorithmus etwas mit der Definition verallgemeinerter Prozesse für die Erzeugung von "Ausgabe" -Interzahlen aus anderen "Eingabe" -Interzahlen - "Eingabeparametern" willkürlich und unendlich im Umfang oder begrenzt im Umfang, aber immer noch variabel - durch Manipulation von zu tun hat Unterscheidbare Symbole (Zahlen zählen) mit endlichen Sammlungen von Regeln, die eine Person mit Papier und Bleistift ausführen kann.

Die gebräuchlichsten Zahlenmanipulationsschemata - sowohl in der formalen Mathematik als auch im Alltagsleben - sind: (1) die rekursiven Funktionen, die von einer Person mit Papier und Bleistift berechnet werden, und (2) die Turing-Maschine oder ihre Turing-Äquivalente - das primitive Register - Maschinen- oder "Gegenmaschinen" -Modell, das Direktzugriffsmaschinenmodell (RAM), das Direktzugriffs-Maschinenmodell (RASP) und sein funktionales Äquivalent "der Computer ".

Wenn wir "arithmetisch" machen, berechnen wir wirklich durch die Verwendung von "rekursiven Funktionen" in den Kurzalgorithmen, die wir in der Grundschule gelernt haben, zum Beispiel Addieren und Subtrahieren.

Die Beweise , dass jede „rekursive Funktion“ können wir von Hand berechnen wir können mit der Maschine berechnen und umgekehrt-beachten Sie die Verwendung der Wörter berechnen im Vergleich zu berechnen -is bemerkenswert. Diese Äquivalenz zusammen mit der These (unbewiesene Behauptung), dass dies jede Berechnung / Berechnung einschließt, zeigt jedoch, warum bei der Definition spezifischer Algorithmen so viel Wert auf die Verwendung von Turing-äquivalenten Maschinen gelegt wurde und warum die Definition von "Algorithmus" selbst bezieht sich oft auf "die Turingmaschine ". Dies wird unter Stephen Kleenes Charakterisierung ausführlicher diskutiert .

Das Folgende sind Zusammenfassungen der bekannteren Charakterisierungen (Kleene, Markov, Knuth) zusammen mit denen, die neuartige Elemente einführen - Elemente, die die Definition weiter erweitern oder zu einer genaueren Definition beitragen.

[ Ein mathematisches Problem und sein Ergebnis können als zwei Punkte in einem Raum betrachtet werden, und die Lösung besteht aus einer Folge von Schritten oder einem Pfad, der sie verbindet. Die Qualität der Lösung hängt vom Pfad ab. Es könnte mehr als ein Attribut für den Pfad, zB Länge definiert sein, die Komplexität der Form, ein einfache verallgemeinernde, Schwierigkeiten, und so weiter . ]]

Chomsky-Hierarchie

Es besteht mehr Konsens über die "Charakterisierung" des Begriffs "einfacher Algorithmus".

Alle Algorithmen müssen in einer formalen Sprache angegeben werden, und der "Begriff der Einfachheit" ergibt sich aus der Einfachheit der Sprache. Die Chomsky-Hierarchie (1956) ist eine Containment-Hierarchie von Klassen formaler Grammatiken , die formale Sprachen erzeugen . Es wird zur Klassifizierung von Programmiersprachen und abstrakten Maschinen verwendet .

Wenn der Algorithmus aus Sicht der Chomsky-Hierarchie in einer einfacheren Sprache (als uneingeschränkt) angegeben werden kann, kann er durch diese Art von Sprache charakterisiert werden, andernfalls handelt es sich um einen typischen "uneingeschränkten Algorithmus".

Beispiele: Eine "Allzweck" -Makrosprache wie M4 ist uneingeschränkt ( Turing vollständig ), die C-Präprozessor-Makrosprache jedoch nicht. Daher ist jeder in C-Präprozessor ausgedrückte Algorithmus ein "einfacher Algorithmus".

Siehe auch Beziehungen zwischen Komplexitätsklassen .

Merkmale eines guten Algorithmus

Das Folgende sind die Merkmale eines guten Algorithmus;

• Präzision: Ein guter Algorithmus muss bestimmte Schritte haben. Die Schritte sollten genau genug sein und nicht variieren.

• Eindeutigkeit: Jeder Schritt im Algorithmus sollte ein eindeutiges Ergebnis liefern, wie vom Verfasser des Algorithmus angegeben. Die Ergebnisse sollten in keiner Weise schwanken.
• Machbarkeit: Der Algorithmus sollte im wirklichen Leben möglich und praktikabel sein. Es sollte nicht abstrakt oder imaginär sein.
• Eingabe: Ein guter Algorithmus muss in der Lage sein, eine Reihe definierter Eingaben zu akzeptieren.
• Ausgabe: Ein guter Algorithmus sollte in der Lage sein, Ergebnisse als Ausgabe zu erzeugen, vorzugsweise als Lösungen.
• Endlichkeit: Der Algorithmus sollte nach einer bestimmten Anzahl von Anweisungen angehalten werden.
• Allgemeines: Der Algorithmus muss auf eine Reihe definierter Eingaben angewendet werden.

1881 John Venns negative Reaktion auf W. Stanley Jevons 'Logical Machine von 1870

Anfang 1870 präsentierte W. Stanley Jevons eine "Logical Machine" (Jevons 1880: 200) zur Analyse eines Syllogismus oder einer anderen logischen Form, z. B. eines auf eine Boolesche Gleichung reduzierten Arguments . Mit dem, was Couturat (1914) eine "Art logisches Klavier [,] ... nannte, werden die Gleichheiten, die die Prämissen darstellen ..., auf einer Tastatur wie der einer Schreibmaschine" gespielt ". ... Wenn alle Prämissen "gespielt" worden sind, zeigt das Panel nur die Bestandteile, deren Summe gleich 1 ist, dh ... sein logisches Ganzes. Diese mechanische Methode hat den Vorteil gegenüber der geometrischen Methode von VENN ... "(Couturat 1914: 75).

Für seinen Teil John Venn , ein Logiker zeitgenössischen zu Jevons, war weniger als begeistert, Meinen , dass „es nicht zu mir scheint , dass alle contrivances derzeit bekannt oder wahrscheinlich entdeckt zu werden wirklich den Namen der logischen Maschinen verdienen“ (Hervorhebung hinzugefügt, Venn 1881: 120). Aber von historischem Nutzen für den sich entwickelnden Begriff "Algorithmus" ist seine Erklärung für seine negative Reaktion in Bezug auf eine Maschine, die "einen wirklich wertvollen Zweck erfüllen kann, indem sie es uns ermöglicht, ansonsten unvermeidliche Arbeit zu vermeiden":

(1) "Da ist zunächst die Angabe unserer Daten in genauer logischer Sprache",

(2) "Zweitens müssen wir diese Aussagen in eine Form bringen, mit der der Motor arbeiten kann - in diesem Fall die Reduktion jedes Satzes auf seine elementaren Ablehnungen",

(3) "Drittens gibt es die Kombination oder Weiterbehandlung unserer Räumlichkeiten nach einer solchen Reduzierung."

(4) "Schließlich müssen die Ergebnisse interpretiert oder abgelesen werden. Letzteres führt im Allgemeinen zu einer großen Öffnung für Geschicklichkeit und Scharfsinn."

Er kommt zu dem Schluss, dass "ich nicht sehen kann, dass irgendeine Maschine hoffen kann, uns zu helfen, außer im dritten dieser Schritte; so dass es sehr zweifelhaft erscheint, ob irgendetwas dieser Art wirklich den Namen eines logischen Motors verdient" (Venn 1881: 119) –121).

1943, 1952 Stephen Kleenes Charakterisierung

Dieser Abschnitt ist aufgrund seiner Bedeutung für das Thema länger und detaillierter als die anderen: Kleene schlug als erster vor, dass alle Berechnungen / Berechnungen - jeder Art, der Gesamtheit von - äquivalent (i) unter Verwendung von fünf berechnet werden können. " primitive rekursive Operatoren "plus einen speziellen Operator, der als mu-Operator bezeichnet wird , oder (ii) durch die Aktionen einer Turing-Maschine oder eines äquivalenten Modells berechnet werden.

Darüber hinaus meinte er, dass beides als Definition des Algorithmus gelten würde .

Ein Leser, der sich zuerst mit den folgenden Wörtern auseinandersetzt, kann durchaus verwirrt sein, daher ist eine kurze Erklärung angebracht. Berechnungsmittel von Hand, Berechnungsmittel von Turing-Maschine (oder gleichwertig). (Manchmal rutscht ein Autor aus und tauscht die Wörter aus). Eine "Funktion" kann als "Eingabe-Ausgabe-Feld" betrachtet werden, in das eine Person natürliche Zahlen einfügt, die als "Argumente" oder "Parameter" bezeichnet werden (aber nur die Zählzahlen einschließlich 0 - die nichtnegativen ganzen Zahlen) und eine einzelne nichtnegative Zahl herausgibt Ganzzahl (üblicherweise "die Antwort" genannt). Stellen Sie sich die "Funktionsbox" als einen kleinen Mann vor, der entweder von Hand mit "allgemeiner Rekursion" berechnet oder mit einer Turing-Maschine (oder einer gleichwertigen Maschine) berechnet.

"Effektiv berechenbar / berechenbar" ist allgemeiner und bedeutet "berechenbar / berechenbar durch ein Verfahren, eine Methode, eine Technik ... was auch immer ...". "Allgemein rekursiv" war Kleenes Schreibweise, was heute nur "Rekursion" genannt wird; "Primitive Rekursion" - Berechnung unter Verwendung der fünf rekursiven Operatoren - ist jedoch eine geringere Form der Rekursion, die keinen Zugriff auf den sechsten zusätzlichen mu-Operator hat, der nur in seltenen Fällen benötigt wird. Daher erfordert der größte Teil des Lebens nur die "primitiven rekursiven Funktionen".

1943 "These I", 1952 "Church's Thesis"

1943 schlug Kleene eine so genannte These der Kirche vor :

" These I. Jede effektiv berechenbare Funktion (effektiv entscheidbares Prädikat) ist allgemein rekursiv" (Erstmals angegeben von Kleene im Jahr 1943 (nachgedruckt Seite 274 in Davis, Hrsg. The Undecidable ; erscheint auch wörtlich in Kleene (1952), S. 300).

Auf den Punkt gebracht: zur Berechnung irgendeiner Funktion die einzigen Operationen muss eine Person (technisch, formal) sind die sechs primitive Betreiber von „allgemeinen“ Rekursion (heute die Betreiber der genannten mu rekursive Funktionen ).

Kleenes erste Aussage dazu war unter dem Abschnittstitel " 12. Algorithmische Theorien ". Er würde es später in seinem Text (1952) wie folgt erweitern:

"These I und ihre Umkehrung liefern die genaue Definition des Begriffs eines Berechnungs- (Entscheidungs-) Verfahrens oder Algorithmus für den Fall einer Funktion (Prädikat) natürlicher Zahlen" (S. 301, Fettdruck zur Hervorhebung hinzugefügt)

(Seine Verwendung des Wortes "Entscheidung" und "Prädikat" erweitert den Begriff der Berechenbarkeit auf die allgemeinere Manipulation von Symbolen, wie sie in mathematischen "Beweisen" vorkommt.)

Dies ist nicht so entmutigend, wie es sich anhört - "allgemeine" Rekursion ist nur eine Möglichkeit, unsere alltäglichen arithmetischen Operationen aus den fünf "Operatoren" der primitiven rekursiven Funktionen zusammen mit dem zusätzlichen mu-Operator nach Bedarf durchzuführen . In der Tat gibt Kleene 13 Beispiele für primitive rekursive Funktionen an, und Boolos-Burgess-Jeffrey fügt weitere hinzu, von denen die meisten dem Leser bekannt sind - z. B. Addition, Subtraktion, Multiplikation und Division, Exponentiation, CASE-Funktion, Verkettung usw. usw.; Eine Liste finden Sie unter Einige häufig verwendete primitive rekursive Funktionen .

Warum eher allgemein rekursive Funktionen als primitiv rekursive Funktionen?

Kleene et al. (vgl. § 55 Allgemeine rekursive Funktionen S. 270 in Kleene 1952) musste einen sechsten Rekursionsoperator hinzufügen, den Minimierungsoperator (geschrieben als μ-Operator oder mu-Operator ), weil Ackermann (1925) eine enorm wachsende Funktion erzeugte - den Ackermann Funktion - und Rózsa Péter (1935) erstellte eine allgemeine Methode zum Erstellen rekursiver Funktionen unter Verwendung des diagonalen Arguments von Cantor , von denen keine durch die 5 Operatoren primitiv-rekursiver Funktionen beschrieben werden konnte. In Bezug auf die Ackermann-Funktion:

„... in einem gewissen Sinne, die Länge des Berechnungsalgorithmus einer rekursiven Funktion , die nicht auch primitiv - rekursiv ist schneller wächst mit den Argumenten als der Wert jeder primitiven rekursive Funktion“ (Kleene (1935) nachgedruckt p. 246 in dem Unentscheidbar , plus Fußnote 13 in Bezug auf die Notwendigkeit eines zusätzlichen Operators (Fettdruck hinzugefügt).

Die Notwendigkeit des Mu-Operators ist jedoch eine Seltenheit. Wie oben in Kleenes Liste allgemeiner Berechnungen angegeben, geht eine Person ihr Leben lang glücklich damit, primitive rekursive Funktionen zu berechnen, ohne befürchten zu müssen, auf die durch Ackermanns Funktion erzeugten Monsternummern zu stoßen (z. B. Superexponentiation ).

1952 "Turings These"

Turing's Thesis vermutet die Berechenbarkeit "aller berechenbaren Funktionen" durch das Turing-Maschinenmodell und seine Äquivalente.

Um dies auf effektive Weise zu tun, erweiterte Kleene den Begriff "berechenbar", indem er das Netz weiter ausbaute - indem er sowohl "Gesamtfunktionen" als auch "Teilfunktionen" in den Begriff "Funktionen" einbezog. Eine Gesamtfunktion ist eine Funktion , die für alle natürlichen Zahlen definiert ist (positive ganze Zahlen einschließlich 0). Eine Teilfunktion ist für einige natürliche Zahlen definiert, aber nicht für alle - die Angabe von "einige" muss "von vornherein" erfolgen. Somit erweitert die Einbeziehung von "Teilfunktion" den Funktionsbegriff auf "weniger perfekte" Funktionen. Gesamt- und Teilfunktionen können entweder von Hand berechnet oder maschinell berechnet werden.

Beispiele:

"Funktionen": umfassen "gemeinsame Subtraktion m  -  n " und "Addition m  +  n "

"Teilfunktion": "Gemeinsame Subtraktion" m  -  n ist undefiniert, wenn nur natürliche Zahlen (positive ganze Zahlen und Null) als Eingabe zulässig sind - z. B. 6 - 7 ist undefiniert

Gesamtfunktion: "Addition" m  +  n ist für alle positiven ganzen Zahlen und Null definiert.

Wir beobachten nun Kleenes Definition von "berechenbar" im formalen Sinne:

Definition: "Eine Teilfunktion φ ist berechenbar , wenn es eine Maschine M gibt, die sie berechnet" (Kleene (1952) S. 360)

Definition 2.5. Eine n- fache Funktion f ( x ₁ , ..., x _n ) ist teilweise berechenbar, wenn eine Turingmaschine Z existiert, so dass

f ( x ₁ , ..., x _n ) = Ψ _Z ^{( n )} ( x ₁ , ..., [ x _n )

In diesem Fall sagen wir, dass [Maschine] Z f berechnet . Wenn zusätzlich f ( x ₁ , ..., x _n ) eine Gesamtfunktion ist, dann heißt es berechenbar "(Davis (1958) S. 10)

So sind wir zu Turings These gekommen :

"Jede Funktion, die natürlich als berechenbar angesehen werden würde, ist berechenbar ... von einer seiner Maschinen ..." (Kleene (1952) S.376)

Obwohl Kleene keine Beispiele für "berechenbare Funktionen" angegeben hat, haben andere. Zum Beispiel gibt Davis (1958) Turing-Tabellen für die Konstanten-, Nachfolger- und Identitätsfunktionen an, drei der fünf Operatoren der primitiven rekursiven Funktionen :

Berechnbar mit der Turing-Maschine:

Addition (ist auch die Konstantenfunktion, wenn ein Operand 0 ist)

Inkrement (Nachfolgerfunktion)

Gemeinsame Subtraktion (nur definiert, wenn x ≥ y ist ). Somit ist " x  -  y " ein Beispiel für eine teilweise berechenbare Funktion.

Richtige Subtraktion x ┴ y (wie oben definiert)

Die Identitätsfunktion: Für jedes i existiert eine Funktion U _Z ⁿ = Ψ _Z ⁿ ( x ₁ , ..., x _n ), die x _i aus der Menge der Argumente ( x ₁ , ..., x _n ) _herausholt.

Multiplikation

Boolos-Burgess-Jeffrey (2002) geben folgende Prosa-Beschreibungen von Turing-Maschinen für:

Verdoppelung: 2 p

Parität

Zusatz

Multiplikation

In Bezug auf die Gegenmaschine ein abstraktes Maschinenmodell , das der Turingmaschine entspricht:

Beispiele, die mit einer Abacus-Maschine berechnet werden können (vgl. Boolos-Burgess-Jeffrey (2002))

Zusatz

Multiplikation

Erklärung: (eine Flussdiagramm- / Blockdiagrammbeschreibung des Algorithmus)

Demonstrationen der Berechenbarkeit mit einer Abakusmaschine (Boolos-Burgess-Jeffrey (2002)) und einer Gegenmaschine (Minsky 1967):

Die sechs rekursiven Funktionsoperatoren:

1. Nullfunktion
2. Nachfolgerfunktion
3. Identitätsfunktion
4. Kompositionsfunktion
5. Primitive Rekursion (Induktion)
6. Minimierung

Die Tatsache, dass die Abakus- / Gegenmaschinenmodelle die rekursiven Funktionen simulieren können, liefert den Beweis, dass: Wenn eine Funktion "maschinenberechnbar" ist, ist sie "durch teilweise Rekursion von Hand berechenbar". Kleenes Satz XXIX:

" Satz XXIX:" Jede berechenbare Teilfunktion φ ist teilweise rekursiv ... "(kursiv im Original, S. 374).

Die Umkehrung erscheint als sein Satz XXVIII. Zusammen bilden diese den Beweis ihrer Äquivalenz, Kleenes Satz XXX.

1952 Church-Turing-These

Mit seinem Satz XXX beweist Kleene die Gleichwertigkeit der beiden "Thesen" - der Kirchenthese und der Turingthese. (Kleene kann nur die Wahrheit beider Thesen hypothetisieren (vermuten) - diese hat er nicht bewiesen ):

Satz XXX: Die folgenden Klassen von Teilfunktionen ... haben dieselben Elemente: (a) die partiellen rekursiven Funktionen, (b) die berechenbaren Funktionen ... " (S. 376)

Definition der "partiellen rekursiven Funktion": "Eine partielle Funktion φ ist in [den Teilfunktionen] ψ ₁ , ... ψ _n partiell rekursiv , wenn es ein Gleichungssystem E gibt, das φ rekursiv aus [Teilfunktionen] ψ ₁ , _{1 definiert} . ... ψ _n "(S. 326)

Nach Kleenes Satz XXX führt entweder die Methode zur Herstellung von Zahlen aus Eingabenummern - rekursive Funktionen, die von Hand berechnet oder von einer Turing-Maschine oder einem Äquivalent berechnet werden - zu einer " effektiv berechenbaren / berechenbaren Funktion". Wenn wir die Hypothese akzeptieren, dass jede Berechnung / Berechnung mit beiden Methoden gleichwertig durchgeführt werden kann, haben wir sowohl Kleenes Theorem XXX (die Äquivalenz) als auch die Church-Turing-These (die Hypothese von "jedem") akzeptiert .

Ein Hinweis auf Dissens: "Es gibt mehr zu Algorithmus ..." Blass und Gurevich (2003)

Der Gedanke, die Thesen von Church und Turing von der "Church-Turing-These" zu trennen, taucht nicht nur in Kleene (1952), sondern auch in Blass-Gurevich (2003) auf. Aber während es Vereinbarungen gibt, gibt es auch Meinungsverschiedenheiten:

"... wir sind mit Kleene nicht einverstanden, dass der Begriff des Algorithmus so gut verstanden wird. Tatsächlich ist der Begriff des Algorithmus heutzutage reicher als zu Turings Zeiten. Und es gibt Algorithmen moderner und klassischer Sorten, die nicht direkt von abgedeckt werden Turings Analyse zum Beispiel Algorithmen, die mit ihrer Umgebung interagieren, Algorithmen, deren Eingaben abstrakte Strukturen sind, und geometrische oder allgemeiner nicht diskrete Algorithmen "(Blass-Gurevich (2003), S. 8, fett gedruckt)

1954 Charakterisierung von AA Markov Jr ..

Andrey Markov Jr. (1954) lieferte die folgende Definition des Algorithmus:

"1. In der Mathematik wird unter" Algorithmus "allgemein eine genaue Vorschrift verstanden, die einen Rechenprozess definiert, der von verschiedenen Anfangsdaten zum gewünschten Ergebnis führt."

"Die folgenden drei Merkmale sind charakteristisch für Algorithmen und bestimmen ihre Rolle in der Mathematik:

"a) die Präzision der Verschreibung, die keinen Platz für Willkür lässt, und ihre universelle Verständlichkeit - die Bestimmtheit des Algorithmus;

"b) die Möglichkeit, mit Anfangsdaten zu beginnen, die innerhalb vorgegebener Grenzen variieren können - die Allgemeinheit des Algorithmus;

"c) die Ausrichtung des Algorithmus auf das Erhalten eines gewünschten Ergebnisses, das tatsächlich am Ende mit geeigneten Anfangsdaten erhalten wird - die Aussagekraft des Algorithmus." (S.1)

Er gab zu, dass diese Definition "keine mathematische Präzision vorgibt" (S. 1). Seine Monographie von 1954 war sein Versuch, den Algorithmus genauer zu definieren; er sah seine resultierende Definition - seinen "normalen" Algorithmus - als "äquivalent zum Konzept einer rekursiven Funktion " (S. 3). Seine Definition umfasste vier Hauptkomponenten (Kapitel II.3, S. 63ff):

"1. Separate Elementarschritte, von denen jeder nach einer der [Substitutions-] Regeln ausgeführt wird ... [zu Beginn gegebene Regeln]

"2. ... Schritte lokaler Natur ... [Somit ändert der Algorithmus nicht mehr als eine bestimmte Anzahl von Symbolen links oder rechts vom beobachteten Wort / Symbol]

"3. Regeln für die Substitutionsformeln ... [er nannte die Liste dieser" das Schema "des Algorithmus]

"4. ... ein Mittel zur Unterscheidung einer" abschließenden Substitution "[dh eines unterscheidbaren" terminalen / endgültigen "Zustands oder von Zuständen]

In seiner Einleitung stellte Markov fest, dass "die gesamte Bedeutung der Bemühungen zur genaueren Definition des Algorithmus für die Mathematik" "im Zusammenhang mit dem Problem einer konstruktiven Grundlage für die Mathematik" stehen würde (S. 2). Ian Stewart (vgl. Encyclopædia Britannica) teilt eine ähnliche Überzeugung: "... konstruktive Analyse entspricht weitgehend dem algorithmischen Geist der Informatik ...". Weitere Informationen finden Sie unter Konstruktive Mathematik und Intuitionismus .

Unterscheidbarkeit und Lokalität : Beide Begriffe tauchten erstmals bei Turing (1936–1937) auf -

"Die neu beobachteten Quadrate müssen vom Computer sofort erkennbar sein [ sic : ein Computer war 1936 eine Person]. Ich halte es für vernünftig anzunehmen, dass es sich nur um Quadrate handeln kann, deren Abstand vom nächsten der sofort beobachteten Quadrate a nicht überschreitet bestimmte feste Menge. Lassen Sie uns bleiben, dass jedes der neu beobachteten Quadrate innerhalb von L Quadraten eines der zuvor beobachteten Quadrate liegt. " (Turing (1936) S. 136 in Davis ed. Undecidable )

Die Lokalität spielt in den Werken von Gurevich und Gandy (1980) (die Gurevich zitiert) eine herausragende Rolle. Gandys "viertes Prinzip für Mechanismen" ist "das Prinzip der lokalen Kausalität":

"Wir kommen nun zu dem wichtigsten unserer Prinzipien. In Turings Analyse beruhte die Anforderung, dass die Handlung nur von einem begrenzten Teil der Aufzeichnung abhängt, auf einer menschlichen Begrenzung. Wir ersetzen diese durch eine physikalische Begrenzung, die wir das Prinzip der lokalen nennen Kausalität. Ihre Rechtfertigung liegt in der endlichen Ausbreitungsgeschwindigkeit von Effekten und Signalen: Die zeitgenössische Physik lehnt die Möglichkeit einer sofortigen Fernwirkung ab. " (Gandy (1980), S. 135 in J. Barwise et al.)

1936, 1963, 1964 Gödels Charakterisierung

1936 : Ein ziemlich berühmtes Zitat von Kurt Gödel erscheint in einem „bei der Korrektur Bemerkung [der ursprünglichen deutschen Veröffentlichung] in seinem Vortrag‚Auf der Länge von Proofs‘übersetzt von Martin Davis , die auf S. 82-83 von. Die Unentscheidbare A. Die Anzahl der Autoren - Kleene, Gurevich, Gandy usw. - hat Folgendes zitiert:

"Somit ist der Begriff" berechenbar "in gewissem Sinne" absolut ", während praktisch alle anderen bekannten metamathematischen Begriffe (z. B. beweisbar, definierbar usw.) ganz wesentlich von dem System abhängen, für das sie definiert sind." (S. 83)

1963 : In einer "Notiz" vom 28. August 1963, die zu seiner berühmten Abhandlung über formal unentscheidbare Sätze (1931) hinzugefügt wurde, erklärt Gödel (in einer Fußnote), dass " formale Systeme " "die charakteristische Eigenschaft haben, die das Denken in ihnen im Prinzip hat". kann vollständig durch mechanische Geräte ersetzt werden "(S. 616 in van Heijenoort). "... aufgrund von" AM Turings Arbeit kann nun eine genaue und zweifellos angemessene Definition des allgemeinen Begriffs des formalen Systems gegeben werden [und] eine vollständig allgemeine Version der Sätze VI und XI ist jetzt möglich. "(S. 616). In einer Notiz von 1964 zu einem anderen Werk äußert er dieselbe Meinung stärker und detaillierter.

1964 : In einem Postscriptum vom 1964 zu einem Papier, das dem Institut für fortgeschrittene Studien im Frühjahr 1934 vorgelegt wurde, bekräftigte Gödel seine Überzeugung, dass "formale Systeme" solche sind, die mechanisiert werden können:

"Infolge späterer Fortschritte, insbesondere der Tatsache, dass aufgrund der Arbeit von AM Turing nun eine genaue und zweifellos angemessene Definition des allgemeinen Konzepts des formalen Systems gegeben werden kann ... Turings Arbeit gibt eine Analyse des Konzepts von" mechanisches Verfahren "(alias" Algorithmus "oder" Rechenverfahren "oder" endliches kombinatorisches Verfahren "). Dieses Konzept entspricht dem einer" Turingmaschine ". * Ein formales System kann einfach als ein beliebiges mechanisches Verfahren definiert werden zur Herstellung von Formeln, die als beweisbare Formeln bezeichnet werden ... " (S. 72 in Martin Davis ed. The Undecidable : "Postscriptum" bis "On Undecidable Propositions of Formal Mathematical Systems", erschienen auf S. 39, aa O.)

Das * kennzeichnet eine Fußnote, in der Gödel die Arbeiten von Alan Turing (1937) und Emil Post (1936) zitiert und anschließend die folgende faszinierende Aussage macht:

"Zu früheren äquivalenten Definitionen der Berechenbarkeit, die jedoch für unseren Zweck viel weniger geeignet sind, siehe Alonzo Church , Am. J. Math., Bd. 58 (1936) [erscheint in The Undecidable S. 100-102]).

Die Definitionen der Kirche umfassen die sogenannte " Rekursion " und den " Lambda-Kalkül " (dh die λ-definierbaren Funktionen). In seiner Fußnote 18 heißt es, dass er das Verhältnis von "effektiver Berechenbarkeit" und "Rekursivität" mit Gödel erörterte, aber unabhängig voneinander "effektive Berechenbarkeit" und "λ-Definierbarkeit" in Frage stellte:

"Wir definieren nun den Begriff ... einer effektiv berechenbaren Funktion positiver Ganzzahlen, indem wir ihn mit dem Begriff einer rekursiven Funktion positiver Ganzzahlen ¹⁸ (oder einer λ-definierbaren Funktion positiver Ganzzahlen) identifizieren .

"Es wurde bereits darauf hingewiesen, dass es für jede Funktion positiver Ganzzahlen, die im soeben definierten Sinne effektiv berechenbar ist, einen Algorithmus zur Berechnung ihres Wertes gibt.

"Umgekehrt ist es wahr ..." (S. 100, The Undecidable).

Daraus und aus dem Folgenden geht hervor, dass für Gödel die Turing-Maschine ausreichend und der Lambda-Kalkül "viel weniger geeignet" war. Er macht weiter darauf aufmerksam, dass die Jury in Bezug auf Einschränkungen der menschlichen Vernunft immer noch nicht besetzt ist:

("Beachten Sie, dass die Frage, ob es endliche nichtmechanische Verfahren ** gibt, die mit keinem Algorithmus gleichwertig sind, überhaupt nichts mit der Angemessenheit der Definition des" formalen Systems "und des" mechanischen Verfahrens "zu tun hat.) (S. 72, loc. Cit.)

"(Für Theorien und Verfahren im allgemeineren Sinne, die in Fußnote ** angegeben sind, kann die Situation anders sein. Beachten Sie, dass die im Nachsatz genannten Ergebnisse keine Grenzen für die Kräfte der menschlichen Vernunft festlegen, sondern für die Möglichkeiten des reinen Formalismus in Mathematik.) (S. 73 loc. cit.)

Fußnote **: "Das heißt, die Verwendung abstrakter Begriffe aufgrund ihrer Bedeutung. Siehe meine Arbeit in Dial. 12 (1958), S. 280." (Diese Fußnote erscheint auf S. 72, aa O.).

1967 Minskys Charakterisierung

Minsky (1967) behauptet kahlköpfig, dass "ein Algorithmus" eine effektive Prozedur ist "und lehnt es ab, das Wort" Algorithmus "weiter in seinem Text zu verwenden. Tatsächlich macht sein Index deutlich, was er über" Algorithmus, Synonym für effektive Prozedur " empfindet ( S. 311):

"Wir werden den letzteren Begriff [ein effektives Verfahren ] in der Folge verwenden. Die Begriffe sind ungefähr synonym, aber es gibt eine Reihe von Bedeutungsschattierungen, die in verschiedenen Kontexten verwendet werden, insbesondere für 'Algorithmus'" (kursiv im Original, S. 105) )

Andere Autoren (siehe Knuth unten) verwenden das Wort "effektives Verfahren". Dies führt zu der Frage: Was ist Minskys Vorstellung von "einem effektiven Verfahren"? Er beginnt mit:

"... eine Reihe von Regeln, die uns von Moment zu Moment genau sagen, wie wir uns verhalten sollen" (S. 106)

Er erkennt jedoch, dass dies Gegenstand einer Kritik ist:

"... die Kritik, dass die Auslegung der Regeln von einer Person oder einem Agenten abhängt" (S. 106)

Seine Verfeinerung? "Zusammen mit der Erklärung der Regeln die Details des Mechanismus angeben, der sie interpretieren soll ". Um den "umständlichen" Prozess zu vermeiden, "dies für jedes einzelne Verfahren noch einmal wiederholen zu müssen", hofft er, eine "einigermaßen einheitliche Familie von Mechanismen zur Einhaltung von Regeln " zu identifizieren . Seine "Formulierung":

"(1) eine Sprache, in der Verhaltensregeln ausgedrückt werden sollen, und

"(2) eine einzelne Maschine, die Anweisungen in der Sprache interpretieren und somit die Schritte jedes spezifizierten Prozesses ausführen kann." (kursiv im Original, alle Zitate dieses Abs. S. 107)

Am Ende befürchtet er jedoch immer noch, dass "die Angelegenheit einen subjektiven Aspekt hat. Verschiedene Personen sind sich möglicherweise nicht einig, ob ein bestimmtes Verfahren als wirksam bezeichnet werden sollte" (S. 107).

Aber Minsky lässt sich nicht abschrecken. Er führt sofort "Turings Analyse des Berechnungsprozesses" ein (sein Kapitel 5.2). Er zitiert, was er "Turings These " nennt.

"Jeder Prozess, der natürlich als effektives Verfahren bezeichnet werden könnte, kann von einer Turing-Maschine realisiert werden" (S. 108. (Minsky kommentiert, dass dies in einer allgemeineren Form als " Kirchenthese " bezeichnet wird).

Nach einer Analyse von "Turings Argument" (sein Kapitel 5.3) stellt er fest, dass "die Gleichwertigkeit vieler intuitiver Formulierungen" von Turing, Church, Kleene, Post und Smullyan "... uns zu der Annahme führt, dass es hier wirklich ein Ziel gibt "oder" absolute "Vorstellung. Wie Rogers [1959] es ausdrückte:

"In diesem Sinne ist der Begriff der effektiv berechenbaren Funktion eines der wenigen 'absoluten' Konzepte, die moderne Arbeiten in den Grundlagen der Mathematik hervorbringen" (Minsky, S. 111, zitiert Rogers, Hartley Jr. (1959). Die vorliegende Theorie der Turing-Maschine Berechenbarkeit , J. SIAM 7, 114-130.)

1967 Rogers 'Charakterisierung

In seiner Theorie der rekursiven Funktionen und der effektiven Berechenbarkeit von 1967 charakterisiert Hartley Rogers "Algorithmus" grob als "ein klerikales (dh deterministisches, buchhalterisches) Verfahren ..., das auf ... symbolische Eingaben angewendet wird und das sich letztendlich für jede dieser Eingaben ergibt eine entsprechende symbolische Ausgabe "(S. 1). Anschließend beschreibt er den Begriff "in ungefähren und intuitiven Begriffen" mit 10 "Merkmalen", von denen er behauptet, dass "praktisch alle Mathematiker zustimmen würden" (S. 2). Die verbleibenden 5, die er behauptet, "sind weniger offensichtlich als * 1 bis * 5 und über die wir möglicherweise weniger allgemeine Übereinstimmung finden" (S. 3).

Die 5 "offensichtlichen" sind:

• 1 Ein Algorithmus ist eine Reihe von Anweisungen endlicher Größe.
• 2 Es gibt einen fähigen Computeragenten.
• 3 "Es gibt Möglichkeiten zum Ausführen, Speichern und Abrufen von Schritten in einer Berechnung."
• 4 Bei Nr. 1 und Nr. 2 berechnet der Agent "diskret schrittweise" ohne Verwendung kontinuierlicher Methoden oder analoger Geräte ",
• 5 Der Computeragent führt die Berechnung "ohne Rückgriff auf zufällige Methoden oder Geräte, z. B. Würfel", weiter (in einer Fußnote fragt sich Rogers, ob # 4 und # 5 wirklich gleich sind).

Die verbleibenden 5, die er zur Debatte öffnet, sind:

• 6 Keine feste Grenze für die Größe der Eingänge,
• 7 Keine feste Grenze für die Größe des Befehlssatzes,
• 8 Keine feste Grenze für den verfügbaren Speicherplatz,
• 9 Eine feste endliche Grenze, die an die Kapazität oder Fähigkeit des Rechenagenten gebunden ist (Rogers veranschaulicht anhand eines Beispiels einfache Mechanismen, die einer Post-Turing-Maschine oder einer Gegenmaschine ähnlich sind ).
• 10 Eine Grenze für die Länge der Berechnung - "Sollten wir vorab eine Vorstellung davon haben, wie lange die Berechnung dauern wird?" (S. 5). Rogers verlangt "nur, dass eine Berechnung nach einer endlichen Anzahl von Schritten beendet wird; wir bestehen nicht auf einer a priori Fähigkeit, diese Anzahl zu schätzen." (S. 5).

1968, 1973 Knuths Charakterisierung

Knuth (1968, 1973) hat eine Liste von fünf Eigenschaften angegeben, die als Anforderungen für einen Algorithmus allgemein anerkannt sind:

1. Endlichkeit : "Ein Algorithmus muss immer nach einer endlichen Anzahl von Schritten enden ... eine sehr endliche Zahl, eine vernünftige Zahl."
2. Bestimmtheit : "Jeder Schritt eines Algorithmus muss genau definiert sein; die auszuführenden Aktionen müssen für jeden Fall streng und eindeutig festgelegt werden."
3. Eingabe : "... Mengen, die ihm vor Beginn des Algorithmus gegeben werden. Diese Eingaben stammen aus bestimmten Objektgruppen."
4. Ausgabe : "... Mengen, die eine bestimmte Beziehung zu den Eingaben haben"
5. Wirksamkeit : "... alle im Algorithmus auszuführenden Operationen müssen so grundlegend sein, dass sie im Prinzip von einem Mann mit Papier und Bleistift genau und in endlicher Zeit ausgeführt werden können."

Knuth bietet als Beispiel den euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier natürlicher Zahlen an (vgl. Knuth Vol. 1 S. 2).

Knuth gibt zu, dass seine Beschreibung eines Algorithmus zwar intuitiv klar sein mag, ihm jedoch die formale Genauigkeit fehlt, da nicht genau klar ist, was "genau definiert" oder "streng und eindeutig spezifiziert" oder "ausreichend grundlegend" bedeutet, und so weiter her. In seinem ersten Band bemüht er sich in diese Richtung, wo er detailliert definiert, was er die " Maschinensprache " für seinen "mythischen MIX ... den ersten mehrfach ungesättigten Computer der Welt " nennt (S. 120ff). Viele der Algorithmen in seinen Büchern sind in der MIX-Sprache geschrieben. Er verwendet auch Baumdiagramme , Flussdiagramme und Zustandsdiagramme .

"Güte" eines Algorithmus, "beste" Algorithmen : Knuth erklärt: "In der Praxis wollen wir nicht nur Algorithmen, wir wollen gute Algorithmen ..." Er schlägt vor, dass einige Kriterien für die Güte eines Algorithmus die Anzahl der auszuführenden Schritte sind der Algorithmus, seine "Anpassungsfähigkeit an Computer, seine Einfachheit und Eleganz usw." Welcher ist bei einer Reihe von Algorithmen zur Durchführung derselben Berechnung "am besten"? Er nennt diese Art der Untersuchung "algorithmische Analyse: einen Algorithmus gegeben, um dessen Leistungscharakteristik zu bestimmen" (alle zitieren diesen Absatz: Knuth Vol. 1 S. 7)

1972 Stones Charakterisierung

Stone (1972) und Knuth (1968, 1973) waren gleichzeitig Professoren an der Stanford University, so dass es nicht verwunderlich ist, wenn ihre Definitionen Ähnlichkeiten aufweisen (Fettdruck zur Hervorhebung hinzugefügt):

"Zusammenfassend ... definieren wir einen Algorithmus als einen Satz von Regeln , der eine Folge von Operationen genau definiert, so dass jede Regel effektiv und eindeutig ist und die Folge in einer endlichen Zeit endet ." (Fettdruck hinzugefügt, S. 8)

Stein ist bemerkenswert wegen seiner ausführlichen Diskussion dessen , was eine „wirksame“ -Regel - seine Roboter oder Person-acting as-Roboter, müssen einige haben Informationen und Fähigkeiten innerhalb ihnen, und wenn nicht die Informationen und die Möglichkeit vorgesehen werden in "der Algorithmus":

"Damit Menschen den Regeln eines Algorithmus folgen können, müssen die Regeln so formuliert werden, dass sie roboterartig befolgt werden können, dh ohne nachzudenken ... jedoch, wenn die Anweisungen [zum Lösen des Quadrats" vorliegen Gleichung, sein Beispiel] soll von jemandem befolgt werden, der weiß, wie man arithmetische Operationen ausführt, aber nicht weiß, wie man eine Quadratwurzel extrahiert, dann müssen wir auch eine Reihe von Regeln zum Extrahieren einer Quadratwurzel bereitstellen, um die Definition von zu erfüllen Algorithmus "(S. 4-5)

Darüber hinaus "... sind nicht alle Anweisungen akzeptabel , da sie möglicherweise erfordern, dass der Roboter über Fähigkeiten verfügt, die über die von uns als angemessen erachteten hinausgehen ." Er gibt das Beispiel eines Roboters, der mit der Frage konfrontiert ist: "Henry VIII ein König von England?" und 1 zu drucken, wenn ja, und 0, wenn nein, aber der Roboter wurde zuvor nicht mit diesen Informationen versorgt. Und schlimmer noch, wenn der Roboter gefragt wird, ob Aristoteles ein König von England war und der Roboter nur mit fünf Namen versehen wurde, wurde er würde nicht wissen, wie man antwortet. Also:

„Eine intuitive Definition einer akzeptablen Folge von Anweisungen ist eine, bei der jede Anweisung genau definiert ist, damit der Roboter garantiert in der Lage ist, sie zu befolgen “ (S. 6).

Nachdem Stone uns seine Definition gegeben hat, stellt er das Turing-Maschinenmodell vor und gibt an, dass der Satz von fünf Tupeln, die die Anweisungen der Maschine sind, „ein Algorithmus ... bekannt als Turing-Maschinenprogramm“ ist (S. 9). Unmittelbar danach sagt er weiter, dass eine „ Berechnung einer Turing-Maschine beschrieben wird, indem Folgendes angegeben wird:

"1. Das Bandalphabet

"2. Die Form, in der die [Eingabe] -Parameter auf dem Band angezeigt werden

"3. Der Ausgangszustand der Turingmaschine

"4. Die Form, in der die Antworten [Ausgabe] auf dem Band dargestellt werden, wenn die Turing-Maschine anhält

"5. Das Maschinenprogramm" (kursiv, S. 10)

Diese genaue Vorschrift dessen, was für "eine Berechnung" erforderlich ist, entspricht dem, was in der Arbeit von Blass und Gurevich folgen wird.

1995 Soares Charakterisierung

"Eine Berechnung ist ein Prozess, bei dem wir von anfänglich gegebenen Objekten, die als Eingaben bezeichnet werden , nach einem festgelegten Regelwerk, das als Programm, Prozedur oder Algorithmus bezeichnet wird , durch eine Reihe von Schritten fortfahren und mit einem Finale zum Ende dieser Schritte gelangen Ergebnis, als Ausgabe bezeichnet . Der Algorithmus als ein Satz von Regeln, die von Eingaben zu Ausgaben gehen, muss präzise und eindeutig sein, wobei jeder aufeinanderfolgende Schritt klar bestimmt wird. Das Konzept der Berechenbarkeit betrifft diejenigen Objekte, die im Prinzip durch Berechnungen spezifiziert werden können. "(kursiv im Original, fett gedruckt S. 3)

2000 Berlinskis Charakterisierung

Während seines Studiums in Princeton Mitte der 1960er Jahre war David Berlinski Schüler der Alonzo Church (vgl. S. 160). Sein 2000 erschienenes Buch Das Aufkommen des Algorithmus: Die 300-jährige Reise von einer Idee zum Computer enthält die folgende Definition des Algorithmus :

" In der Stimme des Logikers:

" Ein Algorithmus ist

ein endliches Verfahren,

geschrieben in einem festen symbolischen Vokabular,

durch genaue Anweisungen geregelt,

in diskreten Schritten bewegen, 1, 2, 3 ,. . .,

deren Ausführung erfordert keine Einsicht, Klugheit,

Intuition, Intelligenz oder Scharfsinn,

und das geht früher oder später zu Ende. "(fett und kursiv im Original, S. xviii)

2000, 2002 Gurevichs Charakterisierung

Eine sorgfältige Lektüre von Gurevich 2000 führt zu dem Schluss (schlussfolgern?), Dass er glaubt, dass "ein Algorithmus" tatsächlich "eine Turing-Maschine" oder "eine Zeiger-Maschine " ist, die eine Berechnung durchführt. Ein "Algorithmus" ist nicht nur die Symboltabelle, die das Verhalten der Maschine steuert, noch ist es nur eine Instanz einer Maschine, die eine Berechnung mit einem bestimmten Satz von Eingabeparametern durchführt, noch ist es eine geeignet programmierte Maschine mit ausgeschaltetem Gerät ;; Vielmehr ist ein Algorithmus die Maschine, die tatsächlich jede Berechnung durchführt, zu der sie fähig ist . Gurewitsch kommt nicht gleich heraus und sagt dies, so wie oben formuliert, ist diese Schlussfolgerung (Folgerung?) Mit Sicherheit offen für Debatten:

"... jeder Algorithmus kann von einer Turing-Maschine simuliert werden ... ein Programm kann simuliert werden und daher von einer Turing-Maschine eine genaue Bedeutung erhalten." (S. 1)

"Es wird oft angenommen, dass das Problem der Formalisierung des Begriffs des sequentiellen Algorithmus von Church [1936] und Turing [1936] gelöst wurde. Beispielsweise ist nach Savage [1987] ein Algorithmus ein Rechenprozess , der von einer Turing-Maschine definiert wird. Church und Turing haben das Problem der Formalisierung des Begriffs des sequentiellen Algorithmus nicht gelöst. Stattdessen gaben sie (unterschiedliche, aber äquivalente) Formalisierungen des Begriffs der berechenbaren Funktion an, und ein Algorithmus enthält mehr als die von ihm berechnete Funktion. 3)

"Natürlich sind die Begriffe Algorithmus und berechenbare Funktion eng miteinander verbunden: Per Definition ist eine berechenbare Funktion eine Funktion, die durch einen Algorithmus berechenbar ist ... (S. 4)

In Blass und Gurevich 2002 berufen sich die Autoren auf einen Dialog zwischen "Quisani" ("Q") und "Autoren" (A), wobei Yiannis Moshovakis als Folie verwendet wird.

" A: Um die Meinungsverschiedenheit zu lokalisieren, erwähnen wir zunächst zwei Übereinstimmungspunkte. Erstens gibt es einige Dinge, die offensichtlich nach jedermanns Definition Algorithmen sind - Turing-Maschinen, zeitgesteuerte ASMs [Abstract State Machines] und dergleichen. Zweitens sind es Spezifikationen, die nach jedermanns Definition nicht als Algorithmen angesehen werden, da sie keinen Hinweis darauf geben, wie etwas berechnet werden soll. Das Problem ist, wie detailliert die Informationen sein müssen, um als Algorithmus zu gelten ... Moshovakis erlaubt einige Dinge, die wir nur als deklarative Spezifikationen bezeichnen würden, und er würde wahrscheinlich das Wort "Implementierung" für Dinge verwenden, die wir Algorithmen nennen. " (Absätze zur besseren Lesbarkeit zusammengefügt, 2002: 22)

Diese Verwendung des Wortes "Implementierung" bringt die Frage auf den Punkt. Zu Beginn der Zeitung gibt Q seine Lesart von Moshovakis an:

"... [H] er würde wahrscheinlich denken, dass Ihre praktische Arbeit [Gurevich arbeitet für Microsoft] Sie dazu zwingt, mehr an Implementierungen als an Algorithmen zu denken. Er ist durchaus bereit, Implementierungen mit Maschinen zu identifizieren, aber er sagt, dass Algorithmen etwas mehr sind Allgemeines. Es läuft darauf hinaus, dass Sie sagen, ein Algorithmus sei eine Maschine, und Moschovakis sagt, dass dies nicht der Fall ist. " (2002: 3)

Aber die Autoren waffeln hier und sagen "[L] et hält sich an" Algorithmus "und" Maschine ", und der Leser ist wieder verwirrt. Wir müssen bis Dershowitz und Gurevich 2007 warten, um den folgenden Fußnotenkommentar zu erhalten:

"... Wenn man jedoch den Standpunkt von Moshovakis akzeptiert, dann ist es die" Implementierung "von Algorithmen, die wir charakterisieren wollen." (Vgl. Fußnote 9 2007: 6)

2003 Blass und Gurevichs Charakterisierung

Blass und Gurevich beschreiben ihre Arbeit als entwickelt aus der Betrachtung von Turing-Maschinen und Zeigermaschinen , insbesondere Kolmogorov-Uspensky-Maschinen (KU-Maschinen), Schönhage Storage Modification Machines (SMM) und Verknüpfungsautomaten, wie sie von Knuth definiert wurden. Die Arbeiten von Gandy und Markov werden auch als einflussreiche Vorläufer beschrieben.

Gurevich bietet eine "starke" Definition eines Algorithmus (Fettdruck hinzugefügt):

"... Turings informelles Argument für seine These rechtfertigt eine stärkere These: Jeder Algorithmus kann von einer Turing-Maschine simuliert werden ... In der Praxis wäre es lächerlich ... [Trotzdem] [c] eine Verallgemeinerung Turing-Maschinen, damit jeder Algorithmus, egal wie abstrakt, von einer verallgemeinerten Maschine modelliert werden kann? ... Aber nehmen wir an, dass solche verallgemeinerten Turing-Maschinen existieren. Wie würden ihre Zustände sein? ... eine Struktur erster Ordnung ... eine bestimmte Ein kleiner Befehlssatz reicht in allen Fällen aus ... Berechnung als Entwicklung des Zustands ... könnte nicht deterministisch sein ... kann mit ihrer Umgebung interagieren ... [könnte] parallel und multiagent sein ... [könnte] dynamische Semantik ... [die beiden Grundlagen ihrer Arbeit sind:] Turings These ... [und] der Begriff der Struktur (erster Ordnung) von [Tarski 1933] "(Gurevich 2000, S. 1-2)

Die obige Phrasenberechnung als Entwicklung des Zustands unterscheidet sich deutlich von der Definition von Knuth und Stone - dem "Algorithmus" als Turing-Maschinenprogramm. Sie entspricht vielmehr dem, was Turing die vollständige Konfiguration nannte (vgl. Turings Definition in Undecidable, S. 118) - und enthält sowohl den aktuellen Befehl (Status) als auch den Status des Bandes. [vgl. Kleene (1952) p. 375 wo er ein Beispiel eines Bandes mit 6 Symbolen zeigt - alle anderen Quadrate sind leer - und wie man seinen kombinierten Tischbandstatus Gödelisiert].

In Algorithmusbeispielen sehen wir die Entwicklung des Zustands aus erster Hand.

1995 - Daniel Dennett: Evolution als algorithmischer Prozess

Der Philosoph Daniel Dennett analysiert in seinem 1995 erschienenen Buch Darwins gefährliche Idee die Bedeutung der Evolution als algorithmischen Prozess . Dennett identifiziert drei Hauptmerkmale eines Algorithmus:

• Substratneutralität : Ein Algorithmus beruht auf seiner logischen Struktur. Daher ist die besondere Form, in der sich ein Algorithmus manifestiert, nicht wichtig (Dennetts Beispiel ist die lange Teilung: Sie funktioniert genauso gut auf Papier, Pergament, Computerbildschirm oder unter Verwendung von Neonlichtern oder beim Skywriting). (S. 51)
• Grundlegende Gedankenlosigkeit : Egal wie kompliziert das Endprodukt des algorithmischen Prozesses sein mag, jeder Schritt im Algorithmus ist ausreichend einfach, um von einem nicht empfindungsfähigen mechanischen Gerät ausgeführt zu werden. Der Algorithmus benötigt kein "Gehirn", um ihn zu warten oder zu betreiben. „Die Standard - Lehrbuch Analogie stellt fest , dass Algorithmen sind Rezepte von Art, entworfen von befolgt werden unerfahrene Köche. . “ (S. 51)
• Garantierte Ergebnisse : Wenn der Algorithmus korrekt ausgeführt wird, werden immer die gleichen Ergebnisse erzielt. "Ein Algorithmus ist ein narrensicheres Rezept." (S. 51)

Auf der Grundlage dieser Analyse kommt Dennett zu dem Schluss, dass "Evolution nach Darwin ein algorithmischer Prozess ist". (S. 60).

Auf der vorherigen Seite ist er jedoch viel weiter gegangen. Im Zusammenhang mit seinem Kapitel "Prozesse als Algorithmen" stellt er fest:

"Aber dann ... gibt es überhaupt Grenzen für das, was als algorithmischer Prozess angesehen werden kann? Ich denke, die Antwort lautet NEIN. Wenn Sie möchten, können Sie jeden Prozess auf abstrakter Ebene als algorithmischen Prozess behandeln ... Wenn was Rätselhaft ist die Gleichmäßigkeit der Sandkörner des Ozeans oder die Stärke der Klinge aus gehärtetem Stahl. Eine algorithmische Erklärung wird Ihre Neugier befriedigen - und es wird die Wahrheit sein.

„Egal , wie beeindruckend die Produkte eines Algorithmus, der zugrunde liegende Prozess besteht immer aus nichts anderes als eine Reihe von individualy [ sic ] sinnlosen Schritten sie ohne die Hilfe einer intelligenten Überwachung gelingen, sie sind‚automatisch‘definitionsgemäß : die Funktionsweise ein Automat. " (S. 59)

Es ist unklar , aus den oben , ob Dennett ist die besagt , dass die physische Welt für sich allein und ohne Beobachter ist intrinsisch algorithmischen (Computational) , oder ob ein Symbol Verarbeitung Beobachter ist , was mit den Beobachtungen „ im Sinne von “ hinzufügt.

2002 John Searle fügt Dennetts Charakterisierung eine klarstellende Einschränkung hinzu

Daniel Dennett ist ein Befürworter einer starken künstlichen Intelligenz : Die Idee, dass die logische Struktur eines Algorithmus ausreicht, um den Geist zu erklären . John Searle , der Schöpfer des chinesischen Raumgedankenexperiments , behauptet, dass "die Syntax [ dh die logische Struktur] allein für semantischen Inhalt [dh Bedeutung] nicht ausreicht " ( Searle 2002 , S. 16). Mit anderen Worten, die "Bedeutung" von Symbolen ist relativ zu dem Verstand, der sie verwendet; Ein Algorithmus - ein logisches Konstrukt - allein reicht für einen Geist nicht aus.

Diejenigen Searle warnt , die behaupten , dass algorithmische (Computational) Prozesse sind intrinsische zur Natur (zum Beispiel Kosmologen, Physiker, Chemiker, etc.):

Die Berechnung [...] ist beobachterbezogen, und dies liegt daran, dass die Berechnung als Symbolmanipulation definiert wird, der Begriff „Symbol“ jedoch kein Begriff der Physik oder Chemie ist. Etwas ist nur dann ein Symbol, wenn es als Symbol verwendet, behandelt oder betrachtet wird. Das chinesische Raumargument zeigte, dass die Semantik der Syntax nicht eigen ist. Dies zeigt jedoch, dass die Syntax der Physik nicht eigen ist. [...] Etwas ist ein Symbol nur in Bezug auf einen Beobachter, Benutzer oder Agenten, der ihm eine symbolische Interpretation zuweist. [...] Sie können allem eine rechnerische Interpretation zuweisen. Aber wenn die Frage lautet: "Ist das Bewusstsein an sich rechnerisch?" Die Antwort lautet: Nichts ist an sich rechnerisch [zur Hervorhebung kursiv]. Die Berechnung existiert nur relativ zu einem Agenten oder Beobachter, der einem Phänomen eine rechnerische Interpretation auferlegt. Dies ist ein offensichtlicher Punkt. Ich hätte es vor zehn Jahren sehen sollen, aber ich habe es nicht getan.

-  John Searle, Searle 2002 , p. 17

2002: Boolos-Burgess-Jeffrey-Spezifikation der Turing-Maschinenberechnung

Beispiele für diese Spezifikationsmethode, die auf den Additionsalgorithmus "m + n" angewendet wird, finden Sie unter Algorithmusbeispiele .

Ein Beispiel in Boolos-Burgess-Jeffrey (2002) (S. 31–32) zeigt die Genauigkeit, die für eine vollständige Spezifikation eines Algorithmus erforderlich ist, in diesem Fall um zwei Zahlen hinzuzufügen: m + n. Es ähnelt den oben genannten Steinanforderungen.

(i) Sie haben die Rolle des "Zahlenformats" bei der Berechnung erörtert und die "Tally-Notation" ausgewählt, um Zahlen darzustellen:

"Sicherlich kann die Berechnung in der Praxis mit einigen Notationen schwieriger sein als mit anderen ... Aber ... es ist im Prinzip möglich, in jeder anderen Notation einfach die Daten zu übersetzen ... Zum Zwecke der Festlegung eines streng definierten Begriffs der Berechenbarkeit ist es zweckmäßig, die Monadic- oder Tally-Notation zu verwenden "(S. 25-26)

(ii) Zu Beginn ihres Beispiels geben sie die Maschine an, die bei der Berechnung als Turing-Maschine verwendet werden soll . Sie haben zuvor festgelegt (S. 26), dass die Turing-Maschine eher aus 4-Tupel als aus 5-Tupel besteht. Weitere Informationen zu dieser Konvention finden Sie unter Turingmaschine .

(iii) Zuvor haben die Autoren angegeben, dass die Position des Bandkopfs durch einen Index rechts neben dem gescannten Symbol angezeigt wird . Weitere Informationen zu dieser Konvention finden Sie unter Turingmaschine . (Im Folgenden wird zur Hervorhebung Fettdruck hinzugefügt):

"Wir haben keine offizielle Definition gegeben, was es bedeutet, dass eine numerische Funktion von einer Turing-Maschine berechnet werden kann, und angegeben, wie Eingaben oder Argumente auf der Maschine dargestellt werden sollen und wie Ausgaben oder Werte dargestellt werden sollen. Unsere Spezifikationen für eine k- Die Platzierungsfunktion von positiven Ganzzahlen zu positiven Ganzzahlen lautet wie folgt:

"(a) [ Anfangszahlformat: ] Die Argumente m ₁ , ... m _k , ... werden in monadischer [unärer] Notation durch Blöcke dieser Anzahl von Strichen dargestellt, wobei jeder Block durch einen einzelnen vom nächsten getrennt ist leer, auf einem ansonsten leeren Band.

Beispiel: 3 + 2, 111B11

"(b) [ Anfangskopfposition, Anfangszustand: ] Zu Beginn scannt das Gerät die am weitesten links stehende 1 auf dem Band und befindet sich in ihrem Anfangszustand, Zustand 1.

Beispiel: 3 + 2, 1 ₁ 111B11

"(c) [ Erfolgreiche Berechnung - Zahlenformat bei Halt: ] Wenn die zu berechnende Funktion den Argumenten, die anfänglich auf dem Band dargestellt sind, einen Wert n zuweist, stoppt die Maschine schließlich auf einem Band, das einen Strichblock enthält und sonst leer ...

Beispiel: 3 + 2, 11111

"(d) [ Erfolgreiche Berechnung - Kopfposition bei Halt: ] In diesem Fall [c] stoppt das Gerät das Scannen der am weitesten links stehenden 1 auf dem Band ...

Beispiel: 3 + 2, 1 _n 1111

"(e) [ Nicht erfolgreiche Berechnung - Fehler beim Anhalten oder Anhalten mit einem nicht standardmäßigen Zahlenformat: ] Wenn die zu berechnende Funktion den Argumenten, die anfänglich auf dem Band dargestellt sind, keinen Wert zuweist, wird der Computer dies auch niemals tun anhalten oder in einer nicht standardmäßigen Konfiguration anhalten ... "(ebenda)

Beispiel: B _n 11111 oder B11 _n 111 oder B11111 _n

Diese Spezifikation ist unvollständig: Sie erfordert den Ort, an dem die Anweisungen platziert werden sollen, und ihr Format in der Maschine.

(iv) in der TABELLE der Finite-State-Maschine oder im Fall einer Universal-Turing-Maschine auf dem Band und

(v) die Anweisungstabelle in einem bestimmten Format

Dieser spätere Punkt ist wichtig. Boolos-Burgess-Jeffrey demonstrieren (S. 36), dass die Vorhersagbarkeit der Einträge in der Tabelle es ermöglicht, die Tabelle zu "verkleinern", indem die Einträge nacheinander angeordnet und der Eingabestatus und das Symbol weggelassen werden. Für die Beispielberechnung der Turing-Maschine waren in der Tat nur die 4 Spalten erforderlich, wie in der folgenden Tabelle gezeigt (Hinweis: Diese wurden der Maschine in Zeilen dargestellt ):

Zustand qk	Gescanntes Symbol	Aktion	Nächster Zustand qk		Zustand qn	Gescanntes Symbol	Aktion	Nächster Zustand qk		Zustand qk	B-Aktion	B-nächster Zustand qkB	1 Aktion	1: nächster Zustand 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: Sipsers Behauptung und seine drei Beschreibungsebenen

Beispiele für diese Spezifikationsmethode, die auf den Additionsalgorithmus "m + n" angewendet wird, finden Sie unter Algorithmusbeispiele .

Sipser definiert zunächst den "Algorithmus" wie folgt:

"Informell gesehen ist ein Algorithmus eine Sammlung einfacher Anweisungen zur Ausführung einer Aufgabe. Im Alltag werden Algorithmen manchmal als Prozeduren oder Rezepte bezeichnet (im Original kursiv, S. 154).

"... unser eigentlicher Fokus liegt von nun an auf Algorithmen. Das heißt, die Turing-Maschine dient lediglich als präzises Modell für die Definition des Algorithmus. Wir müssen uns nur mit Turing-Maschinen so gut auskennen, dass wir glauben, dass sie erfassen." alle Algorithmen "(S. 156)

Bedeutet Sipser, dass "Algorithmus" nur "Anweisungen" für eine Turingmaschine sind, oder ist die Kombination von "Anweisungen + eine (bestimmte Vielfalt von) Turingmaschinen"? Zum Beispiel definiert er die beiden Standardvarianten (Multi-Tape und nicht deterministisch) seiner speziellen Variante (nicht dasselbe wie Turings Original) und beschreibt in seinen Problemen (Seiten 160-161) vier weitere Varianten ( Einmal schreiben, doppelt unendliches Band (dh links und rechts unendlich), links zurücksetzen und "bleiben statt links bleiben"). Außerdem legt er einige Einschränkungen fest. Erstens muss die Eingabe als Zeichenfolge codiert werden (p. 157) und sagt über numerische Kodierungen im Kontext der Komplexitätstheorie:

"Beachten Sie jedoch, dass eine unäre Notation zum Codieren von Zahlen (wie in der durch die unäre Nummer 11111111111111111 codierten Nummer 17) nicht sinnvoll ist, da sie exponentiell größer ist als wirklich vernünftige Codierungen, wie z. B. die Basis- k- Notation für k ≥ 2." (S. 259)

Van Emde Boas kommentiert ein ähnliches Problem in Bezug auf das abstrakte Berechnungsmodell der Direktzugriffsmaschine (RAM), das manchmal anstelle der Turing-Maschine verwendet wird, wenn eine "Analyse von Algorithmen" durchgeführt wird: "Das Fehlen oder Vorhandensein einer multiplikativen und parallelen Bitmanipulation Operationen sind für das korrekte Verständnis einiger Ergebnisse bei der Analyse von Algorithmen von Bedeutung.

"... [T] existiert hier kaum so etwas wie eine" unschuldige "Erweiterung des Standard-RAM-Modells in den einheitlichen Zeitmaßen; entweder hat man nur additive Arithmetik oder man könnte genauso gut alle vernünftigen multiplikativen und / oder bitweisen einschließen Boolesche Anweisungen für kleine Operanden. " (Van Emde Boas, 1990: 26)

In Bezug auf eine "Beschreibungssprache" für Algorithmen beendet Sipser die Arbeit, die Stone und Boolos-Burgess-Jeffrey begonnen haben (Fettdruck hinzugefügt). Er bietet uns drei Beschreibungsebenen für Turing-Maschinenalgorithmen an (S. 157):

Beschreibung auf hoher Ebene : "wobei wir ... Prosa verwenden, um einen Algorithmus zu beschreiben, wobei die Implementierungsdetails ignoriert werden. Auf dieser Ebene müssen wir nicht erwähnen, wie die Maschine ihr Band oder ihren Kopf verwaltet."

Implementierungsbeschreibung : "In der wir ... Prosa verwenden, um zu beschreiben, wie die Turing-Maschine ihren Kopf bewegt und wie sie Daten auf ihrem Band speichert. Auf dieser Ebene geben wir keine Details zu Zuständen oder Übergangsfunktionen an."

Formale Beschreibung : "... die niedrigste, detaillierteste Beschreibungsebene ... die die Zustände, die Übergangsfunktion usw. der Turing-Maschine vollständig beschreibt."

Anmerkungen

Verweise

• David Berlinski (2000), Das Aufkommen des Algorithmus: Die 300-jährige Reise von einer Idee zum Computer , Harcourt, Inc., San Diego, ISBN   0-15-601391-6 (pbk.)
• George Boolos , John P. Burgess , Richard Jeffrey (2002), Berechenbarkeit und Logik: Vierte Ausgabe , Cambridge University Press, Cambridge, UK. ISBN   0-521-00758-5 (pbk).
• Andreas Blass und Yuri Gurevich (2003), Algorithmen: Eine Suche nach absoluten Definitionen , Bulletin der Europäischen Vereinigung für Theoretische Informatik 81, 2003. Enthält eine ausgezeichnete Bibliographie mit 56 Referenzen.
• Burgin, M. Superrekursive Algorithmen , Monographien in der Informatik, Springer, 2005. ISBN   0-387-95569-0
• Davis, Martin (1958). Berechenbarkeit und Unlösbarkeit . New York: McGraw-Hill Book Company, Inc. . Eine Quelle wichtiger Definitionen und einiger maschinenbasierter Turing-Algorithmen für einige rekursive Funktionen.
• Davis, Martin (1965). Das Unentscheidbare: Grundlegende Papiere zu unentscheidbaren Aussagen, unlösbaren Problemen und berechenbaren Funktionen . New York: Raven Press. Davis gibt vor jedem Artikel einen Kommentar. Papiere von Gödel , Alonzo Church , Turing , Rosser , Kleene und Emil Post sind enthalten.
• Dennett, Daniel (1995). Darwins gefährliche Idee . New York: Touchstone / Simon & Schuster.
• Robin Gandy , These und Prinzipien der Kirche für Mechanismen , in J. Barwise , HJ Keisler und K. Kunen , Hrsg., The Kleene Symposium , North-Holland Publishing Company 1980), S. 123–148. Gandys berühmte "4 Prinzipien von [Rechen-] Mechanismen" beinhalten "Prinzip IV - Das Prinzip der lokalen Kausalität".
• Yuri Gurevich , Sequentielle abstrakte Zustandsmaschinen erfassen sequentielle Algorithmen , ACM-Transaktionen auf Computerlogik, Band 1, Nr. 1 (Juli 2000), Seiten 77–111. Enthält eine Bibliographie mit 33 Quellen.
• Kleene C., Stephen (1943). "Rekursive Prädikate und Quantifizierer" . Transaktionen der American Mathematical Society . Transaktionen der American Mathematical Society, Vol. 53, No. 1. 54 (1): 41–73. doi : 10.2307 / 1990131 . JSTOR   1990131 . Nachdruck in The Undecidable , p. 255ff. Kleene verfeinerte seine Definition von "allgemeiner Rekursion" und fuhr in seinem Kapitel "12. Algorithmische Theorien" fort, "These I" (S. 274) zu setzen; er würde diese These später wiederholen (in Kleene 1952: 300) und sie "Church's Thesis" (Kleene 1952: 317) nennen (dh die Church Thesis ).
• Kleene, Stephen C. (1991) [1952]. Einführung in die Metamathematik (10. Aufl.). Nordholland Verlag. Hervorragend zugängliche, lesbare Referenzquelle für mathematische "Grundlagen".
• Knuth, Donald E. (1973) [1968]. Die Kunst der Computerprogrammierung 2. Auflage, Band 1 / Grundlegende Algorithmen (2. Aufl.). Addison-Wesley Verlag. Die erste von Knuths berühmter Serie von drei Texten.
• Lewis, HR und Papadimitriou, CH Elemente der Berechnungstheorie , Prentice-Hall, Uppre Saddle River, NJ, 1998
• AA Markov (1954) Theorie der Algorithmen . [Übersetzt von Jacques J. Schorr-Kon und PST-Mitarbeitern] Impressum Moskau, Akademie der Wissenschaften der UdSSR, 1954 [dh Jerusalem, Israel Programm für wissenschaftliche Übersetzungen, 1961; erhältlich beim Office of Technical Services, US-Handelsministerium, Washington] Beschreibung 444 p. 28 cm. Hinzugefügt tp in russischer Übersetzung von Werken des Mathematischen Instituts, Akademie der Wissenschaften der UdSSR, v. 42. Originaltitel: Teoriya algerifmov. [QA248.M2943 Bibliothek des Dartmouth College. US-Handelsministerium, Office of Technical Services, Nummer OTS 60-51085.]
• Minsky, Marvin (1967). Berechnung: Endliche und unendliche Maschinen (Erstausgabe). Prentice-Hall, Englewood Cliffs, NJ. Minsky erweitert seine "... Idee eines Algorithmus - ein effektives Verfahren ..." in Kapitel 5.1 Berechenbarkeit, effektive Verfahren und Algorithmen. Unendliche Maschinen.
• Hartley Rogers, Jr. (1967), Theorie rekursiver Funktionen und effektiver Berechenbarkeit , MIT Press (1987), Cambridge, MA, ISBN   0-262-68052-1 (pbk.)
• Searle, John (2002). Bewusstsein und Sprache . Cambridge Großbritannien: Cambridge University Press. ISBN   0-521-59744-7 .
• Robert Soare (1995, erschienen in Proceedings of the 10th International Congress of Logic, Methodology and Philosophy of Science , 19.-25. August 1995, Florenz, Italien), Computability and Recursion ), im Internet unter ??.
• Michael Sipser , (2006), Einführung in die Theorie der Berechnung: Zweite Ausgabe , Thompson Course Technology div. von Thompson Learning, Inc. Boston, MA. ISBN   978-0-534-95097-2 .
• Ian Stewart , Algorithmus , Encyclopædia Britannica 2006.
• Stone, Harold S. Einführung in die Computerorganisation und Datenstrukturen (1972 ed.). McGraw-Hill, New York. Vgl. Insbesondere das erste Kapitel mit dem Titel: Algorithmen, Turingmaschinen und Programme . Seine prägnante informelle Definition: "... jede Folge von Anweisungen, die von einem Roboter befolgt werden können, wird als Algorithmus bezeichnet " (S. 4).
• Peter van Emde Boas (1990), "Maschinenmodelle und Simulationen", S. 3–66, erscheint in Jan van Leeuwen (1990), Handbuch der Theoretischen Informatik. Band A: Algorithmen & Komplexität , MIT Press / Elsevier, 1990, ISBN   0-444-88071-2 (Band A)