Ich habe versucht, jemandem zu erklären, dass C Turing-vollständig ist, und habe festgestellt, dass ich eigentlich nicht weiß, ob es tatsächlich technisch Turing-vollständig ist. (C wie in der abstrakten Semantik, nicht wie in einer tatsächlichen Implementierung.)
Die "offensichtliche" Antwort (ungefähr: Sie kann eine beliebige Menge an Speicher adressieren, so dass sie eine RAM-Maschine emulieren kann, so dass sie vollständig ist) ist nicht richtig, soweit ich das beurteilen kann, obwohl der C-Standard dies zulässt Damit size_t beliebig groß ist, muss es auf eine bestimmte Länge festgelegt werden, und unabhängig davon, auf welche Länge es festgelegt ist, ist es immer noch endlich. (Mit anderen Worten, obwohl Sie bei einer willkürlich angehaltenen Turing-Maschine eine Länge von size_t wählen könnten, damit sie "richtig" läuft, gibt es keine Möglichkeit, eine Länge von size_t zu wählen, damit alle angehaltenen Turing-Maschinen richtig laufen.)
Also: Ist C99 Turing-complete?
Antworten:
Ich bin mir nicht sicher, aber ich denke, die Antwort ist aus ziemlich subtilen Gründen nein. Ich habe vor ein paar Jahren nach Theoretischer Informatik gefragt und keine Antwort erhalten, die über das hinausgeht, was ich hier präsentieren werde.
In den meisten Programmiersprachen können Sie eine Turing-Maschine folgendermaßen simulieren:
Eine konkrete Implementierung, die auf einem Computer ausgeführt wird, verfügt nicht über genügend Speicher, wenn das Band zu lang wird. Eine ideale Implementierung kann jedoch das Turing-Maschinenprogramm zuverlässig ausführen. Dies kann mit Stift und Papier oder durch den Kauf eines Computers mit mehr Speicher und eines Compilers erfolgen, der auf eine Architektur mit mehr Bits pro Wort abzielt, und so weiter, falls das Programm jemals keinen Speicher mehr hat.
Dies funktioniert in C nicht, da es unmöglich ist, eine verknüpfte Liste zu haben, die für immer wachsen kann: Die Anzahl der Knoten ist immer begrenzt.
Um zu erklären, warum, muss ich zuerst erklären, was eine C-Implementierung ist. C ist eigentlich eine Familie von Programmiersprachen. Der ISO-C-Standard (genauer gesagt eine bestimmte Version dieses Standards) definiert (mit dem Grad an Formalität, den Englisch zulässt) die Syntax und Semantik einer Familie von Programmiersprachen. C hat viel undefiniertes und implementierungsdefiniertes Verhalten. Eine „Implementierung“ von C codiert das gesamte implementierungsdefinierte Verhalten (die Liste der zu codierenden Dinge befindet sich in Anhang J für C99). Jede Implementierung von C ist eine eigene Programmiersprache. Beachten Sie, dass die Bedeutung des Wortes „Implementierung“ etwas eigenartig ist: Was es wirklich bedeutet, ist eine Sprachvariante. Es kann mehrere verschiedene Compiler-Programme geben, die dieselbe Sprachvariante implementieren.
In einer gegebenen Implementierung von C hat ein Byte mögliche Werte. Alle Daten können als Array von Bytes dargestellt werden: Ein Typ hat höchstens mögliche Werte. Diese Anzahl variiert in verschiedenen Implementierungen von C, ist jedoch für eine bestimmte Implementierung von C eine Konstante. 2 CHAR_BIT × sizeof (t)2CHAR_BIT 2CHAR_BIT×sizeof(t)
t
Insbesondere können Zeiger höchstens Werte . Das heißt, es gibt eine endliche maximale Anzahl adressierbarer Objekte.2CHAR_BIT×sizeof(void*)
Die Werte von
CHAR_BIT
undsizeof(void*)
sind beobachtbar. Wenn Ihnen also der Speicher ausgeht, können Sie Ihr Programm nicht einfach mit größeren Werten für diese Parameter fortsetzen. Sie würden das Programm unter einer anderen Programmiersprache ausführen - einer anderen C-Implementierung.Wenn Programme in einer Sprache nur eine begrenzte Anzahl von Zuständen haben können, ist die Programmiersprache nicht ausdrucksvoller als endliche Automaten. Das Fragment von C, das auf adressierbaren Speicher beschränkt ist, lässt höchstens zu, wobei die Größe des abstrakten Syntaxbaums von ist Programm (das den Zustand des Kontrollflusses darstellt), daher kann dieses Programm von einem endlichen Automaten mit so vielen Zuständen simuliert werden. Wenn C aussagekräftiger ist, muss es durch die Verwendung anderer Merkmale erfolgen. nn×2CHAR_BIT×sizeof(void*) n
C legt keine maximale Rekursionstiefe fest. Eine Implementierung darf ein Maximum haben, aber es darf auch keines geben. Aber wie kommunizieren wir zwischen einem Funktionsaufruf und seinem übergeordneten Element? Argumente sind nicht gut, wenn sie adressierbar sind, da dies indirekt die Rekursionstiefe einschränken würde: Wenn Sie eine Funktion haben, haben
int f(int x) { … f(…) …}
alle Vorkommenx
auf aktiven Framesf
eine eigene Adresse, und daher ist die Anzahl der verschachtelten Aufrufe durch die Anzahl begrenzt von möglichen Adressen fürx
.Ein Programm kann einen nicht adressierbaren Speicher in Form von
register
Variablen verwenden. "Normale" Implementierungen können nur eine kleine, begrenzte Anzahl von Variablen haben, die keine Adresse haben. Theoretisch kann eine Implementierung jedoch eine unbegrenzte Menge anregister
Speicherplatz ermöglichen. In einer solchen Implementierung können Sie eine unbegrenzte Anzahl von rekursiven Aufrufen einer Funktion ausführen, sofern das Argument dies zulässtregister
. Da es sich bei den Argumentenregister
jedoch um Argumente handelt , können Sie keinen Zeiger auf sie erstellen. Daher müssen Sie deren Daten explizit kopieren: Sie können nur eine begrenzte Datenmenge übergeben, keine Datenstruktur beliebiger Größe, die aus Zeigern besteht.Mit unbegrenzter Rekursionstiefe und der Einschränkung, dass eine Funktion nur Daten von ihrem direkten Aufrufer (
register
Argumente) abrufen und Daten an ihren direkten Aufrufer (den Funktionsrückgabewert) zurückgeben kann, erhalten Sie die Macht deterministischer Pushdown-Automaten .Ich kann keinen Weg finden, weiter zu gehen.
(Natürlich könnten Sie das Programm veranlassen, den Bandinhalt extern zu speichern, und zwar über Dateieingabe- / ausgabefunktionen. Dann würden Sie jedoch nicht fragen, ob C vollständig ist, sondern ob C plus ein unendliches Speichersystem vollständig ist . , welche die Antwort ist ein langweilige „ja“ Sie könnten als definieren auch die Speicherung ein Turing Orakel zu sein - Aufruf
fopen("oracle", "r+")
,fwrite
der anfängliche Bandinhalt zu ihm undfread
. wieder der endgültigen Bandinhalt)quelle
Die Hinzufügung von C99
va_copy
zum variadischen Argument API kann uns eine Hintertür zur Turing-Vollständigkeit geben. Da es möglich ist, eine Liste variabler Argumente mehrmals in einer anderen Funktion als der ursprünglich empfangenen zu durchlaufen,va_args
kann ein Zeiger ohne Zeiger implementiert werden.Natürlich wird eine echte Implementierung der API mit variablen Argumenten wahrscheinlich irgendwo einen Zeiger haben, aber in unserer abstrakten Maschine kann sie stattdessen mit Magie implementiert werden.
Hier ist eine Demo, die einen 2-Stack-Pushdown-Automaten mit beliebigen Übergangsregeln implementiert:
Hinweis: Wenn
va_list
es sich um einen Array-Typ handelt, gibt es tatsächlich versteckte Zeigerparameter für die Funktionen. Es wäre also wahrscheinlich besser, die Typen allerva_list
Argumente auf zu ändernwrapped_stack
.quelle
va_list
Variablen zugewiesen werden mussstack
. Diese Variablen müssen eine Adresse haben&stack
, und wir können nur eine begrenzte Anzahl von diesen haben. Diese Anforderung könnte umgangen werden, indem jede lokale Variable deklariert wirdregister
, vielleicht?register
.int
man nicht eine Schranke haben müssen, es sei denn, jemand benutzt die Schranke odersizeof(int)
?int
einen Wert zwischen einigen endlichen GrenzenINT_MIN
und hatINT_MAX
. Und wenn der Wert einesint
überläuft, tritt dieses gebundene, undefinierte Verhalten auf. Andererseits erfordert der Standard absichtlich nicht, dass alle Objekte an einer bestimmten Adresse physisch im Speicher vorhanden sind, da dies Optimierungen wie das Speichern des Objekts in einem Register, das Speichern nur eines Teils des Objekts, das es anders als der Standard darstellt, ermöglicht Layout, oder es ganz weglassen, wenn es nicht benötigt wird.Nichtstandard-Arithmetik vielleicht?
Es scheint also, dass das Problem die endliche Größe von ist
sizeof(t)
. Ich denke jedoch, dass ich eine Arbeit um kenne.Soweit ich weiß, benötigt C keine Implementierung, um die Standard-Ganzzahlen für seinen Ganzzahltyp zu verwenden. Daher könnten wir ein nicht standardmäßiges Rechenmodell verwenden . Dann würden wir eine
sizeof(t)
nicht standardmäßige Zahl festlegen , und jetzt werden wir sie niemals in einer endlichen Anzahl von Schritten erreichen. Daher wird die Länge des Turingmaschinenbandes immer kleiner als das "Maximum" sein, da das Maximum buchstäblich nicht zu erreichen ist.sizeof(t)
ist einfach keine Zahl im eigentlichen Sinne des Wortes.Dies ist natürlich eine Technik: der Satz von Tennenbaum . Es heißt, dass das einzige Modell der Peano-Arithmetik das Standardmodell ist, was offensichtlich nicht ausreichen würde. Nach meinem Kenntnisstand erfordert C jedoch keine Implementierungen, um Datentypen zu verwenden, die die Peano-Axiome erfüllen, und erfordert auch keine berechenbare Implementierung, sodass dies kein Problem sein sollte.
Was soll passieren, wenn Sie versuchen, eine nicht standardmäßige Ganzzahl auszugeben? Nun, Sie können jede nicht standardmäßige Ganzzahl mit einer nicht standardmäßigen Zeichenfolge darstellen, also nur Ziffern von der Vorderseite dieser Zeichenfolge streamen.
quelle
sizeof(t)
ist selbst ein Wert vom Typsize_t
, also eine natürliche ganze Zahl zwischen 0 undSIZE_MAX
.IMO, eine starke Einschränkung ist, dass der adressierbare Raum (über die Zeigergröße) endlich ist und dies nicht wiederherstellbar ist.
Man könnte befürworten, dass der Speicher "auf die Festplatte ausgelagert" werden kann, aber irgendwann überschreitet die Adressinformation selbst die adressierbare Größe.
quelle
In der Praxis sind diese Einschränkungen für die Vollständigkeit von Turing irrelevant. Die eigentliche Anforderung besteht darin, das Band beliebig lang und nicht unendlich lang zu machen. Das würde ein anderes Problem zum Stillstand bringen (wie "berechnet" das Universum das Band?)
Es ist so falsch, als würde man sagen "Python ist nicht vollständig, weil man keine unendlich große Liste erstellen kann".
[Bearbeiten: Danke an Mr. Whitledge für die Erläuterung der Bearbeitung.]
quelle
size_t
endlich. Das Problem ist, dass Sie keine Grenze festlegen können, die fürsize_t
die gesamte Berechnung gültig ist: Bei jeder Grenze kann ein Programm überlaufen. Die C-Sprache gibt jedoch an, dass es eine Grenze gibt fürsize_t
: Bei einer bestimmten Implementierung kann sie nur aufsizeof(size_t)
Bytes anwachsen . Auch nett sein . Zu sagen, dass Leute, die Sie kritisieren, „nicht alleine denken können“, ist unhöflich.Wechselmedien ermöglichen es uns, das unbegrenzte Speicherproblem zu umgehen. Vielleicht denken die Leute, dass dies ein Missbrauch ist, aber ich denke, es ist in Ordnung und im Wesentlichen sowieso unvermeidlich.
Beheben Sie alle Implementierungen einer universellen Turing-Maschine. Für das Band verwenden wir Wechselmedien. Wenn der Kopf am Ende oder am Anfang der aktuellen CD abläuft, fordert das Gerät den Benutzer auf, die nächste oder die vorherige CD einzulegen. Wir können entweder einen speziellen Marker verwenden, um das linke Ende des simulierten Bandes zu kennzeichnen, oder ein Band, das in beide Richtungen unbegrenzt ist.
Der entscheidende Punkt hierbei ist, dass alles, was das C-Programm tun muss, endlich ist. Der Computer benötigt nur genügend Speicher, um den Automaten zu simulieren, und
size_t
muss nur groß genug sein, um auf diese (eigentlich ziemlich kleine) Speichermenge und auf die Datenträger zuzugreifen, die eine festgelegte endliche Größe haben können. Da der Benutzer nur aufgefordert wird, die nächste oder vorherige CD einzulegen, benötigen wir keine unbegrenzt großen Ganzzahlen, um "Bitte CD-Nummer 123456 einlegen ..." zu sagen.Ich nehme an, der hauptsächliche Einwand ist wahrscheinlich die Einbeziehung des Benutzers, aber das scheint bei jeder Implementierung unvermeidlich zu sein, da es anscheinend keinen anderen Weg gibt, unbegrenzten Speicher zu implementieren.
quelle
Entscheide dich
size_t
unendlich groß zu seinSie könnten wählen
size_t
, unendlich groß zu sein. Natürlich ist es unmöglich, eine solche Implementierung zu realisieren. Aber das ist keine Überraschung angesichts der Endlichkeit der Welt, in der wir leben.Praktische Auswirkungen
Aber selbst wenn es möglich wäre, eine solche Implementierung zu realisieren, gäbe es praktische Probleme. Betrachten Sie die folgende C-Anweisung:
Dies gibt eine Dezimaldarstellung vonO(2size_t)
SIZE_MAX
zu Standard aus. VermutlichSIZE_MAX
ist . Also wenn unendlich groß ist, ist auch unendlich groß. Die einzige Möglichkeit, eine Dezimalform einer unendlich großen Zahl zu drucken, besteht darin, einen unendlichen Strom von Dezimalstellen zu erzeugen. Dies bedeutet, dass in einigen Fällen nicht beendet wird.size_t
SIZE_MAX
printf
Glücklicherweise konnte ich für unsere theoretischen Zwecke keine Anforderung in der Spezifikation finden, die die Garantie
printf
für alle Eingaben erlischt. Soweit mir bekannt ist, verstoßen wir hier nicht gegen die C-Spezifikation.Zur rechnerischen Vollständigkeit
Es bleibt noch zu beweisen, dass unsere theoretische Umsetzung Turing Complete ist . Wir können dies durch die Implementierung einer "single-taped Turing Machine" zeigen.
Die meisten von uns haben wahrscheinlich eine Turing-Maschine als Schulprojekt implementiert. Ich werde nicht auf die Details einer bestimmten Implementierung eingehen, aber hier ist eine häufig verwendete Strategie:
Lassen Sie uns nun sehen, was erforderlich ist, um eine solche Implementierung zu realisieren:
MAX_INT
unendlich zu sein. (Alternativ könnten wir andere Objekte verwenden, um Zustände und Symbole darzustellen.)malloc
, aber es gibt noch ein bisschen mehr, das wir berücksichtigen müssen:malloc
fehlschlagen, wenn z. B. der verfügbare Speicher erschöpft ist. Unsere Implementierung ist also nur dann wirklich universell, wenn siemalloc
niemals fehlschlägt.malloc
zum Fehlschlagen. Ohne den C-Standard zu verletzen, garantiert unsere Implementierung, dass diesmalloc
niemals fehlschlägt.Die obige Liste ist also notwendig, um eine Turing-Maschine in unserer hypothetischen C-Implementierung zu implementieren. Diese Funktionen müssen beendet werden. Alles andere darf jedoch nicht gekündigt werden (es sei denn, der Standard schreibt dies vor). Dies schließt Arithmetik, E / A usw. ein.
quelle
printf("%zu\n",SIZE_MAX);
eine solche Implementierung bedeuten?sizeof(size_t)
(oderCHAR_BITS
). Sie können den neuen Status nicht wieder herstellen, Sie müssen neu starten, aber die Ausführung des Programms kann jetzt anders sein, da sich diese Konstanten unterscheidenDas Hauptargument war hier, dass die Größe von size_t endlich ist, obwohl sie unendlich groß sein kann.
Es gibt eine Problemumgehung, obwohl ich nicht sicher bin, ob dies mit ISO C übereinstimmt.
Angenommen, Sie haben eine Maschine mit unbegrenztem Speicher. Sie sind also nicht an die Zeigergröße gebunden. Sie haben noch Ihren size_t-Typ. Wenn Sie mich fragen, was sizeof (size_t) ist, lautet die Antwort einfach sizeof (size_t). Wenn Sie zum Beispiel fragen, ob es größer als 100 ist, lautet die Antwort ja. Wenn Sie fragen, was sizeof (size_t) / 2 ist, wie Sie sich vorstellen können, lautet die Antwort noch sizeof (size_t). Wenn Sie es ausdrucken möchten, können wir eine Ausgabe vereinbaren. Der Unterschied zwischen diesen beiden kann NaN usw. sein.
Die Zusammenfassung ist, dass die Lockerung der Bedingung für size_t have finite size keine bereits existierenden Programme kaputt macht.
PS: Das Zuweisen von Speichergröße von (size_t) ist weiterhin möglich. Sie benötigen nur eine abzählbare Größe. Nehmen wir also an, Sie haben alle Möglichkeiten (oder einen ähnlichen Trick).
quelle
sizeof
muss ein zurückgebensize_t
. Sie müssen also einen bestimmten Wert auswählen.Ja ist es.
1. Zitierte Antwort
Als Reaktion auf die hohe Anzahl von Abstimmungen meiner (und anderer) richtigen Antworten - im Vergleich zu der alarmierend hohen Zustimmung zu falschen Antworten - suchte ich nach einer weniger theoretisch fundierten alternativen Erklärung. Ich habe diesen gefunden . Ich hoffe, es werden einige der hier häufig vorkommenden Irrtümer behandelt, damit ein wenig mehr Einsicht gezeigt wird. Wesentlicher Teil des Arguments:
Kurz gesagt, weil es für jede berechenbare Funktion eine Lösung in der C-Sprache gibt (aufgrund der unbegrenzten Obergrenzen), hat jedes berechenbare Problem ein C-Programm, daher ist C Turing-vollständig.
2. Meine ursprüngliche Antwort
Es gibt weit verbreitete Verwechslungen zwischen mathematischen Konzepten in der theoretischen Informatik (wie Turing-Vollständigkeit) und ihrer praktischen Anwendung, dh Techniken in der praktischen Informatik. Die Turing-Vollständigkeit ist keine Eigenschaft von physisch vorhandenen Maschinen oder eines in der Raumzeit begrenzten Modells. Es ist nur ein abstraktes Objekt, das Eigenschaften mathematischer Theorien beschreibt.
C99 ist Turing-complete, unabhängig von implementierungsbedingten Einschränkungen, wie praktisch jede andere gängige Programmiersprache, da es einen funktional vollständigen Satz logischer Verknüpfungen ausdrücken kann und im Prinzip auf eine unbegrenzte Menge an Speicher zugreifen kann. Man hat darauf hingewiesen, dass C den wahlfreien Speicherzugriff explizit einschränkt, um ihn jedoch nicht zu umgehen, da diese Einschränkungen zusätzlich im C-Standard angegeben sind, während die Turing-Vollständigkeit ohne sie bereits gegeben ist:
Hier ist eine sehr grundlegende Sache über logische Systeme, die für einen nicht konstruktiven Beweis ausreichen sollten . Stellen Sie sich einen Kalkül mit einigen Axiomschemata und -regeln vor, sodass die Menge der logischen Folgen X ist. Wenn Sie nun einige Regeln oder Axiome hinzufügen, wächst die Menge der logischen Konsequenzen, dh es muss sich um eine Obermenge von X handeln ist die Modallogik S4 richtig in S5 enthalten. Wenn Sie eine Subspezifikation haben, die Turing-complete ist, aber zusätzlich einige Einschränkungen hinzufügen, verhindern diese keine der Konsequenzen in X, dh, es muss eine Möglichkeit geben, alle Einschränkungen zu umgehen. Wenn Sie eine Sprache wünschen, die nicht Turing-vollständig ist, muss der Kalkül reduziert und nicht erweitert werden. Erweiterungen, die behaupten, dass etwas nicht möglich wäre, aber tatsächlich ist, fügen nur Inkonsistenz hinzu. Diese Inkonsistenzen in der C-Norm dürfen jedoch keine praktischen Konsequenzen haben, so wie die Turing-Vollständigkeit nichts mit der praktischen Anwendung zu tun hat.
Das Simulieren von willkürlichen Zahlen basierend auf der Rekursionstiefe (dh dies ; mit der Möglichkeit, mehrere Zahlen über Scheduling / Pseudo-Threads zu unterstützen; es gibt keine theoretische Grenze für die Rekursionstiefe in C ) oder das Verwenden des Dateispeichers zum Simulieren von unbegrenztem Programmspeicher ( Idee ) wahrscheinlich nur zwei von unendlichen Möglichkeiten, die Turing-Vollständigkeit von C99 konstruktiv nachzuweisen. Man sollte sich daran erinnern, dass für die Berechenbarkeit die Komplexität von Zeit und Raum keine Rolle spielt. Insbesondere ist die Annahme einer begrenzten Umgebung zur Verfälschung der Turing-Vollständigkeit nur eine Zirkelschlussfolgerung, da diese Beschränkung alle Probleme ausschließt, die die vorausgesetzte Komplexität überschreiten.
( ANMERKUNG : Ich habe diese Antwort nur geschrieben, um zu verhindern, dass Menschen aufgrund eines anwendungsorientierten eingeschränkten Denkens angehalten werden, um mathematische Intuition zu erlangen. Es ist sehr schade, dass die meisten Lernenden die falsch akzeptierte Antwort lesen, da sie auf der Grundlage von upvotes gelesen wird Grundlegende Denkfehler, damit mehr Menschen solche falschen Überzeugungen verbreiten. Wenn Sie diese Antwort ablehnen, sind Sie nur ein Teil des Problems.)
quelle
CHAR_BITS
.