Gibt es einen Namen für "physikalische Dinge, aus denen man eine Turing-Maschine bauen kann"?

16

Eines der erstaunlichen Dinge in der Informatik ist, dass die physikalische Implementierung in gewisser Weise "irrelevant" ist. Die Menschen haben erfolgreich Computer aus mehreren unterschiedlichen Substraten gebaut - Relais, Vakuumröhren, diskrete Transistoren usw. Die Menschen könnten bald erfolgreich Turing-Computer aus nichtlinearen optischen Materialien, verschiedenen Biomolekülen und einigen anderen Substraten bauen. Grundsätzlich scheint es möglich zu sein, einen Billard-Ball-Computer zu bauen .

Das physikalische Substrat ist jedoch nicht völlig irrelevant. Man hat festgestellt, dass bestimmte Komponentengruppen - insbesondere die Dioden-Widerstands-Logik - "unvollständig" sind: Unabhängig davon, wie viele von ihnen an eine Stromversorgung und aneinander angeschlossen werden, gibt es bestimmte sehr einfache Dinge, die nicht möglich sind tun. (Die Diodenwiderstandslogik kann UND, ODER implementieren, implementiert jedoch NICHT). Außerdem sind bestimmte Arten der Verbindung von Bauteilen - insbesondere von einschichtigen Perzeptronen - "unvollständig": Es gibt bestimmte sehr einfache Dinge, die sie nicht ausführen können. (Ein einschichtiges Perzeptron kann AND, OR, NOT implementieren, kann aber kein XOR implementieren.)

Gibt es einen weniger peinlichen Ausdruck für "physische Dinge, aus denen man eine Turing-Maschine bauen kann"? Oder im Gegenteil, "physische Dinge, die, egal wie viele sie haben, keine Turing-Maschine bilden können"?

Für eine Weile habe ich den Ausdruck "funktional vollständiger Satz" oder "universeller Satz von Toren" verwendet - oder, wenn ich mit Mathematikern spreche, "physikalische Dinge, die einen funktional vollständigen Satz implementieren können" - aber mir wurde gesagt, dass dies nicht der Fall ist. nicht ganz richtig. Einige Komponentensätze können einen funktional vollständigen Satz implementieren. und dennoch ist es nicht möglich, eine Turing-Komplettmaschine komplett aus diesen Komponenten zu bauen. Beispielsweise können Glühbirnen und manuell betätigte 4-Wege-Lichtschalter einen funktional vollständigen Satz (AND, OR, NOT, XOR usw.) implementieren. und doch ist es nicht möglich, eine Turing-Komplettmaschine vollständig aus Lichtschaltern und Glühbirnen zu bauen, da der (elektrische oder optische) Ausgang des einen nicht in den (mechanisch rotierenden) Eingang des nächsten eingespeist werden kann.

verwandt: Gibt es einen offiziellen Namen für den Begriff "wiederverwendbar universell"? und gibt es einen Namen für "Chips, aus denen man eine CPU bauen kann"?

David Cary
quelle
1
Dies ist keine Antwort, aber ich kann keine Kommentare posten und ich hatte das Bedürfnis, den Link zu diesem unglaublichen xkcd-Comic zu geben: [A Bunch of Rocks] [1], der mit dieser Frage zusammenhängt :). [1]: xkcd.com/505
Zenon

Antworten:

3

Ich glaube, ein passender Begriff ist "eine physikalische Implementierung einer Turing-Maschine".

Das Hauptproblem bei jeder Implementierung besteht darin, wie ein "unendliches Band" oder in einer abstrakteren Ebene ein unendlicher Speicher bereitgestellt wird. Eine einfache Lösung für dieses Problem besteht darin, ein spezielles Symbol zu verwenden, um das letzte Bandquadrat anzugeben. Wenn eine Turing-Maschine sie erreicht, tritt sie in einen speziellen Zustand ein, der einen Benutzereingriff erfordert, der zusätzliches Band liefert. Dann kann der TM seinen Betrieb fortsetzen. Leider beinhalten solche Implementierungen, die "physikalisch" sind, Physik. Wenn das Universum endlich ist und die Planck-Skala dies zulässt, steht eine begrenzte Menge an Band zur Verfügung. Hier entstehen Probleme, die vielleicht nicht von Informatikern, sondern von Physikern beantwortet werden können. Beachten Sie, dass die Physiker in diesen Fragen, die als große offene Probleme der Größe von , noch keine Schlussfolgerung gezogen habenPNPDaher wäre es unwahrscheinlich, dass ein Informatiker sie lösen würde.

