Kombinierte Logikschaltungen und Berechnungstheorie

8

Ich versuche, kombinatorische Logikschaltungen (Computer, die nur auf logischen Gattern basieren) mit allem zu verknüpfen, was ich kürzlich in Theory of Computation gelernt habe.

Ich habe mich gefragt, ob kombinatorische Logikschaltungen Berechnungen auf die gleiche Weise wie Finite-State-Maschinen implementieren können. Sie scheinen radikal anders zu sein:

Finite-State-Maschinen haben jedoch einen genau definierten Speicher in Form der Zustände, in denen sie sich befinden können. Kombinatorische Logikschaltungen verfügen jedoch nicht über einen genau definierten Speicher, um Algorithmen zu implementieren, die Speicher benötigen, verwenden sie einige seltsame Methode der seriellen Verbindung (siehe, wie des vorherigen Addierers mit des aktuellen Addierers im Bild unten verbunden ist). C i nC.ÖutC.ichn

So radikal unterschiedlich sie auch erscheinen mögen, beide scheinen Berechnungen durchzuführen. Zum Beispiel können beide einen Algorithmus für die binäre Addition (und sogar die binäre Multiplikation) implementieren, wie unterschiedlich diese Implementierungen auch sein mögen:

FSM:
Geben Sie hier die Bildbeschreibung ein

Combinational Logic Circuit (C steht wie in und für Carry): C o u tC.ichnC.Öut
Geben Sie hier die Bildbeschreibung ein

Ich denke sogar (obwohl immer noch sehr unsicher), dass wir jedes FSM in eine entsprechende kombinatorische Logikschaltung umwandeln können.

Also frage ich mich:

Können kombinatorische Logikschaltungen auch als augenblickliches Berechnungsmodell betrachtet werden? Können wir alle Konzepte, die wir in der Berechenbarkeitstheorie und der Computerkomplexitätstheorie lernen, wie Raumkomplexität und Berechenbarkeit, darauf anwenden?

Einerseits scheinen sie nicht als Berechnungsmodell zu passen, da sie keine elementaren Operationen (wie Lesen / Schreiben eines Bandes, Funktionsreduzierung, Schritte zur Beweissuche nach logischen Programmierparadigmen) haben, die sie implementieren ihre Berechnungen sofort.
Andererseits scheinen sie als Berechnungsmodell geeignet zu sein, da wir mit ihnen alle Arten von Berechnungen modellieren können (binäre Addition ist ein Beispiel), und sie können abstrakt betrachtet werden (indem wir uns nur auf die Wahrheitstabellen und konzentrieren die logischen Gatter und das Vergessen der physischen Schaltung, die sie implementieren könnte).
Also, was denkt ihr?

Wenn es tatsächlich als (augenblickliches) Berechnungsmodell betrachtet werden kann, habt ihr ein Beispiel für ein anderes ähnliches (auch augenblickliches) Berechnungsmodell?

vielen Dank im Voraus

nerdig
quelle
Vielleicht möchten Sie sich das ansehen: stackoverflow.com/questions/4908893/…
Benutzer

Antworten:

9

Logikschaltungen sind in der Komplexitätstheorie üblich, wo sie als Schaltungen bezeichnet werden . Es gibt einen großen Unterschied zwischen Schaltkreisen und Rechenmodellen wie der Turing-Maschine: Jeder Schaltkreis kann nur Eingaben fester Größe verarbeiten. Um dies zu beheben, gibt es unter dem Schaltungsberechnungsmodell für jede Eingangslänge eine Schaltung , und zusammen berechnen sie eine Funktion für Zeichenketten beliebiger Länge. Dieses Rechenmodell ist, wie gesagt, zu stark: Es kann nicht berechenbare Funktionen berechnen, in der Tat alle Funktionen. Das Problem ist, dass eine unendliche Folge von Schaltkreisen nicht unbedingt eine endliche Beschreibung hat. Um dieses Problem zu beheben, fordern wir normalerweise, dass die Schaltkreise gleichmäßig sindC n n C nnC.ndas heißt, dass sie von einer Turing-Maschine erzeugt werden, die bei Eingabe erzeugt .nC.n

Das Schaltungsmodell ist in der Komplexitätstheorie auch ohne die Einschränkung der Gleichmäßigkeit besonders beliebt. Der Grund ist die folgende Beobachtung: Eine Turingmaschine, die in Polynomzeit läuft, kann in eine (einheitliche) Folge von Schaltkreisen mit Polynomgröße umgewandelt werden, wobei im Wesentlichen die Ideen des Cookschen Theorems verwendet werden (was zeigt, dass SAT NP-vollständig ist). Wenn Sie also beweisen möchten, dass ein bestimmtes Problem nicht in Polynomzeit gelöst werden kann, reicht es aus, zu zeigen, dass es nicht durch Schaltungen mit Polynomgröße gelöst werden kann.

Yuval Filmus
quelle
Ich glaube, ich verstehe den Kern dieser Antwort. Korrigieren Sie mich, wenn ich falsch liege: Die zeitliche Komplexität einer Turing-Maschine begrenzt die räumliche Komplexität einer analogen Schaltungsmaschine. Aber ich verstehe diese Aussage nicht: "Das Berechnungsmodell [der Schaltung] ist, wie gesagt, zu stark: Es kann nicht berechenbare Funktionen berechnen, tatsächlich alle Funktionen." Das Modell selbst ist zu stark? Oder ist Ihre anfängliche Aussage des Modells stärker als das Modell tatsächlich?
Kdbanman
Uneingeschränkte Schaltungen sind ein zu starkes Rechenmodell. Sie müssen sie irgendwie einschränken - entweder ihre Größe oder Struktur einschränken oder verlangen, dass sie einheitlich sind oder beides.
Yuval Filmus
Warum aber das Modell einschränken? Welchen Einschränkungen müssen sie entsprechen? Wenn sie ein theoretisches Konstrukt sind, können sie dann nicht tun, was wir wollen?
Kdbanman
Sie können, aber dann sind sie für die Komplexitätstheorie nicht nützlich, da sie jede mögliche Funktion berechnen können.
Yuval Filmus