Ich habe einen mechanischen Computer gebaut, der mit Murmeln betrieben wird. Was sind ihre theoretischen Grenzen?

8

In den letzten Jahren habe ich einen mechanischen Computer gebaut, der mit Murmeln betrieben wird, und daraus ein Spiel gemacht. Es ähnelt dem alten Digi-Comp II, abgesehen von zwei wesentlichen Unterschieden:

  1. Teile können auf der Platine neu positioniert werden.
  2. Sie können mehrere "Bits" über Zahnräder miteinander verbinden. Wenn eines dieser Bits umgedreht wird, werden die anderen damit verbundenen Bits umgedreht.

Der obige Link beschreibt, wie es funktioniert. Meine Frage ist, wo liegen die theoretischen Grenzen? Mein theoretischer Computerhintergrund ist schwach, also bitte ELI5.

edit: Ich bin nicht an den offensichtlichen Einschränkungen interessiert: Geschwindigkeit (ich werde dort keine Rennen gewinnen ...), Brettgröße oder Anzahl der Murmeln. Ich interessiere mich mehr für seine theoretischen Grenzen. Vielleicht würde es helfen, es in zwei Fragen aufzuteilen:

  1. Wie kann nachgewiesen (oder widerlegt) werden, dass Turing vollständig ist?
  2. Wenn mehr als 3 Zahnräder miteinander verbunden sind, wird die Reibung zu groß, als dass ein Marmor sie alle gleichzeitig drehen könnte. Schafft das zusätzliche Einschränkungen?

Danke - ich freue mich sehr auf Ihre Antworten! Ich habe lange darüber nachgedacht.

complexity-theory turing-machines computer-architecture computation-models Paul Boswell
quelle
3
Möchten Sie ein idealisiertes Modell (unendliche Gittergröße, unendlich viele Murmeln) oder die jeweilige Maschine in Betracht ziehen? Können Sie anhand der Melagne der von Ihnen ausgewählten Tags eingrenzen, welche Fragen Sie beantworten möchten? Was kann berechnet werden? Wie schnell können Dinge berechnet werden? Welche Fragen zur Architektur haben Sie im Sinn?
Raphael
1
Die einfachste Möglichkeit, die Funktionen Ihres Modells einzugrenzen, besteht darin, diese Fragen zu beantworten. 1) Was sind Ein- und Ausgabe? 2) Welche logischen Gatter können Sie modellieren? Ich frage 2), weil es klar ist, dass Sie dort keinen Universalcomputer haben; Jede Kartenkonfiguration ist ein festes Programm, das den Schaltkreisen sehr nahe kommt. Wenn Sie also einen vollständigen Satz von Gates (z. B. NAND-Gates) simulieren können, haben Sie ein Turing-vollständiges Modell (unter der Annahme von unendlich allem). Da Sie keine statische Komponente mit zwei Eingängen und einem einzigen Ausgang haben, sehe ich jedoch nicht sofort, was los ist.
Raphael
2
Das heißt, interessantes Projekt! Bitte lassen Sie es uns im Computer Science Chat wissen, wenn es startet.
Raphael
3
Im Video sagst du: Wenn du ein Board groß genug machst, kann es das, was jeder Computer kann. Ja und nein: Wenn Sie einen Computer haben, können Sie (theoretisch) ein ausreichend großes Board bauen, aber wenn Sie ein Board haben, können Sie einen Computer bauen, der ein größeres Board benötigt - und das bedeutet, dass Ihre Boards nicht vollständig sind. Um die Vollständigkeit zu gewährleisten, muss ein beliebig großer Speicher verwendet werden, was Ihre Boards nicht können. Jede Turingmaschine ist die Grenze einer unendlichen Reihe von Turingmaschinen mit endlichen Bändern, aber das macht Turingmaschinen mit endlichen Bändern nicht vollständig.
Reinierpost
2
Wenn Sie das Vergrößern einer Platine zu einem Teil des Maschinenbetriebs machen, wird Turing vollständig.
Reinierpost

Antworten:

3

Was Sie gerade haben, ist ein konkreter Computer. Wir können es nicht mit einem Rechenmodell vergleichen, bis es richtig formalisiert ist.

Meine Intuition ist, dass das Board als Datenflussarchitektur modelliert werden könnte . Computermodelle, die nach diesem Paradigma konzipiert wurden, können Turing-vollständig sein, aber (wie in den Kommentaren erwähnt) wird kein konkreter Computer jemals Turing-äquivalent sein, und ich denke nicht, dass Sie sich darüber Sorgen machen sollten. Alle realen Computer sind nur (unvollkommene) Arbeitsmetaphern formaler Rechenmodelle.

Sollten Sie auf die Idee kommen, eine Turing-äquivalente Datenflussmaschine genauer zu imitieren, gibt es einige Probleme, die behoben werden könnten, um sozusagen "die Metapher zu stärken". Die Einführung von Zyklen und die Zusammensetzung von Maschinen wären meiner Meinung nach die beiden wichtigsten Dinge, aber ich denke, Ihre Maschine ist bereits ziemlich erstaunlich. Es erfüllt seinen Zweck sehr gut, und diese "Verbesserungen" könnten seine Verwendbarkeit opfern.

André Souza Lemos
quelle
Vielen Dank! Und sehr hilfreich! Ich wusste vorher nichts über die Unterscheidung zwischen Datenflussarchitektur und beispielsweise Von Neumann-Architektur. Ich stellte mir nur vor, dass eine Von Neumann-Architektur gebaut werden könnte, wenn das Board größer wäre. Gibt es eine Chance, dass Sie eine Definition oder einen Link zu dem anbieten, was Sie unter "Zyklen" und "Komposition" verstehen?
Paul Boswell
Stellen Sie sich für Zyklen vor, dass es eine Möglichkeit gibt, die Murmeln wieder nach oben, zum Start oder zu einem Zwischenspeicher in der Mitte zu senden. Auf diese Weise können Sie einige Arten primitiver rekursiver Funktionen berechnen. Die Zusammensetzung von Maschinen ähnelt der Zusammensetzung von Funktionen. Stellen Sie sich vor, Sie könnten den Ausgang einer Karte mit dem Eingang anderer verbinden.
André Souza Lemos
Ein von Neumann-Computer ist ein großer Zyklus.
André Souza Lemos