Para las referencias, hay una enorme literatura sobre la tesis de Church-Turing, que nos parece fundamental para su pregunta. (Sigue el enlace para una gran lista de referencias.) Los matemáticos y los filósofos se han enfrentado con varios aspectos de lo que significa encontrar una computadora universal dentro de un sistema. Véase también Copeland del artículo en la tesis de Church-Turing, que también tiene una extensa lista de referencias.
Para encontrar una computadora universal en cualquier caso, uno debe ser capaz de establecer una configuración inicial correspondiente a un determinado programa y la entrada, deje que el sistema evolucione y, a continuación, ser capaz de reconocer cuando el sistema ha llegado a una conclusión para la computación e interpretar el resultado.
El juego de la vida se presenta este fenómeno. Para cualquier Turing
programa de máquina de p y de entrada n, hay un primer
configuración de un juego de la vida, de tal manera que a medida que
configuración evoluciona de acuerdo a las reglas de GOL, el
las configuraciones pueden ser vistos como la simulación de Turing
máquina de computación. El cese de cálculo conduce a una
reconocidas en el GOL de configuración, y cuando
esta característica se produce, la salida de la computación puede ser
leer a partir de esa configuración.
De manera abstracta, podemos decir que una función f de un conjunto C de sí mismo, visto como un sistema dinámico en el sentido de que tenemos la intención de recorrer en f, es vida, si no es un "set-up" de la función s, una terminación conjunto de T y una salida de la interpretación de la función t, de tal manera que un programa de p en la entrada n da salida m si y sólo si al calcular la iteración fk(s(p,n)), a continuación, para los menos k por lo que este valor es en T, la salida de t(fk(s(p,n))) = m. Es decir, podemos configurar el sistema, deja correr libremente, y si y cuando termine, podemos interpretar la salida correctamente.
Usted va a querer insistir en que f, s, y T, son computables (y rápidamente computable) en el sentido de que es aceptable para usted, de lo contrario, no va a ser demasiado computación que ocurren dentro de la configuración o en la salida de la interpretación. (Esta fue la base de su y Gowers respecto a mi anterior cuenta de que el cambio de mapa.)
En esta cuenta, todos los habituales modelos de computabilidad están vivos. Por ejemplo, en el cálculo de registro de máquinas, máquinas de Turing a sí mismos, diagrama de flujo de las máquinas, autómatas con pilas y así sucesivamente, para todos la costumbre de Church-Turing completo de cuentas de la computabilidad. Todos estos pueden ser vistos como sistemas dinámicos en el sentido de thtat el cálculo de las ganancias por la iteración de un relativamente trivial de la función de actualización, correspondiente a un paso de la computación. El juego de la vida, también, está vivo.
El cambio de mapa, por supuesto, actúa de forma natural en el infinito de objetos, que pueden tener una enorme cantidad de información, que el cambio de mapa trae a la vista.
Sin embargo, por la imposición de las exigencias naturales de s, t y T, se puede ver que el cambio de mapa está muerto. Se propuso que, dado que (p,n), debemos establecer una configuración inicial que modifica un fondo aleatorio de la secuencia sólo finitely y, a continuación, ejecute el cambio de mapa.
También vamos a suponer que s, t y T son computables, y también que T y t no depende de p o n. (Es decir, que en el fin de interpretar la salida, no necesitamos saber cuál es el programa o entrada fue.) En este caso, no habrá universal del ordenador. La razón es que si el cálculo se detiene antes de la longitud de las modificaciones realizadas por el set-up, entonces hay una computable límite en la longitud de la computación, y si se detiene después de, a continuación, toda la información acerca de n, se ha perdido completamente, y la función debe ser constante en las entradas que conducen a esta situación. Por lo tanto, vamos a ser capaces de computably resolver la suspensión problema para las funciones implementadas por el cambio de mapa, y no puede haber ninguna computadora universal aquí.
Si uno está más relajado acerca de los requisitos de s, t y T, sin embargo, todavía se puede encontrar una computadora universal aquí. Veamos solo cambiar el requisito de que t y T no depende de p y n. En este caso, no necesitamos a todos. Vamos a interpretar "al azar", en el sentido de que todos finito subcadenas se producen en el fondo de la secuencia. Ahora, si el cálculo de p en la entrada n se detiene, a continuación, habrá una subcadena que ocurren en el fondo de la secuencia que corresponde a la codificación exactamente este cálculo, se pusieron en marcha entre los dos marcadores. Sea T el conjunto de las infinitas cadenas que entre los dos primeros marcadores en él, hay una cadena de codificación el cálculo completo de p en la entrada n. Sea t la función de mapeo de esta codificado computación para su salida. Este sistema está vivo en el sentido técnico que me dio, y la forma en que funciona es mediante el ambiente de la aleatoriedad de la secuencia de fondo que usted proporcionó para verificar que un determinado cálculo procede correctamente. Este tipo de computabilidad similar al modelo del ADN de la informática, donde cada uno tiene un vaso de precipitados lleno de ADN al azar de las moléculas que se combinan y volver a montar de acuerdo a reglas químicas. (Para el problema del viajante de comercio, imaginar que las hebras de ADN correspondiente a menos de rutas óptimas son destruidos y aquellos con más rutas óptimas se reproducen.) El cambio de mapa y salida de interpretación son como el filtro que se ordena a través del vaso de precipitados buscando la respuesta deseada.
