Sind Boolesche Funktionen Turing abgeschlossen?

9

Eine Boolesche Funktion ist eine Funktion . $f:\{0,1\}^n\rightarrow\{0,1\}$

Die boolesche Basis ist bekanntermaßen Turing-vollständig, da jede Sequenz umgedreht oder unverändert gelassen werden kann. Gleiches gilt für Gates. $(\vee,\wedge)$ $s\in\{0,1\}$ $\mathrm{XOR}$

In diesem Sinne können wir mit einer anfänglichen Maschinenkonfiguration so dass und es mit aufeinanderfolgenden Werten : $\textbf{b}=(b_1,\ldots,b_n)$ $b_i\in\{0,1\}$ $\mathrm{XOR}$ $\textbf{v}_i$

$\textbf{b}\oplus\textbf{v}_1\oplus\textbf{v}_2\oplus\textbf{v}_3\ldots$

Jeder Zustand würde eine Permutation eines Elements in . Dieser Prozess ahmt effektiv eine Turing-Maschine nach und setzt voraus, dass es einen Generator für die Werte . $\textbf{v}_i$ $\textbf{b}$ $\textbf{v}_i$

Können wir also sagen, dass Boolesche Funktionen Turing abgeschlossen sind?

turing-machines turing-completeness boolean-algebra user13675
quelle

1

Wie könnte diese Maschinerie in einer Endlosschleife stecken bleiben?

Guildenstern

Ich denke, die Sache ist, dass der Boolesche Schaltungsformalismus zwar isomorph zum Turing-Formalismus ist, Ihnen aber nicht sagt, wie man ein solches Programm erstellt oder generiert ... Sie müssen nur die Werte "kennen" ...

v_{i}

$\textbf{v}_i$

user13675

8

Informell ist eine (Programmier-) Sprache Turing vollständig, wenn jede berechenbare Funktion eine Darstellung hat. Eine allgemeine berechenbare Funktion akzeptiert eine Eingabe beliebiger Größe. Boolesche Funktionen akzeptieren dagegen eine Eingabe fester Größe. Daher Booleschen Funktionen auch nicht qualifizieren als potenziell Turing-vollständig.

Der relevante Begriff der Vollständigkeit ist hier eine vollständige Grundlage von Konnektiven. Eine Reihe von Konnektiven ( -ary-Funktionen für Boolesche Werte für beliebiges ) ist vollständig, wenn jede Boolesche Funktion für (für beliebiges ) mithilfe der Konnektiva dargestellt werden kann. Die folgenden Sätze sind vollständig: die de Morgan-Basis und die Basis . Im Gegensatz dazu ist nicht vollständig: Es kann nur lineare Funktionen ausdrücken. $k$ $k$ $x_1,\ldots,x_n$ $n \geq 1$ $\{\lnot,\lor,\land\}$ $\{\lnot,\Rightarrow\}$ $\{\lnot,\oplus\}$

Yuval Filmus
quelle

Wäre ihr Gegenstück, die Booleschen Schaltkreise, vollständig? Ich vermute, dass dies der Fall ist, seit Cook (in seinem Beweis der NP-Vollständigkeit von 3SAT) gezeigt hat, wie Turing-Maschinen und Boolesche Schaltkreise gleichwertig sind.

user13675

@ user13675 Nein, es ist genau das gleiche Problem. Jede anhaltende Turing-Maschine mit kann für jede Eingangsgröße in eine äquivalente Boolesche Schaltung oder Formel umgewandelt werden, für jede Größe benötigen Sie jedoch eine andere.

Yuval Filmus

5

Genau genommen, wie YF geantwortet hat, können endliche Schaltkreise nicht vollständig sein.

Erwähnenswert ist jedoch ein Hinweis auf diese Frage (und vielleicht auch das, wonach Sie suchen), ein eng verwandtes Konzept, das theoretisch weit verbreitet ist und bei dem Schaltkreise verwendet werden, um Funktionen auf eine Weise zu berechnen, die stärker ist als Turing complete.

$n$ $C_n$

vzn
quelle

Sind Boolesche Funktionen Turing abgeschlossen?

Antworten: