Gibt es einen Namen für "Chips, aus denen man eine CPU bauen kann"?

9

Einige Leute genießen es , "Homebrew" -CPUs aus einfacheren ICs zu bauen.

Gibt es einen Namen für "Chips, aus denen man eine CPU bauen kann, wenn man genug davon hat"? Gibt es einen Namen für die anderen Chips, "Chips, aus denen man keine CPU bauen kann, egal wie viele davon Sie haben"?

Man kann eine CPU aus ausreichend großen Mengen von 4: 1-Mux-Chips bauen ( Multiplexer sind die taktische Nuke von Logic Design ). Man kann eine CPU aus (etwas größeren) Mengen von 2-in-NAND-Gattern bauen. Oder von 2-in-NOR-Gattern. Oder von ein paar (vielleicht einem) CPLD oder FPGA.

Jedoch,

Eine CPU kann nicht allein aus 2-in-XOR-Gattern aufgebaut werden. Man kann eine CPU nicht allein aus der Diodenwiderstandslogik bauen . Man kann eine CPU nicht allein aus Flip-Flops vom Typ D bauen.

Gibt es einen Begriff oder eine Phrase zur Unterscheidung dieser beiden Kategorien von Chips, der weniger umständlich ist als "Chips, aus denen man eine CPU bauen kann"?

Davidcary
quelle
6
Ein Problem , das ich mit dieser Frage haben (was bedeutet , vielleicht können Sie es verbessern, oder ich etwas fehlt) ist , dass man vage auf die sich sein , wie Sie sein evaluate der Lage zu „bauen eine CPU“ aus. Ist dies eine Entwurfsfrage (Logikfrage) oder eine Frage der IC-Familie? Fragen Sie nach den logischen Anforderungen für den Entwurf eines vollständigen Turing-Computers?
mctylr
1
@mctylr: Ja - Wie nennt man die Art von Chips wie den 4: 1-Mux, mit denen man einen Turing-vollständigen Computer vollständig aus diesem Chip heraus entwerfen kann? Ich vermute, dass jede IC-Familie einen IC hat, aus dem man (in ausreichender Anzahl) einen Turing-vollständigen Computer bauen kann; und hat einen anderen IC, der allein nicht ausreicht, um einen Turing-vollständigen Computer zu bauen. Welche Terminologie kann ich verwenden, um die erste Art von Chip von der zweiten Art von Chip zu unterscheiden?
Davidcary
@reemrevnivek: Ich dachte, "Diode" hätte etwas mit "Diodenwiderstandslogik" zu tun.
Davidcary

Antworten:

16

Sie müssen in der Lage sein, NICHT und eines von UND und ODER zu tun. Unter Verwendung der Demorganschen Gesetze kann eine dieser Funktionen in die andere und von dort in alle anderen logischen Funktionen umgewandelt werden.

Dies wird als funktionale Vollständigkeit oder Ausdrucksadäquanz bezeichnet. Die Komponenten oder Funktionen, die ein solches System erzeugen, werden als Sheffer-Funktionen (nach Henry Sheffer, der einen Beweis zu diesem Thema veröffentlicht hat) oder als alleinige ausreichende Operatoren bezeichnet.

Interessant ist auch die Tatsache, dass Sie ein Quartett von NAND-Gates zu einem D-Flip-Flop und von dort zu einer Speicherzelle kombinieren können, die auch zur Erstellung der Turing-Vollständigkeit erforderlich ist.

Der Artikel von ProofWiki zu diesem Thema ist gut zu lesen.

