Maximale Rechenleistung einer C-Implementierung

28

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_BITSpeicherbits 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 registerObjekte nicht begrenzt, deterministische Pushdown-Automaten codieren.

Ist das richtig? Können Sie eine leistungsfähigere C-Implementierung finden? Existiert eine Turing-complete C-Implementierung?

Gilles 'SO - hör auf böse zu sein'
quelle
4
@ Dave: Wie Gilles erklärte, scheint es, dass Sie unbegrenztes Gedächtnis haben können, aber keine Möglichkeit, es direkt anzusprechen.
Jukka Suomela
2
Ihrer Erklärung nach kann eine C-Implementierung nur so programmiert werden, dass sie Sprachen akzeptiert, die von deterministischen Pushdown-Automaten akzeptiert werden, die schwächer sind als selbst kontextfreie Sprachen. Diese Beobachtung ist meiner Meinung nach jedoch von geringem Interesse, da es sich um eine falsche Anwendung von Asymptotika handelt.
Warren Schudy
3
Ein Punkt, den Sie beachten sollten, ist, dass es viele Möglichkeiten gibt, "implementierungsdefiniertes Verhalten" (oder "undefiniertes Verhalten") auszulösen. Im Allgemeinen kann eine Implementierung z. B. Bibliotheksfunktionen bereitstellen, die Funktionen bereitstellen, die im C-Standard nicht definiert sind. Alle diese bieten "Schlupflöcher", durch die Sie beispielsweise auf eine Turing-Komplettmaschine zugreifen können. Oder sogar etwas viel Stärkeres, wie ein Orakel, das das Halteproblem löst. Ein dummes Beispiel: Das implementierungsdefinierte Verhalten von vorzeichenbehafteten Ganzzahlüberläufen oder Ganzzahl-Zeiger-Konvertierungen kann Ihnen den Zugriff auf ein solches Orakel ermöglichen.
Jukka Suomela
7
Übrigens könnte es eine gute Idee sein, das Tag "leisure" (oder was auch immer wir für lustige Rätsel verwenden) hinzuzufügen, damit die Leute dies nicht zu ernst nehmen. Es ist natürlich die "falsche Frage", aber trotzdem fand ich es amüsant und faszinierend. :)
Jukka Suomela
2
@Jukka: Gute Idee. Beispiel: Überlauf durch X = X / 3 auf das Band schreiben und in Richtung X% 3 bewegen, Unterlauf = das Signal auslösen, das dem Symbol auf dem Band entspricht. Es fühlt sich ein bisschen wie ein Missbrauch an, aber es ist definitiv im Geiste meiner Frage. Könnten Sie es als Antwort schreiben? (@others: Nicht, dass ich andere so clevere Vorschläge entmutigen möchte!)
Gilles 'SO - hör auf, böse zu sein'

Antworten:

8

Wie in der Frage erwähnt, erfordert Standard C, dass ein Wert UCHAR_MAX vorhanden ist, sodass jede Variable vom Typ unsigned charimmer 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 ist unsigned char*, und dass es eine Konstante gibt, sizeof(unsigned char*)so dass jeder Zeiger dieses Typs durch eine Folge von sizeof(unsigned char *)Werten des Typs identifizierbar ist unsigned 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.UCHAR_MAXsizeof(unsigned char)101010

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 nur UCHAR_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.

Superkatze
quelle
Was würde sizeof (char) mit einer solchen Maschine zurückgeben?
TLW
1
@TLW: Wie bei jeder anderen Maschine: 1. Die Makros CHAR_BITS und CHAR_MAX wären jedoch etwas problematischer. Der Standard würde das Konzept von Typen, die keine Grenzen haben, nicht zulassen.
Supercat
Hoppla, ich meinte CHAR_BITS, wie Sie sagten, sorry.
TLW
7

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.

Jared
quelle
Aber Turingmaschinen mit einem Band, das unendlich in nur eine Richtung läuft, sind genauso leistungsfähig wie Turingmaschinen mit einem Band, das unendlich in zwei Richtungen läuft. Außerdem können mehrere Threads von einem Scheduler simuliert werden. Auf jeden Fall benötigen wir nicht einmal eine Threading-Bibliothek.
Xamid
3

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

  • Definieren Sie eine Struktur, die als doppelt verknüpfte Liste für die Banddarstellung verwendet werden kann
    typdef struct {
      cell_t * pred; // Zelle links
      cell_t * succ; // Zelle rechts
      int val; // Zellwert
    } cell_t 

Das headwird ein Zeiger auf eine cell_tStruktur sein

  • Definieren Sie eine Struktur, in der der aktuelle Status und ein Flag gespeichert werden können
    typedef struct {
      int state;
      int flag;
    } info_t 
  • Definieren Sie dann eine Einzelschleifenfunktion, die ein Universal TM simuliert, wenn sich der Kopf zwischen den Grenzen der doppelt verknüpften Liste befindet. Wenn der Kopf eine Grenze berührt, setze das Flag der info_t-Struktur (HIT_LEFT, HIT_RIGHT) und kehre zurück:
void simulate_UTM (cell_t * head, info_t * info) {
  while (wahr) {
    head-> val = UTM_nextsymbol [info-> state, head-> val]; // Schreibsymbol
    info-> state = UTM_nextstate [info-> state, head-> val]; // nächster Zustand
    if (info-> state == HALT_STATE) {// print if akzeptiert und beendet das Programm
       putchar ((info-> state == ACCEPT_STATE)? '1': '0');
       Ausfahrt (0);
    }
    int move = UTM_nextmove [info-> state, head-> val];
    if (move == MOVE_LEFT) {
      kopf = kopf-> pred; // geh nach links
      if (head == NULL) {info-> flag = HIT_LEFT; Rückkehr; }
    } else {
      head = head-> succ; // nach rechts bewegen
      if (head == NULL) {info-> flag = HIT_RIGHT; Rückkehr; }
    }
  } // immer noch in der Grenze ... mach weiter
}
  • Definieren Sie dann eine rekursive Funktion, die zuerst die UTM-Simulationsroutine aufruft und sich dann selbst rekursiv aufruft, wenn das Band erweitert werden muss. Wenn das Band oben erweitert werden muss (HIT_RIGHT), gibt es keine Probleme. Wenn es unten verschoben werden muss (HIT_LEFT), verschieben Sie einfach die Werte der Zellen mithilfe der doppelt verknüpften Liste nach oben:
Leerenstapler (Zelle_t * oben, Zelle_t * unten, Zelle_t * Kopf, Info_t * Info) {
  simulate_UTM (head, info);
  cell_t newcell; // die neue Zelle
  newcell.pred = top; // Aktualisiere die doppelt verknüpfte Liste mit der neuen Zelle
  newcell.succ = NULL;
  top-> succ = & newcell;
  newcell.val = EMPTY_SYMBOL;

  wechseln (info-> hit) {
    case HIT_RIGHT:
      Stapler (& newcell, bottom, newcell, info);
      brechen;
    case HIT_BOTTOM:
      cell_t * tmp = newcell;
      while (tmp-> pred! = NULL) {// Werte hochschalten
        tmp-> val = tmp-> pred-> val;
        tmp = tmp-> pred;
      }
      tmp-> val = EMPTY_SYMBOL;
      Stapler (& neue Zelle, unten, unten, Info);
      brechen;
  }
}
  • Das ursprüngliche Band kann mit einer einfachen rekursiven Funktion gefüllt werden, die die doppelt verknüpfte Liste erstellt und die stackerFunktion dann aufruft, wenn sie das letzte Symbol des Eingabebands liest (mit readchar).
void init_tape (cell_t * top, cell_t * bottom, info_t * info) {
  cell_t newcell;
  int c = readchar ();
  if (c == END_OF_INPUT) -Stapler (& top, bottom, bottom, info); // keine Symbole mehr, starte
  newcell.pred = top;
  if (top! = NULL) top.succ = & newcell; sonst unten = & newcell;
  init_tape (& newcell, bottom, info);
}

BEARBEITEN: Nach einigem Nachdenken gibt es ein Problem mit den Zeigern ...

Wenn jeder Aufruf der rekursiven Funktion stackereinen 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.

Marzio De Biasi
quelle
3
stackernewcellstacker2n/sns=sizeof(cell_t)
@ Gilles: Du hast recht (siehe meine Bearbeitung); Wenn Sie die Rekursionstiefe begrenzen, erhalten Sie einen endlichen Automaten
Marzio De Biasi
@MarzioDeBiasi Nein, er irrt sich, da er auf eine konkrete Implementierung verweist, die der Standard nicht voraussetzt. Tatsächlich gibt es in C keine theoretische Grenze für die Rekursionstiefe . Die Wahl einer Implementierung mit begrenztem Stapel sagt nichts über die theoretischen Grenzen der Sprache aus. Die Turing-Vollständigkeit ist jedoch eine theoretische Grenze.
Xamid
0

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, aber b^knur für eine endliche Anzahl von ks 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?

