Ist C tatsächlich vollständig?

39

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?

TLW
quelle
3
Was ist die "abstrakte Semantik" von C? Sind sie irgendwo definiert?
Yuval Filmus
4
@YuvalFilmus - Siehe z. B. hier , dh C wie im Standard definiert, im Gegensatz zu z. B. "so macht es gcc".
TLW
1
Es gibt die "Technik", dass moderne Computer wie der TM keinen unendlichen Speicher haben und dennoch als "Universalcomputer" gelten. und beachten Sie, dass Programmiersprachen in ihrer "Semantik" nicht wirklich einen endlichen Speicher voraussetzen, außer dass alle ihre Implementierungen natürlich im Speicher begrenzt sind. siehe zB arbeitet unser pc als turingmaschine . sowieso sind im wesentlichen alle "mainstream" programmiersprachen komplett.
VZN
2
C (wie Turing-Maschinen) ist nicht auf die Verwendung des internen Computerspeichers für seine Berechnungen beschränkt, daher ist dies wirklich kein gültiges Argument gegen die Turing-Vollständigkeit von C.
reinierpost,
@reinierpost - das ist so, als ob man sagt, ein Fernschreiber sei nützlich. Das heißt, dass "C + ein externes TM-Äquivalent" Turing-vollständig ist, nicht dass C Turing-vollständig ist.
TLW

Antworten:

34

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:

  • Simulieren des endlichen Automaten mit einem Programm, das eine endliche Speichermenge verwendet;
  • Simulieren des Bandes mit zwei verknüpften Listen von Ganzzahlen, die den Inhalt des Bandes vor und nach der aktuellen Position darstellen. Wenn Sie den Zeiger bewegen, wird der Kopf einer der Listen auf die andere Liste übertragen.

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_BITt2CHAR_BIT×sizeof(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_BITund sizeof(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 Vorkommen xauf aktiven Frames feine eigene Adresse, und daher ist die Anzahl der verschachtelten Aufrufe durch die Anzahl begrenzt von möglichen Adressen für x.

Ein Programm kann einen nicht adressierbaren Speicher in Form von registerVariablen 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 an registerSpeicherplatz ermöglichen. In einer solchen Implementierung können Sie eine unbegrenzte Anzahl von rekursiven Aufrufen einer Funktion ausführen, sofern das Argument dies zulässt register. Da es sich bei den Argumenten registerjedoch 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 ( registerArgumente) 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+"), fwriteder anfängliche Bandinhalt zu ihm und fread. wieder der endgültigen Bandinhalt)

Gilles 'SO - hör auf böse zu sein'
quelle
Es ist nicht sofort klar, warum der Satz von Adressen endlich sein sollte. Ich schrieb einige Gedanken in einer Antwort auf die Frage, die Sie verlinken: cstheory.stackexchange.com/a/37036/43393
Alexey B.
4
Sorry, aber nach der gleichen Logik gibt es überhaupt keine Turing-vollständigen Programmiersprachen. Jede Sprache hat eine explizite oder implizite Beschränkung des Adressraums. Wenn Sie eine Maschine mit unbegrenztem Speicher erstellen, haben Zeiger mit wahlfreiem Zugriff natürlich auch eine unbegrenzte Länge. Wenn eine solche Maschine angezeigt wird, muss sie daher einen Befehlssatz für den sequentiellen Speicherzugriff sowie eine API für Hochsprachen anbieten.
25.
14
@IMil Das ist nicht wahr. Einige Programmiersprachen haben keine Einschränkung des Adressraums, auch nicht implizit. Um ein offensichtliches Beispiel zu nennen: Eine universelle Turing-Maschine, bei der der Anfangszustand des Bandes das Programm bildet, ist eine Programmiersprache, die vollständig Turing ist. Viele in der Praxis verwendete Programmiersprachen haben die gleiche Eigenschaft, zum Beispiel Lisp und SML. Eine Sprache muss kein Konzept eines „Direktzugriffszeigers“ haben. (Forts.)
Gilles 'SO - hör auf böse zu sein'
11
@IMil (Forts.) Implementierungen wirken sich normalerweise auf die Leistung aus, aber wir wissen, dass eine auf einem bestimmten Computer ausgeführte Implementierung nicht vollständig ist, da sie durch die Größe des Computerspeichers begrenzt ist. Dies bedeutet jedoch, dass die Implementierung nicht die gesamte Sprache implementiert, sondern nur eine Teilmenge (von Programmen, die in N Byte Speicher ausgeführt werden). Sie können das Programm auf einem Computer ausführen. Wenn der Arbeitsspeicher knapp wird, verschieben Sie es auf einen größeren Computer usw. für immer oder so lange, bis es anhält. Das wäre eine gute Möglichkeit, die gesamte Sprache zu implementieren.
Gilles 'SO - hör auf böse zu sein'
6

Die Hinzufügung von C99 va_copyzum 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_argskann 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:

#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

Hinweis: Wenn va_listes sich um einen Array-Typ handelt, gibt es tatsächlich versteckte Zeigerparameter für die Funktionen. Es wäre also wahrscheinlich besser, die Typen aller va_listArgumente auf zu ändern wrapped_stack.

Feersum
quelle
Das könnte funktionieren. Ein mögliches Problem besteht darin, dass eine unbegrenzte Anzahl von automatischen va_listVariablen zugewiesen werden muss stack. 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 wird register, vielleicht?
Chi
@chi AIUI Eine Variable muss keine Adresse haben, es sei denn, jemand versucht, die Adresse zu übernehmen. Es ist auch illegal, das Argument unmittelbar vor der Ellipse zu deklarieren register.
Feersum
Nach der gleichen Logik sollte intman nicht eine Schranke haben müssen, es sei denn, jemand benutzt die Schranke oder sizeof(int)?
Chi
@chi Überhaupt nicht. Der Standard definiert als Teil der abstrakten Semantik, dass an inteinen Wert zwischen einigen endlichen Grenzen INT_MINund hat INT_MAX. Und wenn der Wert eines intü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.
Feersum
4

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.

PyRulez
quelle
Wie würde eine Implementierung aussehen?
Reinierpost
@reinierpost Ich vermute, es würde Daten darstellen, die ein abzählbares, nicht standardmäßiges PA-Modell verwenden. Es würde arithmetische Operationen unter Verwendung eines PA-Grades berechnen . Ich denke, ein solches Modell sollte eine gültige C-Implementierung liefern.
PyRulez
Entschuldigung, das funktioniert nicht. sizeof(t)ist selbst ein Wert vom Typ size_t, also eine natürliche ganze Zahl zwischen 0 und SIZE_MAX.
Gilles 'SO - hör auf böse zu sein'
@Gilles SIZE_MAX wäre dann auch eine nicht standardmäßige Natur.
PyRulez
Dies ist ein interessanter Ansatz. Beachten Sie, dass Sie zB auch intptr_t / uintptr_t / ptrdiff_t / intmax_t / uintmax_t benötigen, um nicht dem Standard zu entsprechen. In C ++ würde dies den Vorwärtsfortschrittsgarantien zuwiderlaufen ... ich bin mir nicht sicher, ob C.
TLW
0

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.

Yves Daoust
quelle
Ist das nicht der Hauptpunkt der akzeptierten Antwort? Ich denke nicht, dass es den Antworten auf diese Frage von 2016 etwas Neues hinzufügt.
chi
@chi: nein, in der akzeptierten Antwort wird nicht erwähnt, dass auf externen Speicher gewechselt wird, was möglicherweise eine Problemumgehung darstellt.
Yves Daoust
-1

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.]

der Arzt
quelle
7
Ich glaube nicht, dass dies die Frage beantwortet. Die Frage hat diese Antwort bereits vorweggenommen und erklärt, warum sie nicht gültig ist: "Obwohl der C-Standard es zulässt, dass size_t beliebig groß ist, muss sie auf eine bestimmte Länge festgelegt werden, und unabhängig davon, auf welche Länge sie festgelegt ist, ist sie immer noch endlich ". Haben Sie eine Antwort auf dieses Argument? Ich denke nicht, dass wir die Frage als beantwortet betrachten können, es sei denn, die Antwort erklärt, warum dieses Argument falsch (oder richtig) ist.
DW
5
Zu jedem Zeitpunkt ist ein Wert vom Typ size_tendlich. Das Problem ist, dass Sie keine Grenze festlegen können, die für size_tdie gesamte Berechnung gültig ist: Bei jeder Grenze kann ein Programm überlaufen. Die C-Sprache gibt jedoch an, dass es eine Grenze gibt für size_t: Bei einer bestimmten Implementierung kann sie nur auf sizeof(size_t)Bytes anwachsen . Auch nett sein . Zu sagen, dass Leute, die Sie kritisieren, „nicht alleine denken können“, ist unhöflich.
Gilles 'SO - hör auf böse zu sein'
1
Das ist die richtige Antwort. Eine Drehmaschine benötigt kein Endlosband, sondern ein "beliebig langes" Band. Das heißt, Sie können davon ausgehen, dass das Band so lang ist, wie es sein muss, um die Berechnung abzuschließen. Sie können auch davon ausgehen, dass Ihr Computer über so viel Speicher verfügt, wie er benötigt. Ein unendliches Band ist absolut nicht erforderlich, da eine Berechnung, die in endlicher Zeit anhält, unmöglich eine unendliche Menge an Band verwenden kann.
Jeffrey L Whitledge
Diese Antwort zeigt, dass Sie für jede TM eine C-Implementierung mit einer ausreichenden Zeigerlänge schreiben können, um sie zu simulieren. Es ist jedoch nicht möglich, eine C-Implementierung zu schreiben , die ein beliebiges TM simulieren kann . Die Spezifikation verbietet also, dass eine bestimmte Implementierung T-vollständig ist. Es ist selbst auch nicht T-vollständig, da die Zeigerlänge festgelegt ist.
1
Dies ist eine weitere richtige Antwort, die aufgrund der Unfähigkeit der meisten Menschen in dieser Gemeinde kaum sichtbar ist. In der Zwischenzeit ist die akzeptierte Antwort falsch und der Kommentarbereich wird von Moderatoren geschützt, die kritische Kommentare löschen. Tschüss, cs.stackexchange.
Xamid
-1

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_tmuss 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.

David Richerby
quelle
3
Ich würde argumentieren, dass dies kein Beweis für die Vollständigkeit von Turing sein kann, es sei denn, die C-Definition erfordert einen solchen unbegrenzten externen Speicher. (Für ISO 9899 ist es natürlich nicht erforderlich, dass dies für das Real-World-Engineering geschrieben wurde.) Was mich betrifft, ist, dass wir, wenn wir dies akzeptieren, nach einer ähnlichen Überlegung behaupten könnten, dass DFAs vollständig sind, da sie verwendet werden könnten einen Kopf über ein Band (den externen Speicher) zu fahren.
Chi
@chi Ich verstehe nicht, wie das DFA-Argument folgt. Der springende Punkt bei einem DFA ist, dass er nur Lesezugriff auf den Speicher hat. Wenn Sie es erlauben, "einen Kopf über ein Band zu fahren", ist das nicht genau eine Turing-Maschine?
David Richerby
2
In der Tat bin ich hier ein bisschen pingelig. Der Punkt ist: Warum ist es in Ordnung, C ein "Band" hinzuzufügen, C einen DFA simulieren zu lassen und anhand dieser Tatsache zu behaupten, dass C Turing abgeschlossen ist, wenn wir DFAs nicht auf die gleiche Weise bearbeiten können? Wenn C keine Möglichkeit hat, unbegrenzten Speicher selbst zu implementieren, sollte Turing nicht als abgeschlossen betrachtet werden. (Ich würde es immer noch als "moralisch" bezeichnen. Zumindest weil die Grenzen so groß sind, dass sie in der Praxis in den meisten Fällen keine Rolle spielen.) Ich denke, um die Angelegenheit endgültig zu regeln, müsste man eine strenge formale Spezifikation von C (der ISO-Standard reicht nicht aus)
Chi
1
@chi Ist in Ordnung, da C Datei-E / A-Routinen enthält. DFAs nicht.
David Richerby
1
C gibt nicht vollständig an, was diese Routinen tun - der größte Teil ihrer Semantik ist durch die Implementierung definiert. Eine AC-Implementierung ist nicht erforderlich, um den Dateiinhalt zu speichern. Ich denke, sie kann sich sozusagen so verhalten, als wäre jede Datei "/ dev / null". Es ist auch nicht erforderlich, eine unbegrenzte Datenmenge zu speichern. Ich würde sagen, dass Ihr Argument richtig ist, wenn Sie überlegen, was die meisten C-Implementierungen tun, und dieses Verhalten auf eine ideale Maschine verallgemeinern. Wenn wir uns nur streng auf die C-Definition verlassen und die Praxis vergessen, glaube ich nicht, dass sie gilt.
Chi
-2

Entscheide dich size_tunendlich groß zu sein

Sie 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:

printf("%zu\n",SIZE_MAX);

Dies gibt eine Dezimaldarstellung von SIZE_MAXzu Standard aus. Vermutlich SIZE_MAXist . 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.O(2size_t)size_tSIZE_MAXprintf

Glücklicherweise konnte ich für unsere theoretischen Zwecke keine Anforderung in der Spezifikation finden, die die Garantie printffü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:

  • Die Anzahl von Zuständen, die Anzahl von Symbolen und die Zustandsübergangstabelle sind für jede gegebene Maschine festgelegt. So können wir Zustände und Symbole als Zahlen und die Zustandsübergangstabelle als zweidimensionales Array darstellen.
  • Das Band kann als verknüpfte Liste dargestellt werden. Wir können entweder eine einzelne doppelt verknüpfte Liste oder zwei einfach verknüpfte Listen (eine für jede Richtung von der aktuellen Position aus) verwenden.

Lassen Sie uns nun sehen, was erforderlich ist, um eine solche Implementierung zu realisieren:

  • Die Fähigkeit, eine feste, aber beliebig große Menge von Zahlen darzustellen. Um eine beliebige Zahl darzustellen, wählen wir auch, MAX_INTunendlich zu sein. (Alternativ könnten wir andere Objekte verwenden, um Zustände und Symbole darzustellen.)
  • Die Möglichkeit, eine beliebig große verknüpfte Liste für unser Band zu erstellen. Auch hier gibt es keine begrenzte Größe. Dies bedeutet, dass wir diese Liste nicht im Voraus erstellen können, da wir ewig nur damit verbringen würden, unser Band zu erstellen. Diese Liste kann jedoch inkrementell erstellt werden, wenn die dynamische Speicherzuweisung verwendet wird. Wir können verwenden malloc, aber es gibt noch ein bisschen mehr, das wir berücksichtigen müssen:
    • Die C-Spezifikation kann mallocfehlschlagen, wenn z. B. der verfügbare Speicher erschöpft ist. Unsere Implementierung ist also nur dann wirklich universell, wenn sie mallocniemals fehlschlägt.
    • Wenn unsere Implementierung jedoch auf einem Computer mit unbegrenztem Speicher ausgeführt wird, besteht kein Grund malloczum Fehlschlagen. Ohne den C-Standard zu verletzen, garantiert unsere Implementierung, dass dies mallocniemals fehlschlägt.
  • Die Möglichkeit, Zeiger zu dereferenzieren, Array-Elemente nachzuschlagen und auf die Mitglieder eines verknüpften Listenknotens zuzugreifen.

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.

Nathan Davis
quelle
6
Was würde printf("%zu\n",SIZE_MAX);eine solche Implementierung bedeuten?
Ruslan
1
@ Ruslan, eine solche Implementierung ist unmöglich, genauso wie es unmöglich ist, eine Turing-Maschine zu implementieren. Aber wenn eine solche Implementierung möglich wäre, würde sie meiner Meinung nach eine Dezimaldarstellung einer unendlich großen Zahl ausgeben - vermutlich einen unendlichen Strom von Dezimalstellen.
Nathan Davis
2
@ NathanDavis Es ist möglich, eine Turing-Maschine zu implementieren. Der Trick ist, dass Sie kein unendliches Band erstellen müssen - Sie erstellen den verwendeten Teil des Bands nur nach Bedarf inkrementell.
Gilles 'SO- hör auf böse zu sein'
2
@Gilles: In diesem endlichen Universum, in dem wir leben, ist es unmöglich, eine Turing-Maschine zu implementieren.
gnasher729
1
@ NathanDavis Aber wenn Sie das tun, dann haben Sie geändert sizeof(size_t)(oder CHAR_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 unterscheiden
Gilles 'SO - hör auf, böse zu sein'
-2

Das 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).

Eugene
quelle
1
Msgstr "Der Unterschied zwischen diesen beiden kann NaN sein". Nein, es kann nicht sein. Es gibt kein NaN vom ganzzahligen Typ in C.
TLW
Nach dem Standard sizeofmuss ein zurückgeben size_t. Sie müssen also einen bestimmten Wert auswählen.
Draconis
-4

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:

[...] Sein Argument lautet wie folgt: Angenommen, man hat ein bestimmtes Abschlussprogramm geschrieben, das während seiner Ausführung möglicherweise bis zu einer beliebigen Menge an Speicherplatz benötigt. Ohne dieses Programm zu ändern, ist es von vornherein möglich, ein Stück Computerhardware und seinen C-Compiler zu implementieren, die genügend Speicherplatz für diese Berechnung bieten. Dies erfordert möglicherweise eine Verbreiterung der Breite von char (über CHAR_BITS) und / oder von Zeigern (über size_t), das Programm müsste jedoch nicht geändert werden. Da dies möglich ist, ist C in der Tat Turing-Complete zum Beenden von Programmen.

Der schwierige Teil dieses Arguments ist, dass es nur funktioniert, wenn Sie erwägen, Programme zu beenden. Programmende haben die nette Eigenschaft, dass sie eine statische Obergrenze für ihren Speicherbedarf haben, die man experimentell ermitteln kann, indem man das Programm mit zunehmender Speichergröße über die gewünschte Eingabe laufen lässt, bis es „passt“.

Der Grund, warum ich in meinem Gedankengang irregeführt wurde, war, dass ich die umfassendere Klasse von "nützlichen" nicht beendenden Programmen in Betracht zog [...]

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.)