Weitere Informationen finden Sie in Scott Aaronsons Artikel NP-complete Problems and Physical Reality , insbesondere im Abschnitt Analog and Relativity Computing.

Eine Lego-Implementierung (mit endlichem Band) finden Sie auch auf der folgenden Seite: http://legoofdoom.blogspot.com/

Chazisop
quelle
+1 für die Legos - whee! Ich hoffte, einen Ausdruck zu finden, der sich ein wenig leichter von der Zunge rollen lässt als "Eine physikalische Implementierung einer Turing-Maschine kann aus diesen Teilen zusammengesetzt werden" - aber dies ist immer noch weitaus besser als die Alternativen, die ich bisher gesehen habe.
David Cary
4

Die Physik modelliert die Realität mit Theorien, die ein Konzept des zeitabhängigen Zustands definieren, der einem System zugeordnet ist, und einen Zeitentwicklungsoperator, der beschreibt, wie sich dieser Zustand entwickelt. Sobald Sie ein physikalisches System finden, das (nach einer gewissen Diskretisierung des Zustandsraums) den Zustandsraum Ihrer Turing-Maschine implementiert und Interaktionsterme enthält, die (möglicherweise nach einer gewissen Diskretisierung) die Zeitentwicklung gemäß der Zustandsübergangstabelle von implementieren Befindet sich Ihre Turing-Maschine im Zustandsraum, haben Sie ein Turing-vollständiges physikalisches Modell Ihres Systems gefunden. So kann man wohl sagen, Ihr System ist "Turing-complete".

Bei der Betrachtung des Quantencomputers werden die Auswirkungen physikalischer Theorien auf das Turing-Berechnungsmodell diskutiert. Beispielsweise müssen physikalische Theorien reversibel sein. Eine Eigenschaft, die gewöhnliche Turing-Maschinen nicht teilen. Es gibt jedoch keinen Verlust in der Allgemeinheit, da jede Turing-Maschine durch eine reversible Maschine simuliert werden kann, mit einigem Aufwand, der Zeit gegen Raum usw. austauscht.

Martin Schwarz
quelle
Dieser Text steckt voller interessanter Konzepte und Begriffe. Leider sehe ich hier keine Phrase, die ich als "Dies ist eine <phrase> -Komponentenmenge, während dies eine <nicht phrase> -Komponentenmenge ist" verwenden kann.
David Cary
3

Ich möchte nur darauf hinweisen, dass die Vollständigkeit eines physischen Mediums zur Simulation der Logik, die für die Erstellung einer vollständigen Turing-Rechenmaschine erforderlich ist, nur durch die Fähigkeit festgelegt werden kann, ein NAND-Gatter zu verkörpern, da alle anderen Gatter von NAND-Gattern abgeleitet werden können (eins) Ich könnte fragen, was dann die NAND-Gatter ausmacht, und das ist eine sehr clevere Frage, aber es sind die NAND-Gatter ganz unten!).

Sie sollten sich die Arbeit von Charles Babbage und die Menschen ansehen, die er inspiriert hat. Babbage baute einen physischen Computer, um Polynomfunktionen in gedruckte Tabellen für mathematische Indizes zu tabellieren (damals gab es Stapel von Büchern, die nur Funktionsnamen enthielten, gefolgt von Blättern mit f (x) -Werten) sind zu einem Turing-Komplettcomputer mit Zahnrädern und Cams geworden. Sein Sohn Ich glaube, es wurde seine Arbeit fortgesetzt und die einzige physische Manifestation ihrer gemeinsamen Bemühungen war eine voll funktionsfähige mechanische ALU, die die Grundlage für die mechanischen Taschenrechner ist, die Sie vielleicht kennen oder nicht kennen. Die Finanzierung für diese Projekte fiel jedoch als mechanischer Computer in der Größe und Weise aus, wie sie in dieser Zeit hergestellt werden konnten, und war sehr unpraktisch. Seitdem und insbesondere bei jüngsten Ereignissen Leute haben Charles Babbages Forschung durchlaufen und fördern sie. Dieser Ansatz mag zum Lachen kommen, da es diejenigen gibt, die glauben, dass der einzige Weg, um serielle CPUs schneller als bisher zu machen, darin besteht, einige dieser mechanischen Ansätze in einer CPU zu implementieren, um die Probleme der Elektromagnetik in einem kleineren Maßstab als zu vermeiden die wir jetzt benutzen. Mechaniker arbeiten scheinbar in jeder Größenordnung.

