¿Existe un nombre para "cosas físicas con las cuales uno puede construir una máquina de Turing"?

16

Una de las cosas sorprendentes de la informática es que la implementación física es en cierto sentido "irrelevante". La gente ha construido computadoras con éxito a partir de varios sustratos diferentes: relés, tubos de vacío, transistores discretos, etc. La gente puede tener éxito pronto en la construcción de computadoras completas de Turing con materiales ópticos no lineales, varias biomoléculas y algunos otros sustratos. En principio, parece posible construir una computadora con bolas de billar .

Sin embargo, el sustrato físico no es completamente irrelevante. La gente ha descubierto que ciertos conjuntos de componentes, en particular, la lógica de la resistencia de diodo , están "incompletos": no importa cuántos de ellos conecte a una fuente de alimentación y entre sí, hay ciertas cosas muy simples que no puede hacer. (La lógica de la resistencia de diodo puede implementar AND, OR, pero no implementa NOT). Además, ciertas formas de conectar componentes, en particular, el perceptrón s de capa única , son "incompletas": hay ciertas cosas muy simples que no pueden hacer. (Un perceptrón de una sola capa puede implementar AND, OR, NOT, pero no puede implementar XOR).

¿Existe una frase menos incómoda para "cosas físicas con las cuales uno puede construir una máquina de Turing"? ¿O por el contrario, "cosas físicas que, sin importar cuántas de ellas tenga, no pueden formar una máquina de Turing"?

Durante un tiempo utilicé la frase "conjunto funcionalmente completo" o "conjunto universal de puertas", o, al hablar con matemáticos, "cosas físicas que pueden implementar un conjunto funcionalmente completo", pero me han dicho que eso no es t bastante correcto. Algunos conjuntos de componentes pueden implementar un conjunto funcionalmente completo; y, sin embargo, no es posible construir una máquina completa de Turing completamente con estos componentes. Por ejemplo, las bombillas y los interruptores de luz de 4 vías operados manualmente pueden implementar un conjunto funcionalmente completo (AND, OR, NOT, XOR, etc.); y, sin embargo, no es posible construir una máquina completa de Turing completamente con interruptores de luz y bombillas, ya que la salida (eléctrica u óptica) de uno no se puede alimentar a la entrada (mecánicamente giratoria) de la siguiente.

relacionado: ¿Existe un nombre oficial para una noción de "reutilizable universalmente"? y ¿Hay un nombre para "chips con los que se puede construir una CPU"?

David Cary
fuente
1
Esta no es una respuesta, pero no puedo publicar comentarios y sentí la necesidad de dar el enlace a este increíble cómic xkcd: [A Bunch of Rocks] [1] que está relacionado con esta pregunta :). [1]: xkcd.com/505
Zenon

Respuestas:

3

Creo que un término apropiado es "una implementación física de la máquina Turing".

PAGnortePAG, por lo que sería poco probable que un informático los resolviera.

Puede leer más en el documento NP-complete Problemas y realidad física de Scott Aaronson , especialmente en la sección de computación Analógica y Relatividad.

También puede encontrar una implementación de lego (con cinta finita) en la siguiente página: http://legoofdoom.blogspot.com/

chazisop
fuente
+1 para los Legos: ¡vaya! Esperaba encontrar una frase un poco más fácil de entender que "Una implementación física de una máquina de Turing puede estar compuesta de este conjunto de partes", pero esto es aún mucho mejor que las alternativas que he visto hasta ahora.
David Cary
4

La física modela la realidad con teorías que definen un concepto de estado dependiente del tiempo asociado a un sistema y un operador de evolución temporal que describe cómo evoluciona este estado. Tan pronto como encuentre un sistema físico que (después de una discretización de espacio de estado) implemente el espacio de estado de su máquina Turing, y que incluya términos de interacción que implementen (tal vez después de una discretización de tiempo) la evolución del tiempo de acuerdo con la tabla de transición de estado de En su máquina Turing en su espacio de estado, ha encontrado un modelo físico completo de su sistema. Por lo tanto, puede decir que su sistema "es" completo de Turing.

Al observar la computación cuántica, encontrará discusiones sobre las implicaciones que las teorías físicas tienen sobre el modelo de computación de Turing. Por ejemplo, las teorías físicas tienen que ser reversibles. Una propiedad que no es compartida por las máquinas de Turing normales. Sin embargo, no hay pérdida en general, ya que cualquier máquina de Turing puede ser simulada por una reversible, con algunos gastos generales que pueden compensar el tiempo frente al espacio, etc.