xamid
quelle
4
Ich folge deinem letzten Absatz nicht. Sie behaupten, dass das Hinzufügen von Einschränkungen die Ausdruckskraft erhöht, aber das stimmt eindeutig nicht. Einschränkungen können nur die Ausdruckskraft verringern. Wenn Sie zum Beispiel C nehmen und die Einschränkung hinzufügen, dass kein Programm auf mehr als 640 KB Speicher (jeglicher Art) zugreifen darf, haben Sie daraus einen ausgefallenen endlichen Automaten gemacht, der eindeutig nicht vollständig ist.
David Richerby
3
Wenn Sie über eine feste Speichermenge verfügen, können Sie nichts simulieren, das mehr Ressourcen erfordert als Sie. Es gibt nur endlich viele Konfigurationen, in denen sich Ihr Speicher möglicherweise befindet, was bedeutet, dass Sie möglicherweise nur endlich viele Dinge tun können.
David Richerby
2
Ich verstehe nicht, warum Sie von "physisch vorhandenen Maschinen" sprechen. Es ist zu beachten, dass die Turing-Vollständigkeit eine Eigenschaft eines mathematischen Rechenmodells ist, nicht physikalischer Systeme. Ich würde zustimmen, dass kein physikalisches System, das ein endliches Objekt ist, der Kraft von Turing-Maschinen nahe kommen kann, aber das ist irrelevant. Wir können weiterhin jede Programmiersprache verwenden, die mathematische Definition ihrer Semantik berücksichtigen und prüfen, ob dieses mathematische Objekt vollständig ist. Conways Lebensspiel ist Turing mächtig, auch wenn es keine mögliche physische Umsetzung gibt.
Chi
2
@xamid Wenn Sie Bedenken hinsichtlich der Moderationsrichtlinien dieser Website haben, wenden Sie sich an Computer Science Meta . Bis dahin sei bitte nett . Mündlicher Missbrauch anderer wird nicht toleriert. (Ich habe alle Kommentare entfernt, die sich nicht auf das vorliegende Thema beziehen.)
Raphael
2
Sie sagen, das Ändern der Breite eines Zeigers würde das Programm nicht ändern, aber Programme können die Breite eines Zeigers lesen und mit diesem Wert tun, was sie wollen. Gleiches gilt für CHAR_BITS.
Draconis