¿Se puede implementar algún programa mecánicamente?

13

¿Es posible construir una implementación mecánica de un solo propósito (no completa de Turing) de, por ejemplo, Microsoft Word? ¿Es posible implementar cosas como iteradores, funciones de primer orden, toda la gama de técnicas de programación? ¿Podrían los engranajes y otras partes mecánicas representar estructuras de datos o incluso programar objetos? En cierto punto, ¿esto requiere construir una máquina equivalente a Turing de propósito general, o puede cada función, variable, etc., tener su propia construcción mecánica única en forma de volantes y / o engranajes, trinquetes, ¿qué tiene usted? En resumen, me pregunto si cualquier pieza de software en una computadora estándar podría compilarse en un plano mecánico.

computability pl.programming-languages machine-models ar.hardware-architecture Alex Nye
fuente
Creo que algo que ejecuta Microsoft Word ni siquiera necesita ejecutarse en una máquina Turing, ya que todos los procedimientos en Word deberían (probablemente) terminar (excepto si hay un error de c), aparte del bucle de eventos principal.
Realz Slaw
1
Si señor !
Pratik Deoghare
1
Si esto es posible, lo que parece probable, entonces debería ser posible crear una máquina que no sea completa durante un tiempo que actúe como un compilador, creando planos para otras máquinas a partir del código fuente. Máquinas que pueden o no estar completadas.
Nick Johnson el
@Realz Slaw: no si incluye E / S, macros VBA o extensiones. Por ejemplo, dudo que Word se queje si le proporciona un documento de Word infinito. Probablemente sea el sistema operativo subyacente el que alcanzaría un límite.
reinierpost
@reinierpost pero no es necesario que cada rutina esté completa; probablemente terminarían o probablemente no. Es decir, si lo alimentaste con un documento infinito, probablemente no terminaría. Mi punto fue que la mayoría de los programas que hacemos no tienen que usar un lenguaje completo de Turing, porque podemos limitarlo a programas que podemos probar que terminan, dados datos no infinitos, y no terminan si se les dan datos infinitos; y si puede hacer esto, no hay problema con el problema de detención. TLDR; Si no puede probar que sus rutinas terminan o no, es un programador terrible.
Realz Slaw

Respuestas:

23

Sí lo es. Así es como lo haces:

Puedes compilar básicamente cualquier programa que te guste en circuitos. Vea, por ejemplo, el trabajo de Dan Ghica y sus colaboradores en Geometry of Synthesis, que muestra cómo compilar programas en circuitos.

  1. Dan R. Ghica. Geometría de síntesis: un enfoque estructurado para el diseño VLSI
  2. Dan R. Ghica, Alex Smith. Geometry of Synthesis II: de los juegos a los circuitos insensibles al retraso
  3. Dan R. Ghica, Alex Smith. Geometría de Síntesis III: Gestión de recursos mediante inferencia de tipos.
  4. Dan R. Ghica, Alex Smith, Satnam Singh. Geometría de síntesis IV: compilación de recursividad afín en hardware estático.

Los circuitos luego vuelven a aparecer una y otra vez en ingeniería. John Baez ofrece una gran tabla de analogías de conceptos y resuelve muchas conexiones en los hallazgos de esta semana 288-296. Por lo tanto, los diagramas de circuitos que genera el compilador de Dan podrían instanciarse como sistemas mecánicos o hidráulicos, ¡si realmente lo desea!

╔══════════════════════════════════════════════════════════════╗
║                 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              ║
╚══════════════════════════════════════════════════════════════╝
  1. http://math.ucr.edu/home/baez/week288.html
  2. http://math.ucr.edu/home/baez/week289.html
  3. http://math.ucr.edu/home/baez/week290.html
  4. http://math.ucr.edu/home/baez/week291.html
  5. http://math.ucr.edu/home/baez/week294.html
  6. http://math.ucr.edu/home/baez/week296.html
Neel Krishnaswami
fuente
12
Corolario: las patentes de software no tienen sentido.
András Salamon
1
Fantástica respuesta para una pregunta que apenas sabía cómo hacer. ¡Gracias por el gráfico agregado!
Alex Nye
5

Un ejemplo práctico de esto es la computadora Tic Tac Toe hecha de Tinker Toys en el Museo de Ciencias de Boston (originalmente hecha por un equipo de estudiantes del MIT). Por supuesto, esto es mucho más simple que Microsoft Word.

Aquí hay un artículo de 1989 de Scientific American que lo describe.

También ha habido máquinas de Turing hechas de legos (esto hace un poco de trampa porque usa electricidad --- de hecho una computadora --- para moverse, pero creo que el diseño podría modificarse para evitar esto) chatarra , y más.

SamM
fuente
Disfruté el artículo y la máquina de lego, gracias.
Alex Nye
1

Al tratar de abordar específicamente su ejemplo de crear un editor en hardware, se construyó una computadora experimental temprana que implementó tanto el sistema operativo como el editor completamente en hardware. Más tarde, el editor fue reemplazado por software, lo que redujo sustancialmente el hardware necesario. Esto fue descrito en un libro sobre arquitectura e historia de computadoras. Desafortunadamente, he olvidado el nombre y no he encontrado las palabras clave para rastrear la fuente original.

Bill Simpson
fuente