In ähnlicher Weise wurde an dem sogenannten Quantencomputer gearbeitet, der große Berechnungen durch die Quantentheorie ermöglichen soll. Ich bin mir nicht ganz sicher, wie das alles funktioniert. Aber es spricht physikalisch Experimente der Teilchenphysik an, die auf der Quantentheorie beruhen.

Ich bin mir sicher, dass noch viele andere Computermedien erforscht werden, sogar Felsen in der Wüste, aber ich habe keine Erfahrung mit ihnen.

acp10bda
quelle
Glühbirnen und Lichtschalter können NAND implementieren. Es gibt eine Konfiguration von 2 gewöhnlichen Lichtschaltern und einer Ausgangsglühlampe (und einer zweiten versteckten Glühlampe), bei der die Ausgangsglühlampe HELL bleibt, es sei denn, ein Mensch schaltet beide Schalter auf EIN, und die Ausgangsglühlampe wird DUNKEL. Leider ist es anscheinend (?) Nicht möglich, eine Turing-Komplettmaschine komplett aus Lichtschaltern und Glühbirnen zu bauen. Gibt es einen Begriff, den ich verwenden kann, der den 74HC132 NAND einschließt, aber den Lichtschalter-und-Glühlampen-NAND ausschließt?
David Cary
Nun, das Problem ist, dass der Eingang mechanisch und der Ausgang elektrisch ist, so dass Schalter wie ein Konversions- und Gatter zwischen zwei Domänen sind (Kinetik zu Elektronik). Angenommen, es funktioniert genau wie ein Nandgate, das Sie KÖNNTEN, um einen Turing-Komplettcomputer daraus zu machen, müssten Sie nur die Konvertierung zwischen diesen beiden Medien vereinfachen, damit die Ausgabe von einem Gate in ein anderes eingegeben wird, möglicherweise in einen motorisierten Schalterflipper ja unpraktisch. Ein Begriff, den Sie verwenden könnten, den ich jetzt nur schminken werde, ist das gleiche Medium nandgate, das festlegt, dass sich Eingabe und Ausgabe auf demselben Medium befinden.
acp10bda
+1 gute Idee - erstelle einfach einen Begriff und definiere ihn so, dass er genau dem Begriff entspricht, nach dem ich suche. Das Set {(eine Box mit 2 Eingangs-Lichtschaltern und einer Ausgangs-Glühbirne, die AND implementiert) (ein lichtaktivierter motorisierter Schalterflipper, der NOT implementiert)} ist ein d-universelles Kaskadierungsset. Aber das Set {Glühbirnen, Lichtschalter} allein ist kein d-universal-Kaskadenset.
David Cary
Ist es möglich, eine Turing-Maschine aus Dingen zu bauen, die keine mittelgroßen Nandgates sind?
David Cary
Entschuldigen Sie die Verspätung dieser Antwort, aber ja. Eine Turing-Maschine kann aus einer beliebigen Baugruppe von Bauteilen mit einer Vielzahl von Eingabe- und Ausgabemedien bestehen, sofern die Bauteile so angeordnet sind, dass ein Turing-Komplettmechanismus entsteht. Angesichts der Tatsache, dass das Medium der Berechnung so wild variabel und möglicherweise sehr interessant für die Beobachtung von Arbeiten werden würde, möchte ich einen solchen Mechanismus als Rube-Goldberg-Turing-Komplettmechanismus bezeichnen. :)
acp10bda