Kann irgendein Programm mechanisch implementiert werden?

Ist es möglich, eine einzelne (nicht Turing-vollständige) mechanische Implementierung von Microsoft Word zu erstellen? Ist es möglich, Dinge wie Iteratoren, Funktionen erster Ordnung und die gesamte Bandbreite der Programmiertechniken zu implementieren? Könnten Zahnräder und andere mechanische Teile Datenstrukturen oder sogar Programmobjekte darstellen? Zu einem bestimmten Zeitpunkt muss eine Allzweck-Turing-äquivalente Maschine gebaut werden, oder kann jede Funktion, Variable usw. ein eigenes mechanisches Konstrukt in Form von Schwungrädern und / oder Zahnrädern, Ratschen haben. Was haben Sie? Zusammenfassend frage ich mich, ob eine bestimmte Software auf einem Standardcomputer zu einer mechanischen Blaupause kompiliert werden kann.

computability pl.programming-languages machine-models ar.hardware-architecture Alex Nye
quelle

Ich denke, etwas, das Microsoft Word ausführt, muss nicht einmal auf einer Turing-Maschine ausgeführt werden, da bekannt sein sollte, dass alle Prozeduren in Word abgesehen von der Hauptereignisschleife (nachweislich) beendet werden (es sei denn, es liegt ein Fehler von c vor).

Realz Slaw

Ja, mein Herr !

Pratik Deoghare

Wenn dies möglich ist - was wahrscheinlich erscheint -, sollte es möglich sein, eine nicht vollständig funktionierende Maschine zu erstellen, die als Compiler fungiert und Blaupausen für andere Maschinen aus dem Quellcode erstellt. Maschinen, die selbst komplett sind oder nicht.

Nick Johnson

@ Realz Slaw: Nicht, wenn Sie E / A-, VBA-Makros oder Erweiterungen einschließen. Beispielsweise bezweifle ich, dass Word sich beschweren würde, wenn Sie ein unendliches Word-Dokument einspeisen würden. Es ist wahrscheinlich das zugrunde liegende Betriebssystem, das eine Grenze erreichen würde.

Reinierpost

@reinierpost, aber jede Routine muss nicht vollständig sein. sie würden entweder nachweislich kündigen oder nachweislich nicht. Das heißt, wenn Sie ein unendliches Dokument einspeisen, wird es nachweislich nicht beendet. Mein Punkt war , dass die meisten Programme , die wir machen müssen kein Turing komplette Sprache verwenden, weil wir es Programme beschränken können , dass wir beenden nachweisen können, da nicht unendliche Daten und endet nicht , wenn gegeben unendlich Daten; und wenn Sie dies tun können, gibt es kein Problem mit dem Halteproblem. TLDR; Wenn Sie nicht beweisen können, dass Ihre Routinen beendet sind oder nicht, sind Sie ein schrecklicher Programmierer.

Realz Slaw

Antworten:

Ja ist es. So machst du es:

Sie können grundsätzlich jedes Programm kompilieren, das Sie zu Schaltungen mögen. Sehen Sie sich zum Beispiel die Arbeit von Dan Ghica und seinen Mitarbeitern zur Geometrie der Synthese an, die zeigt, wie man Programme zu Schaltkreisen kompiliert.

Dan R. Ghica. Synthesegeometrie: Ein strukturierter Ansatz für das VLSI-Design
Dan R. Ghica, Alex Smith. Synthesegeometrie II: Von Spielen zu verzögerungsunempfindlichen Schaltungen
Dan R. Ghica, Alex Smith. Synthesegeometrie III: Ressourcenmanagement durch Typinferenz.
Dan R. Ghica, Alex Smith, Satnam Singh. Synthesegeometrie IV: Kompilieren der affinen Rekursion in statische Hardware.

Die Schaltkreise tauchen dann im Engineering immer wieder auf. John Baez gibt in This Week's Finds 288-296 eine große Tabelle mit Analogien von Konzepten und erarbeitet viele Zusammenhänge. Die Schaltpläne, die Dans Compiler generiert, könnten also als mechanische oder hydraulische Systeme instanziiert werden, wenn Sie es wirklich wollten!

╔══════════════════════════════════════════════════════════════╗
║                 displacement  flow      momentum     effort  ║
╠══════════════════════════════════════════════════════════════╣
║ Mechanics      position      velocity  momentum     force    ║
║ (translation)                                                ║
║                                                              ║
║ Mechanics      angle         angular   angular      torque   ║
║ (rotation)                   velocity  momentum              ║
║                                                              ║
║ Electronics    charge        current   flux         voltage  ║
║                                        linkage               ║
║                                                              ║
║ Hydraulics     volume        flow      pressure     pressure ║
║                                        momentum              ║
╚══════════════════════════════════════════════════════════════╝

Neel Krishnaswami
quelle

Fazit: Softwarepatente machen keinen Sinn.

András Salamon

Fantastische Antwort auf eine Frage, die ich kaum stellen konnte. Vielen Dank für die hinzugefügte Grafik!

Alex Nye

Ein praktisches Beispiel hierfür ist der Tic Tac Toe-Computer aus Tinker Toys im Boston Science Museum (ursprünglich von einem Team von MIT-Studenten hergestellt). Dies ist natürlich viel einfacher als Microsoft Word.

Hier ist ein Artikel von Scientific American aus dem Jahr 1989, der dies beschreibt.

Es gab auch Turing-Maschinen aus Legos (das schummelt ein bisschen, weil es Elektrizität - in der Tat einen Computer - zum Bewegen verwendet, aber ich denke, das Design könnte geändert werden, um dies zu vermeiden), Schrott und vieles mehr.

SamM
quelle

Ich habe den Artikel und die Legomaschine genossen, danke.

Alex Nye

Bei dem Versuch, Ihr Beispiel für das Erstellen eines Editors in Hardware zu erläutern, wurde ein früher experimenteller Computer gebaut, der sowohl das Betriebssystem als auch den Editor vollständig in Hardware implementierte. Später wurde der Editor durch Software ersetzt, was die benötigte Hardware erheblich reduzierte. Dies wurde in einem Buch über Computerarchitektur und -geschichte beschrieben. Leider habe ich den Namen vergessen und die Schlüsselwörter nicht gefunden, um die ursprüngliche Quelle aufzuspüren.

Bill Simpson
quelle