Bitmaske
quelle
5
Was ist ein Stapelzeiger? (Beachten Sie, dass das Wort „Stapel“ im C-Standard nicht vorkommt.) Bei meiner Frage geht es um C als Klasse formaler Sprachen, nicht um C-Implementierungen auf einem Computer (die offensichtlich Finite-State-Maschinen sind). Wenn Sie auf die Aufrufliste zugreifen möchten, müssen Sie dies auf eine Weise tun, die von der Sprache bereitgestellt wird. Zum Beispiel indem man die Adresse der Funktionsargumente nimmt - aber jede gegebene Implementierung hat nur eine endliche Anzahl von Adressen, was dann die Tiefe der Rekursion begrenzt.
Gilles 'SO - hör auf böse zu sein'
Ich habe meine Antwort geändert, um die Verwendung eines Stapelzeigers auszuschließen.
Bitmaske
1
Ich verstehe nicht, wohin Sie mit Ihrer überarbeiteten Antwort gehen (abgesehen von der Änderung der Formulierung von berechenbaren Funktionen zu erkannten Sprachen). Da Funktionen auch eine Adresse haben, benötigen Sie eine Implementierung, die groß genug ist, um eine bestimmte Zustandsmaschine zu implementieren. Die Frage ist, ob und wie eine C-Implementierung mehr leisten kann (beispielsweise eine universelle Turing-Maschine), ohne sich auf ein nicht definiertes Verhalten zu verlassen.
Gilles 'SO- hör auf böse zu sein'
0

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:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

{anbncn}

Zumindest denke ich, dass dies funktioniert. Es kann jedoch sein, dass ich einen fundamentalen Fehler mache.

Eine feste Version:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}
Ben Standeven
quelle
Naja, kein grundsätzlicher Fehler, it = *itsollte aber durch ersetzt werden it = * (void **) it, da es sonst *itvom Typ ist void.
Ben Standeven
Es würde mich sehr überraschen, wenn ein
solches
Oh, das wird nicht funktionieren, da das erste 'b' dazu führt, dass read_a () fehlschlägt und somit eine Ablehnung auslöst.
Ben Standeven
Es ist jedoch legitim, den Aufrufstapel auf diese Weise zu durchlaufen, da der C-Standard sagt: "Für ein Objekt [dh eines mit automatischem Speicher], das keinen Array-Typ mit variabler Länge hat, verlängert sich seine Lebensdauer vom Eintritt in den Block mit Die Ausführung des aktuellen Blocks wird unterbrochen, aber nicht beendet. Wenn der Block rekursiv eingegeben wird, wird eine neue Instanz des Objekts erstellt wird jedes Mal erstellt. " Jeder Aufruf von read_triple würde also einen neuen Zeiger erzeugen, der in der Rekursion verwendet werden kann.
Ben Standeven
2
2CHAR_BITsizeof(char*)
0

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

Wie in der Frage angemerkt, erfordert Standard C, dass es einen Wert gibt, UCHAR_MAXso dass jede Variable des Typs char ohne Vorzeichen immer einen Wert zwischen 0 und UCHAR_MAXeinschließlich enthält. Es ist ferner erforderlich, dass jedes dynamisch zugewiesene Objekt durch eine Folge von Bytes dargestellt wird, die über einen Zeiger des Typs char * ohne Vorzeichen identifizierbar ist, und dass es eine Konstante gibt, sizeof(unsigned char*)so dass jeder Zeiger dieses Typs durch eine Folge von sizeof(unsigned char *)Werten des Typs ohne Vorzeichen identifizierbar ist verkohlen.

unsigned char*N{0,1}sizeof(unsigned char*){0,1}sizeof(unsigned char)Nsizeof(unsigned char*)Nω

An dieser Stelle sollte überprüft werden, ob der C-Standard dies tatsächlich zulässt.

sizeofZ

Alexey B.
quelle
1
Viele Operationen an Integraltypen haben ein Ergebnis, das "um eins mehr als der im Ergebnistyp darstellbare Maximalwert reduziert" ist. Wie würde das funktionieren, wenn dieses Maximum eine unendliche Ordnungszahl wäre?
Gilles 'SO - hör auf böse zu sein'
@ Gilles Dies ist ein interessanter Punkt. Es ist in der Tat nicht klar, wie die Semantik lautet 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.
Alexey B.
1
uintptr_tmü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, also size_tunendlich. 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 dieser UINT_MAX+1überlaufen muss.
Gilles 'SO- hör auf böse zu sein'
Auch ein guter Punkt. In der Tat erhalten wir eine Reihe von Typen (Zeiger und size_t), die ℕ, ℤ oder eine darauf basierende Konstruktion sein sollten (für size_t wäre es etwa ℕ ℕ {ω}). Wenn nun für einige dieser Typen der Standard ein Makro erfordert, das den Maximalwert definiert (PTR_MAX oder so), werden die Dinge haarig. Bisher konnte ich jedoch nur die Anforderung von MIN / MAX-Makros für Nicht-Zeigertypen finanzieren.
Alexey B.
Eine andere Möglichkeit zur Untersuchung besteht darin, beide size_tZeigertypen 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.
Alexey B.