Ich beginne ein Buch über Computational Complexity und Turing Machines zu lesen. Hier ist Zitat:
Ein Algorithmus (dh eine Maschine) kann als Bitfolge dargestellt werden, sobald wir uns für eine kanonische Codierung entschieden haben.
Diese Behauptung ist eine einfache Tatsache, aber ich kann es nicht verstehen.
Zum Beispiel, wenn ich einen Algorithmus habe, der als Eingabe nimmt und berechnet oder:
int function (int x){
x = x + 1;
return x**2;
}
Wie kann dies mit dem Alphabet als Zeichenfolge dargestellt werden ?
algorithms
turing-machines
computability
computation-models
Kenenbek Arzymatov
quelle
quelle
Antworten:
Die naivste und einfachste Antwort auf Ihre Frage ist, dass der bereitgestellte Code (und der kompilierte Maschinencode) tatsächlich als syntaktische Zeichenfolgen von {0,1} * dargestellt werden. Da es sich bei den von Ihnen ausgeführten Programmen um Turing-Maschinen handelt, handelt es sich um eine lineare Liste von Operationen / Anweisungen. Es gibt keinen Grund, warum diese nicht als Bits / Bytes dargestellt werden können.
quelle
Sie haben bereits eine Darstellung dieser Funktion als Text. Konvertieren Sie jedes Zeichen mithilfe der ASCII-Codierung in einen Ein-Byte-Wert. Das Ergebnis ist dann eine Folge von Bytes, dh eine Folge von Bits, dh eine Zeichenkette über dem Alphabet . Das ist ein Beispiel für eine Codierung.{ 0 , 1 }∗
quelle
Ich kann nicht widerstehen ...
(Die obigen Punkte stehen für Einsen, die Leerzeichen für Nullen).
quelle
Ihr Computer speichert alles als Sequenzen von
0und1, einschließlich der Frage, die Sie eingegeben haben, um zu fragen, wie es funktioniert. Zum Beispiel wird jeder Buchstabe und jedes Symbol durch 8 Bit dargestellt (ich spreche davon, wie es früher war, heute sind es 16 Bit und es ist komplizierter). Sie können sie hier sehen . Nun, sie zeigen nicht die Bits, sondern die hexadezimalen und oktalen Codes. Wissen Sie, wie man eine Zahl in ihre digitale Darstellung umwandelt?quelle
Die grundlegende Hypothese hinter diesem Konzept ist die Church-Turing-These . Es ist möglicherweise schwer zu erkennen, dass ein Algorithmus als Bitfolge dargestellt werden kann, da der Begriff "Algorithmus" sehr informell verstanden werden kann. In der Church-Turing-These verwenden sie ein sehr genau definiertes Konzept, was ein Algorithmus ist (und selbst dann gab es einige Fragen zu Wörtern). Allerdings hat ihre Terminologie so viel Einfluss bekommen , dass es manchmal , dass diese Definitionen für Begriffe wie „Algorithmus“ argumentiert wird , sind so effektiv , dass wir sie einfach als akzeptieren die Definition.
Church-Turing gibt an, dass jeder Algorithmus als Berechnung auf einer Turing-Maschine implementiert werden kann. Da die Beschreibung einer Turing-Maschine eine endliche Menge von Werten ist, ist es trivial zu sehen, wie diese Beschreibung in eine Folge von Zahlen und dann in eine Folge von Nullen und Einsen abgebildet wird.
Wie in den anderen Antworten bereits erwähnt, ist es trivial, Ihren Beispielalgorithmus mithilfe von ASCII-Codierung oder anderen Codierungen darzustellen.
Ich denke, der Grund, warum Ihr Buch diese Aussage als Tatsache darstellt, liegt in der Tatsache begründet, dass viele einfach die Church-Turing-These als Grundlage für die Definition eines Algorithmus verwenden. Wenn Sie eine solche Definition verwenden, ist dies ebenso offensichtlich wie "5 ist eine Zahl", da Sie sie im Grunde genommen als solche definiert haben.
quelle
Diese Aussage basiert auf der Existenz universeller TMs . Dies sind im Grunde programmierbare TMs, die jedes andere TM mit höchstens Poly-Overhead simulieren können. Daher ist Ihr Programm einfach Teil der Eingabe, die als Nullen und Einsen codiert ist.
quelle
Nun, lassen Sie uns über Algorithmen sprechen, die für keine Art von Codierung als endliche Bitfolge dargestellt werden können.
Lassen Sie mich einen solchen Algorithmus für Sie eingeben ... Ah, aber wenn ich das tue, kann ich diesen Algorithmus mit der Kodierung meines eingegebenen Textes darstellen.
Wie wäre es, wenn Sie meinen Algorithmus mit 'analogen Mitteln' darstellen, etwa durch die Position einiger Münzen auf meinem Schreibtisch. Obwohl die Position dieser Münzen durch einige reelle Zahlen modelliert werden kann (die in einigen Codierungen möglicherweise nicht endgültig darstellbar sind), kann diese gesamte Beschreibung wiederum als Darstellung meines Algorithmus betrachtet und wieder zu einer Bitfolge codiert werden!
Ich hoffe, dass diese Beispiele deutlich machen, dass wir, wenn ein Algorithmus nicht durch eine endliche Bitfolge dargestellt werden kann, überhaupt keine Möglichkeit haben, diesen Algorithmus zu beschreiben!
Warum sollten wir also die Existenz von etwas in Betracht ziehen, von dem wir nicht sprechen können? Vielleicht interessant für die Philosophie, aber nicht für die Wissenschaft. Daher definieren wir den Begriff des Algorithmus so, dass er durch eine Bitfolge dargestellt werden kann, da wir dann zumindest wissen, dass wir über alle Algorithmen sprechen können.
Obwohl die oben gestellte Frage beantwortet wurde, ist die Verwirrung über das angegebene Beispiel meines Erachtens hauptsächlich auf die Tatsache zurückzuführen, dass eine Darstellung nur einen bestimmten Algorithmus eindeutig darstellen muss. Die Art der Darstellung muss nicht die tatsächlichen Berechnungen beinhalten, die vom Algorithmus aufgerufen werden! Dies ist sehr nützlich, da wir damit auch nicht berechenbare Algorithmen darstellen können!
quelle
Eine andere Möglichkeit, dies zu sehen, ist die Informationstheorie. Alle Kodierungen von sinnvollen / nützlichen Informationen / Fragen können in binäre 'Sequenzen' umgewandelt werden.
Ein großer Teil des Fachgebiets beschäftigt sich mit der Frage: "Wie kann man die geringste durchschnittliche Anzahl von Fragen stellen, um eine aussagekräftige Information zu vermitteln?" In der Praxis ist dies dasselbe wie "Was ist der optimale Ansatz, um die geringste Anzahl von Ja / Nein-Fragen zu stellen, um zu verstehen, was kommuniziert oder gesagt wurde?"
quelle