Wie viel Rechenleistung kann eine C-Implementierung haben, wenn wir uns an das Buch halten (oder an eine andere Version der Sprachspezifikation, wenn Sie dies vorziehen)?
Beachten Sie, dass „C-Implementierung“ eine technische Bedeutung hat: Es handelt sich um eine bestimmte Instanz der C-Programmiersprachenspezifikation, in der das implementierungsdefinierte Verhalten dokumentiert ist. Die AC-Implementierung muss nicht auf einem tatsächlichen Computer ausgeführt werden können. Es muss die gesamte Sprache implementieren, einschließlich aller Objekte mit einer Bit-String-Darstellung und Typen mit einer implementierungsdefinierten Größe.
Im Sinne dieser Frage gibt es keinen externen Speicher. Die einzige Eingabe / Ausgabe, die Sie ausführen können, ist getchar
(um die Programmeingabe zu lesen) und putchar
(um die Programmausgabe zu schreiben). Auch jedes Programm, das undefiniertes Verhalten aufruft, ist ungültig: Für ein gültiges Programm muss das Verhalten durch die C-Spezifikation sowie die Beschreibung des implementierungsdefinierten Verhaltens in Anhang J (für C99) definiert werden. Beachten Sie, dass das Aufrufen von Bibliotheksfunktionen, die im Standard nicht erwähnt werden, undefiniertes Verhalten ist.
Meine anfängliche Reaktion war, dass eine C-Implementierung nichts anderes als ein endlicher Automat ist, da die Größe des adressierbaren Speichers begrenzt ist (Sie können nicht mehr als sizeof(char*) * CHAR_BIT
Speicherbits adressieren, da unterschiedliche Speicheradressen beim Speichern unterschiedliche Bitmuster aufweisen müssen in einem Bytezeiger).
Ich denke jedoch, eine Implementierung kann mehr als das. Soweit ich das beurteilen kann, gibt der Standard der Rekursionstiefe keine Grenzen. Damit Sie beliebig viele rekursive Funktionsaufrufe durchführen können, müssen bis auf eine begrenzte Anzahl von Aufrufen nur nicht adressierbare ( register
) Argumente verwendet werden. Somit kann eine C-Implementierung, die eine willkürliche Rekursion ermöglicht und die Anzahl der register
Objekte nicht begrenzt, deterministische Pushdown-Automaten codieren.
Ist das richtig? Können Sie eine leistungsfähigere C-Implementierung finden? Existiert eine Turing-complete C-Implementierung?
quelle
Antworten:
Wie in der Frage erwähnt, erfordert Standard C, dass ein Wert UCHAR_MAX vorhanden ist, sodass jede Variable vom TypUCHAR_MAXsizeof(unsigned char∗) 101010
unsigned char
immer einen Wert zwischen 0 und UCHAR_MAX einschließlich enthält. Es ist weiterhin erforderlich, dass jedes dynamisch zugewiesene Objekt durch eine Folge von Bytes dargestellt wird, die über einen Zeiger des Typs identifizierbar istunsigned char*
, und dass es eine Konstante gibt,sizeof(unsigned char*)
so dass jeder Zeiger dieses Typs durch eine Folge vonsizeof(unsigned char *)
Werten des Typs identifizierbar istunsigned char
. Die Anzahl der Objekte, die gleichzeitig dynamisch zugeordnet werden können, ist somit starr auf . Nichts würde einen theoretischen Compiler davon abhalten, die Werte dieser Konstanten so zuzuweisen, dass mehr als 10 10 10 Objekte unterstützt werden, aber theoretisch bedeutet die Existenz einer beliebigen, auch noch so großen Grenze, dass etwas nicht unendlich ist.Ein Programm könnte eine unbegrenzte Menge an Informationen auf dem Stapel speichern, falls für nichts, was auf dem Stapel zugeordnet ist, jemals eine Adresse vergeben wurde . man könnte also ein C-Programm haben, das in der Lage ist, einige Dinge zu tun, die von keinem endlichen Automaten irgendeiner Größe ausgeführt werden können. Obwohl der Zugriff auf Stapelvariablen (oder vielleicht auch nur, weil er wesentlich eingeschränkter ist als der Zugriff auf dynamisch zugewiesene Variablen, verwandelt er C von einem endlichen Automaten in einen Push-Down-Automaten.
Es gibt jedoch noch ein weiteres mögliches Problem: Wenn ein Programm die zugrunde liegenden Sequenzen fester Länge von Zeichenwerten untersucht, die zwei Zeigern auf verschiedene Objekte zugeordnet sind, müssen diese Sequenzen eindeutig sein. Weil es nurUCHAR_MAXsizeof(unsigned char∗) Mögliche Folgen von Zeichenwerten: Jedes Programm, das eine Reihe von Zeigern auf andere Objekte erstellt hat, die darüber hinausgehen, könnte dem C-Standard nicht entsprechen, wenn der Code jemals die mit diesen Zeigern verknüpfte Folge von Zeichen untersucht . In einigen Fällen könnte ein Compiler jedoch feststellen, dass kein Code jemals die mit einem Zeiger verknüpfte Zeichenfolge untersuchen würde. Wenn jedes "Zeichen" tatsächlich in der Lage wäre, eine endliche ganze Zahl zu speichern, und der Speicher der Maschine eine unzählige Folge von ganzen Zahlen wäre (bei einer Turing-Maschine mit unbegrenztem Band könnte man eine solche Maschine emulieren, obwohl sie sehr langsam wäre) es wäre in der Tat möglich, C zu einer Turing-vollständigen Sprache zu machen.
quelle
Mit der (optionalen) Threading-Bibliothek von C11 ist es möglich, eine vollständige Turing-Implementierung bei unbegrenzter Rekursionstiefe durchzuführen.
Wenn Sie einen neuen Thread erstellen, erhalten Sie einen zweiten Stapel. Zwei Stapel reichen aus, um die Vollständigkeit zu gewährleisten. Ein Stapel steht für die linke Seite des Kopfes, der andere für die rechte Seite.
quelle
Ich denke, es ist Turing komplett : Mit diesem Trick können wir ein Programm schreiben, das eine UTM simuliert (ich habe den Code schnell von Hand geschrieben, daher gibt es wahrscheinlich einige Syntaxfehler ... aber ich hoffe, es gibt keine (Haupt-) Fehler in der Logik :-)
Das
head
wird ein Zeiger auf einecell_t
Struktur seinstacker
Funktion dann aufruft, wenn sie das letzte Symbol des Eingabebands liest (mit readchar).BEARBEITEN: Nach einigem Nachdenken gibt es ein Problem mit den Zeigern ...
Wenn jeder Aufruf der rekursiven Funktion
stacker
einen gültigen Zeiger auf eine lokal im Aufrufer definierte Variable enthalten kann, ist alles in Ordnung . Andernfalls kann mein Algorithmus keine gültige doppelt verknüpfte Liste für die unbegrenzte Rekursion verwalten.quelle
stacker
newcell
stacker
sizeof(cell_t)
Solange Sie eine unbegrenzte Call-Stack-Größe haben, können Sie Ihr Band auf dem Call-Stack verschlüsseln und durch Zurückspulen des Stack-Zeigers wahlfrei darauf zugreifen, ohne von den Funktionsaufrufen zurückzukehren.BEARBEITEN : Wenn Sie nur den RAM verwenden können, der endlich ist, funktioniert diese Konstruktion nicht mehr, siehe unten.
Es ist jedoch höchst fraglich, warum Ihr Stack unendlich sein kann, der eigentliche RAM jedoch nicht.
Eigentlich würde ich sagen, dass Sie nicht einmal alle regulären Sprachen erkennen können, da die Anzahl der Zustände begrenzt ist (wenn Sie den Stapelrücklauf-Trick nicht mitzählen, um den unendlichen Stapel auszunutzen).Ich würde sogar spekulieren, dass die Anzahl der Sprachen, die Sie erkennen können, endlich ist (auch wenn die Sprachen selbst unendlich sein können, z. B.a*
in Ordnung sind, aberb^k
nur für eine endliche Anzahl vonk
s funktionieren ).BEARBEITEN : Dies ist nicht wahr, da Sie den aktuellen Status in zusätzliche Funktionen codieren können, sodass Sie ALLE regulären Sprachen wirklich erkennen können .
Sie können höchstwahrscheinlich alle Typ-2-Sprachen aus dem gleichen Grund erhalten, aber ich bin nicht sicher, ob Sie es schaffen, sowohl den Status als auch die Stapelkonstante in den Aufrufstapel zu setzen. Im Allgemeinen können Sie den Stempel jedoch effektiv vergessen, da Sie die Größe des Automaten immer so skalieren können, dass Ihr Alphabet die Kapazität des Stempels übersteigt. Wenn Sie also ein TM nur mit einem Stapel simulieren könnten, wäre Typ 2 gleich Typ 0, oder?
quelle
Ich habe einmal darüber nachgedacht und beschlossen, eine nicht kontextfreie Sprache mit der erwarteten Semantik zu implementieren. Der Schlüsselteil der Implementierung ist die folgende Funktion:
Zumindest denke ich, dass dies funktioniert. Es kann jedoch sein, dass ich einen fundamentalen Fehler mache.
Eine feste Version:
quelle
it = *it
sollte aber durch ersetzt werdenit = * (void **) it
, da es sonst*it
vom Typ istvoid
.In Anlehnung an die Antwort von @ supercat:
Die Behauptungen der Unvollständigkeit von C scheinen sich darauf zu konzentrieren, dass bestimmte Objekte bestimmte Adressen haben sollten, und die Menge der Adressen wird als endlich angenommen. Wie @supercat schreibt
unsigned char*
sizeof(unsigned char*)
sizeof(unsigned char*)
An dieser Stelle sollte überprüft werden, ob der C-Standard dies tatsächlich zulässt.
sizeof
quelle
uintptr_t p = (uintptr_t)sizeof(void*)
(\ omega in etwas zu setzen, das vorzeichenlose ganze Zahlen enthält). Ich weiß nicht. Wir könnten mit der Definition des Ergebnisses als 0 (oder einer anderen Zahl) davonkommen.uintptr_t
müsste auch unendlich sein. Allerdings ist dieser Typ optional - aber wenn Sie eine unendliche Anzahl unterschiedlicher Zeigerwerte haben,sizeof(void*)
muss er auch unendlich sein, alsosize_t
unendlich. Mein Einwand gegen das Reduktionsmodul ist jedoch nicht so offensichtlich - es kommt nur dann ins Spiel, wenn es einen Überlauf gibt, aber wenn Sie unendliche Typen zulassen, werden diese möglicherweise nie überlaufen. Aber auf der packenden Seite hat jeder Typ einen minimalen und einen maximalen Wert, was, soweit ich das beurteilen kann, impliziert, dass dieserUINT_MAX+1
überlaufen muss.size_t
Zeigertypen als be ℕ {ω} zu definieren. Damit ist das Min / Max-Problem beseitigt. Das Problem mit der Überlaufsemantik bleibt weiterhin bestehen. Was die Semantik sein soll,uint x = (uint)ω
ist mir nicht klar. Auch hier könnten wir zufällig 0 nehmen, aber es sieht ein bisschen hässlich aus.