Verbindung zwischen NAND-Gattern und Turing-Vollständigkeit

Ich weiß, dass NAND-Gatter verwendet werden können, um Schaltkreise zu erstellen, die jede Wahrheitstabelle implementieren, und moderne Computer bestehen aus NAND-Gattern. Was ist der theoretische Zusammenhang zwischen NAND-Gattern und Turing-Vollständigkeit? Es scheint mir, dass NAND-Gatterschaltungen näher an endlichen Automaten liegen als Turing-Maschinen. Meine Intuition ist, dass ich Flip-Flops und damit Register und Speicher aus NAND-Gattern bauen kann und unbegrenzter Speicher eine entscheidende Eigenschaft von Turing-Gesamtsystemen ist. Ich suche eine theoretischere oder mathematischere Erklärung oder Hinweise darauf, was ich lesen soll.

turing-machines turing-completeness digital-circuits bsm
quelle

"Moderne Computer bestehen aus NAND-Gattern" Ich bin mir ziemlich sicher, dass das falsch ist. Typische Zellbibliotheken für digitale Designs enthalten Zehner, wenn nicht Hunderte von Gattern, und sie unterscheiden sich in der Funktion (suchen Sie nach AOI-Gattern) sowie im Fan-In und Fan-Out.

Programmierer

Sie haben Recht, ich habe theoretisch gemeint, dass die gesamte digitale Logik aus NANDS aufgebaut werden kann, die als funktional vollständig betrachtet werden

bsm

Antworten:

Es gibt in der Tat wenig Verbindung. Lassen Sie mich zum besseren Verständnis den Zusammenhang zwischen Programmen und Schaltkreisen erläutern .

Ein Programm (oder Algorithmus oder Maschine ) ist ein Mechanismus zum Berechnen einer Funktion. Nehmen wir zur Sicherheit an, dass die Eingabe eine binäre Zeichenfolge und die Ausgabe eine boolesche Ausgabe . Die Größe der Eingabe ist möglicherweise unbegrenzt. Ein Beispiel ist ein Programm, das bestimmt, ob die Eingabe die binäre Codierung einer Primzahl ist. $x$ $b$

$x$ $n$ $n$

$P$ $P_n$ $P$ $n$ $P_0,P_1,P_2,\ldots$ $n$ $P_n$ $P_n$ $n$

Nicht jede Folge von Schaltkreisen ist einheitlich. In der Tat kann eine Folge von Schaltkreisen jede Funktion von Strings bis zu Booleschen, berechenbaren oder nicht berechenbaren, berechnen! In der Komplexitätstheorie interessieren uns jedoch solche uneinheitlichen Modelle, bei denen die Schaltkreise eingeschränkt sind. Zum Beispiel besagt die Frage P = NP, dass NP-vollständige Probleme nicht durch polynomielle Zeitalgorithmen gelöst werden können. Dies impliziert, dass NP-vollständige Probleme nicht durch Polynomgrößen-Einheitsschaltungen gelöst werden können. Es wird außerdem vermutet, dass NP-vollständige Probleme nicht durch Polynomgrößenschaltungen ohne die Forderung nach Gleichförmigkeit gelöst werden können .

Turing-Complete-Berechnungsmodelle sind Modelle, die alle berechenbaren Funktionen (und nicht mehr) realisieren. Im Gegensatz dazu ermöglichen vollständige Gatesysteme (wie AND, OR, NOT oder NAND) die Berechnung beliebiger endlicher Funktionen unter Verwendung von Schaltungen, die aus diesen Gates bestehen. Solche vollständigen Systeme können unter Verwendung von (uneingeschränkten) Folgen von Schaltkreisen vollständig beliebige Funktionen berechnen.

Yuval Filmus
quelle

Können Sie erklären, "eine Folge von Schaltkreisen kann jede Funktion von Strings bis zu Booleschen, berechenbaren oder nicht berechenbaren, berechnen"? Liegt ihre Fähigkeit, nicht berechenbare Funktionen (aus Sicht der Turing-Vollständigkeit) zu berechnen, in der Beschränkung der Eingabegröße?

bsm

n

$n$

n

$n$

Können Sie das erläutern, @YuvalFilmus? Es scheint seltsam, dass eine nicht berechenbare Funktion wie die Kolmogorov-Komplexität plötzlich mithilfe von Schaltkreisen "berechenbar" wäre.

Cort Ammon - Reinstate Monica

f

$f$

n

$n$

Sie sind in der Tat richtig. Eine kombinatorische Logik entspricht einem endlichen Automaten. NAND-Gatter machen sie nicht mächtiger; Sie werden verwendet, weil es einfach billiger ist, eine digitale Logikschaltung mit nur einer Art von Gatter zu bauen, als sie mit allen verschiedenen Gattern zu bauen. Tatsächlich kann ein NAND-Gatter nur aus einem UND-Gatter und einem NICHT-Gatter aufgebaut werden. Flip-Flops runden die Schaltung ab. Hier ist ein praktischer Schlüssel:

Kombinationsschaltungen ~ Endliche Automaten ~ Reguläre Sprachen ~ Reguläre Ausdrücke ~ Aussagenkalkül ~ Gerade Programme

$\mu$

Wenn Sie mehr erfahren möchten, gibt es ein sehr gutes Buch, das Sie kostenlos als PDF herunterladen können und das alles erklärt:

https://cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf

user628544
quelle