Construí una computadora mecánica impulsada por canicas. ¿Cuáles son sus limitaciones teóricas?

8

En los últimos dos años, construí una computadora mecánica impulsada por canicas e hice un juego con ella. Es similar al antiguo Digi-Comp II, excepto por dos diferencias clave:

  1. Las piezas son reposicionables en el tablero.
  2. Puede conectar múltiples 'bits' juntos usando engranajes. Cuando uno de estos bits se voltea, voltea los otros bits conectados a él.

El enlace de arriba describe cómo funciona. Mi pregunta es, ¿cuáles son sus limitaciones teóricas? Mi formación teórica en informática es débil, así que por favor ELI5.

editar: No estoy interesado en las limitaciones obvias: velocidad (no voy a ganar ninguna carrera allí ...), tamaño del tablero o # de canicas. Estoy más interesado en sus limitaciones teóricas. Quizás ayudaría dividirlo en dos preguntas:

  1. ¿Cómo se puede probar (o refutar) que se completa con Turing?
  2. Si se conectan más de 3 brocas, la fricción se vuelve demasiado grande para que una canica las gire todas a la vez. ¿Eso crea limitaciones adicionales?

Gracias. ¡Estoy realmente emocionado de leer tus respuestas! He estado pensando en esto por mucho tiempo.

complexity-theory turing-machines computer-architecture computation-models Paul Boswell
fuente
3
¿Desea considerar un modelo idealizado (tamaño de cuadrícula infinito, infinitas canicas) o la máquina específica en cuestión? Mirando el melagne de etiquetas que eligió, ¿puede reducir qué preguntas desea abordar? ¿Qué se puede calcular? ¿Qué tan rápido se pueden calcular las cosas? ¿Qué preguntas sobre arquitectura tienes en mente?
Raphael
1
La forma más fácil de reducir las capacidades de su modelo es responder estas preguntas. 1) ¿Qué son las entradas y salidas? 2) ¿Qué puertas lógicas puedes modelar? Estoy preguntando 2) porque está claro que no tienes una computadora universal allí; Cada configuración de placa es un programa fijo, y eso corresponde estrechamente a los circuitos. Por lo tanto, si puede simular cualquier conjunto completo de puertas (por ejemplo, puertas NAND), tiene un modelo completo de Turing (suponiendo infinitas cosas). Sin embargo, como no tiene ningún componente estático con dos entradas y una sola salida, no veo de inmediato lo que está sucediendo.
Raphael
2
Dicho esto, ¡proyecto interesante! Háganos saber en Computer Science Chat cuando se lance.
Raphael
3
En el video, usted dice: si crea una placa lo suficientemente grande, puede hacer lo que cualquier computadora puede hacer. Bueno, sí y no: dada una computadora, puedes (teóricamente) construir una placa lo suficientemente grande, pero dada una placa, puedes construir una computadora que necesite una placa más grande, y eso significa que tus placas no están completas. La integridad de Turing requiere operar en memoria arbitrariamente grande , algo que sus placas no pueden hacer. Cada máquina de Turing es el límite de una serie infinita de máquinas de Turing de cinta finita, pero eso no hace que las máquinas de Turing de cinta finita sean completas.
reinierpost
2
Si hace que agrandar una placa sea parte de la operación de la máquina, se completarán.
reinierpost

Respuestas:

3

Lo que tienes ahora es una computadora concreta. No podemos compararlo con un modelo computacional hasta que esté formalizado adecuadamente.

Mi intuición es que la placa podría modelarse como una arquitectura de flujo de datos . Los modelos computacionales concebidos de acuerdo con este paradigma pueden ser completos para Turing, pero (como se dijo en los comentarios) ninguna computadora concreta será equivalente a Turing, y no creo que deba preocuparse por esto. Todas las computadoras reales son solo metáforas de trabajo (imperfectas) de modelos computacionales formales.

Si llega a la idea de imitar más de cerca una máquina de flujo de datos equivalente a Turing, hay algunos problemas que podrían abordarse para "fortalecer la metáfora", por así decirlo. La introducción de ciclos y composición de máquinas serían las dos cosas más importantes, en mi opinión, pero creo que su máquina ya es bastante sorprendente. Cumple su propósito muy bien, y estas "mejoras" podrían sacrificar su usabilidad.

André Souza Lemos
fuente
¡Gracias! Y muy útil! No sabía sobre la distinción entre la arquitectura de flujo de datos y, digamos, la arquitectura de Von Neumann antes. Me imaginé que, si el tablero fuera más grande, se podría construir una arquitectura Von Neumann. ¿Alguna posibilidad de que pueda ofrecer una definición o un enlace a lo que quiere decir con "ciclos" y "composición"?
Paul Boswell
Para los ciclos, imagine que hay una manera de enviar las canicas de regreso, al inicio o a alguna memoria intermedia en el medio. Eso le permitiría calcular algunos tipos de funciones recursivas primitivas. La composición de las máquinas es similar a la composición de las funciones. Imagine que podría conectar la salida de una placa a la entrada de otras.
André Souza Lemos
Una computadora von Neumann es un gran ciclo.
André Souza Lemos