Kevin Vermeer
quelle
Eine Person auf der Diskussionsseite zur funktionalen Vollständigkeit von Wikipedia behauptet, dass Fredkin-Gates funktionell nicht vollständig sind (da Sie, wenn Sie alle 0 Eingänge auf ein oder mehrere Fredkin-Gates anwenden, die in einer denkbaren Anordnung verdrahtet sind, an keiner Ausgabe eine 1 erhalten können). und noch andere behaupten, Sie könnten eine CPU vollständig aus Fredkin-Gates bauen. Ist ein Fredkin-Tor also tatsächlich "funktional vollständig", oder suche ich nach einer breiteren Kategorie, die "funktional vollständig" und auch Fredkin-Tore umfasst?
Davidcary
@ David - Dies ist ein wenig abseits des Themas, aber wenn Sie den Artikel über Fredkin-Gates lesen, werden Sie feststellen, dass das Fredkin-Gate die Eigenschaft hat, die letzten beiden Bits zu tauschen, wenn das erste Bit 1 ist, und es ist auch reversibel. Wenn Sie zulassen, dass 1 und 0 fest codiert sind, ist es mit ein paar Fredkin-Gates einfach, eine andere Logikfunktion zu erhalten. Wenn Sie jedoch eine Hardcodierung zulassen, ist diese nicht mehr umkehrbar und daher (laut einigen) kein richtiges Fredkin-Gate. Reversibilität ist eine Kategorie, die von der funktionalen Vollständigkeit unabhängig ist, und ich denke, dass die funktionale Vollständigkeit für Ihr Problem ausreicht.
Kevin Vermeer
Wenn Sie alle 0 Eingänge an einen oder mehrere 4: 1-Muxes anlegen, die in einer denkbaren Anordnung verdrahtet sind, können Sie an keinem Ausgang eine 1 erhalten. Ist ein Mux-Chip also tatsächlich "funktional vollständig", obwohl er auf dieser ansonsten hervorragenden ProofWiki-Seite nie erwähnt wird, oder suche ich nach einer breiteren Kategorie, die "funktional vollständig" und auch 4: 1-Mux-Chips umfasst?
Davidcary
@ David - Der 4: 1-Mux ist ein spezielles Gerät für die Elektronik. Auf dem Gebiet der Elektronik sind wir selten, wenn überhaupt, daran interessiert, einen Computer vollständig aus einem IC-Typ zusammenzusetzen, und auf dem Gebiet der theoretischen Informatik (dem Bereich von ProofWiki und dem Begriff "funktionale Vollständigkeit"), Muxes und Andere spezialisierte ICs werden aus Standard-Logikgattern zusammengesetzt. Ich denke, in diesem Niemandsland können Sie Ihre eigenen Begriffe definieren.
Kevin Vermeer
@reemrevnivek: Bei der Herstellung eines Produkts werden häufig Zeit, Geld und Speicherplatz gespart, um einige Arten von generischen Komponenten zu verwenden, die ich in großen Mengen von mehreren Herstellern kaufen kann, anstatt jedes Teil einzeln zu "optimieren" und hochspezialisierte Komponenten zu verwenden das ist nur an einer Stelle in einem Produkt nützlich und dessen Hersteller wird es wahrscheinlich in ein paar Jahren als "nicht mehr für neue Designs empfohlen" deklarieren. ps: schon mal was vom Cray-1 oder dem Apollo Guidance Module gehört? Alles außer dem Speicher vollständig von einem IC-Typ.
Davidcary
5

Der Satz "Chips, aus denen Sie einen Computer bauen können" kann zu Turing-Komplettmaschinen zusammengesetzt werden. Der Rest kann nicht.

Alle Logikgatter können aus Sätzen von entweder nur NAND- oder nur NOR-Gattern zusammengesetzt werden. Wenn Ihr fraglicher IC als einer oder mehrere von diesen fungieren kann, kann er zu einer Turing-Maschine gemacht werden.

Ich kenne keinen bestimmten Begriff, um eine solche Menge zu beschreiben.

Diese Fragen können auch helfen:

/programming/4908893/what-logic-gates-are-required-for-turing-completeness

/programming/7284/what-is-turing-complete

Toby Jaffey
quelle
1
Ausgezeichnet. Die eine Art von Chip ist also "ein Chip, der entweder wie ein NAND-Gatter oder wie ein NOR-Gatter oder beides wirken kann", und die andere Art von Chip ist "ein Chip, der nicht wie ein NAND-Gatter wirken kann". es kann auch nicht wie ein NOR-Gatter wirken ". Konzeptionell viel einfacher. Das ist wahrscheinlich ausreichend, aber ich hatte auf einen Satz gehofft, der mir ein bisschen leichter von der Zunge rollte.
Davidcary
2

Ich stimme der Ansicht zu, dass 4: 1-Multiplexer wunderbar sind. Vor ein paar Jahren habe ich einen 8K-bankvermittelten Speichercontroller für einen Atari 2600 implementiert, der eine einzelne 74xx153 / 74xx253 und eine RC-De-Glitching-Schaltung verwendet. Die Steuerung muss sowohl einen Ausgang bereitstellen, der umgekehrt zum A12-Eingang ist, als auch A6 zwischenspeichern, wenn A11 hoch und A12 niedrig ist. "Damals" (Anfang der 1980er Jahre) verwendeten Bank-Switching-Kassetten entweder benutzerdefiniertes Silizium oder drei TTL-Chips. Mit einem handelsüblichen 74xx153 (der damals verfügbar war) kann die Arbeit jedoch in einem Chip erledigt werden.

Superkatze
quelle