Martin Schwarz
fuente
Este texto está lleno de conceptos y terminología interesantes. Desgraciadamente, no veo ninguna frase aquí que pueda usar como "Este es un conjunto de componentes de <frase>, mientras que esos son un conjunto de componentes de <sin frase>".
David Cary
3

Solo pensé en señalar que la integridad de un medio físico para simular la lógica requerida para hacer que una máquina de computación completa de Turing se pueda establecer únicamente en su capacidad de incorporar una puerta NAND, ya que todas las otras puertas pueden derivarse de las puertas NAND (una podría preguntar qué comprende las compuertas NAND, y esa es una pregunta muy inteligente, ¡pero son compuertas NAND hasta el fondo!).

Deberías mirar el trabajo de Charles Babbage y las personas que él inspiró. Babbage hizo una computadora física para tabular funciones polinomiales en tablas impresas para índices matemáticos (en el pasado, tendría pilas de libros que no tenían más que nombres de funciones seguidos de hojas de valores f (x)). Este último comenzó a trabajar en lo que se ha convertido en una computadora completa de Turing usando levas de engranaje y demás. Su hijo, creo, continuó su trabajo y la única manifestación física de sus esfuerzos combinados fue un ALU mecánico que funcionaba en su totalidad, que es la base de esas calculadoras mecánicas que puede conocer o no. Sin embargo, la financiación de estos proyectos se redujo como una computadora mecánica en el tamaño y la forma en que se podrían hacer en ese momento no era muy práctico. Sin embargo, desde entonces, y especialmente en eventos recientes, la gente ha pasado y está promoviendo la investigación de Charles Babbage. Este enfoque puede tener su última risa, ya que hay quienes piensan que la única forma de hacer CPU en serie más rápido de lo que son ahora sería implementar algunos de estos enfoques mecánicos dentro de una CPU para evitar los problemas que se derivan de la electromagnética a una escala menor que el que usamos ahora. La mecánica funciona en cualquier escala aparentemente.

Del mismo modo, se ha trabajado en lo que se llama la computadora cuántica que busca facilitar grandes cálculos a través de la teoría cuántica, no estoy completamente seguro de cómo funciona todo. Pero físicamente atrae a los experimentos de física de partículas que se basan en la teoría cuántica.

Estoy seguro de que se están explorando muchos más medios informáticos diferentes, incluso rocas en el desierto, pero de ellos no tengo experiencia.

acp10bda
fuente
Las bombillas y los interruptores de luz pueden implementar NAND. Hay una configuración de 2 interruptores de luz ordinarios y una bombilla de luz de salida (y una segunda bombilla de luz oculta) donde la bombilla de luz de salida permanece BRILLANTE, excepto cuando un humano enciende ambos interruptores a ENCENDIDO, luego la bombilla de salida se oscurece. Por desgracia, aparentemente (?) No es posible construir una máquina completa de Turing completamente con interruptores de luz y bombillas. ¿Hay algún término que pueda usar que incluya el 74HC132 NAND pero excluya los interruptores y bombillas NAND?
David Cary
Bueno, el problema es que la entrada es mecánica y la salida es eléctrica, por lo que los interruptores son como una conversión y una puerta entre dos dominios (cinética a electrónica). Suponiendo que funciona como una puerta trasera, PODRÍAS hacer una computadora completa de Turing con ellos, es solo que tendrías que facilitar la conversión entre estos dos medios para que la salida de una puerta se ingrese a otra, posiblemente un interruptor motorizado, pero Sí poco práctico. Un término que podría usar que voy a maquillar ahora es nandgate del mismo medio, que estipula que la entrada y la salida estén en el mismo medio.
acp10bda
+1 buena idea: solo invente un término y defínalo para que sea exactamente el término que estoy buscando. El conjunto {(una caja con 2 interruptores de luz de entrada y una bombilla de salida que implementa AND), (un interruptor de interruptor motorizado activado por luz que implementa NOT)} es un conjunto en cascada d-universal. Pero el conjunto {bombillas, interruptores de luz} por sí solo no es un conjunto en cascada d-universal.
David Cary
¿Es posible construir una máquina de Turing con cosas que no son nandgates del mismo medio?
David Cary
Perdón por la tardanza de esta respuesta, pero sí. Una máquina de Turing podría estar hecha de cualquier conjunto de componentes utilizando cualquier variedad de medios de entrada y salida, siempre que los componentes estén dispuestos de tal manera que el resultado sea un mecanismo completo de Turing. Sin embargo, dado que el medio de cómputo se volvería muy variante y potencialmente muy interesante de ver trabajar, me gustaría referirme a un mecanismo como un mecanismo completo de Rube-Goldberg-Turing. :)
acp10bda