Kombinierte Logikschaltungen und Berechnungstheorie

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 $C_{out}$$C_{in}$

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:

Combinational Logic Circuit (C steht wie in und für Carry): C o u $C_{in}$$C_{out}$

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

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 $n$$C_n$das heißt, dass sie von einer Turing-Maschine erzeugt werden, die bei Eingabe erzeugt .$n$$C_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.