¿Cuáles son los límites de la no-calificación?

Question

Es bastante fácil construir máquinas de Turing que no se detengan. Pero, ¿hasta qué punto podemos hacerlas más complejas? Por ejemplo, supongamos que una máquina tiene acceso a su tabla de transición de estados y puede escribir en ella como un programa C podría apuntar a su propia página de código en la RAM y hurgar en ella. La motivación de la pregunta debería aclarar los detalles:

Imagina que hemos construido un robot autónomo inteligente (pero determinista) que puede autorrepararse completamente del entorno. Imagina que es una sonda espacial. No queremos que se apague solo. Como puede cambiar físicamente, también puede cambiar su propia programación. No tenemos control sobre eso una vez que lanzamos la cosa. Existe la posibilidad de que sufra una serie de cambios que hagan que se detenga y se convierta en chatarra espacial.

¿Hay alguna forma de entender la topología de una "trayectoria" de automodificación para poder minimizar el riesgo de parada? Por ejemplo, tal vez haya algún tipo de "atractor" en el que la detención sea rara.

¿O simplemente tenemos que suponer que se aplica la constante Omega de Chaitin, y que hay una probabilidad constante desconocida de que la cosa se detenga?

---

Actualización: Gracias por los comentarios me hicieron tomar nuevas direcciones. Aquí hay algunos antecedentes adicionales.

• Microsoft tiene un proyecto de investigación activo a lo largo de estas líneas.

Turing demostró que, en general, probar la terminación de un programa es indecidible. Sin embargo, este resultado no excluye la existencia de herramientas de prueba de terminación de programas que funcionen el 99,9 por ciento de del tiempo en programas escritos por humanos. Este es el tipo de herramienta que pretendemos hacer. -Byron Cook, director del proyecto

• Normalmente queremos que los programas se detengan y nos den alguna salida. Pero para el ejemplo que he dado, queremos que se ejecute para siempre. ¿Podemos construir una IA que no se apague espontáneamente con una alta probabilidad, como la de Shannon? La máquina definitiva "? Suponiendo que una civilización sea efectivamente computable (un gran "si", pero es un punto de partida), ¿hay alguna manera de protegerse contra el auto-calentamiento? Peter Suber estudió esta idea, limitada a los sistemas legislativos, y creó el juego Nomic . Paul Krugman da un ejemplo de un gobierno que realmente se auto-aseguró. Mis propios pensamientos sobre esto están en este documento donde asumí que el Omega de Chaitin "gravaría" la probabilidad de supervivencia de cualquier sistema computable. Sin embargo, esto no es muy satisfactorio. Implica que no podemos hacer nada mejor que seleccionar un algoritmo al azar.

Answer 1

Tu pregunta se refiere a muchas cosas, pero permíteme dar una respuesta centrada en una sola cuestión interesante, la de determinar la duración de un programa.

El castor ocupado mide exactamente la duración de los programas de un tamaño determinado antes de detenerse (entre los que se detienen). Existen versiones de la función del castor ocupado para cualquier noción de computación, pero consideremos el caso de los programas en C, ya que los ha mencionado. Observe que para cualquier número natural $n$ hay un enorme número de programas en C de tamaño $n$ medido en kilobytes, por ejemplo. Sin embargo, este enorme número es finito. Entre todos los programas de tamaño como máximo $n$ Algunos se detienen y otros no. Definir $b(n)$ para ser el tiempo de ejecución en ciclos de reloj del programa C más largo pero pero que se detenga, de un tamaño máximo de $n$ .

Lo interesante es que la función de castor ocupado es ¡no es computable! Si tuviéramos una forma de calcular $b$ entonces podríamos resolver el problema de detención, ya que dado cualquier programa programa en C, miramos su tamaño $n$ , computa $b(n)$ y ejecutar el programa durante ese número de pasos; si no se ha detenido para entonces, sabemos que nunca se detendrá. Otra forma de decir esto es que si tenemos una caja negra de oráculo que nos permite calcular la función $b$ entonces seríamos capaces de responder a cualquier consulta del problema de detención. Como es imposible resolver el problema de detención, se deduce que no podemos calcular la función del castor ocupado.

Editar. En su actualización, menciona el problema de resolver el problema de detención el 99,99% de las veces. El problema general de resolver casi todas las instancias de un problema, a diferencia de todas las instancias de un problema, da lugar al tema conocido como complejidad del caso genérico . En concreto, el fenómeno de los agujeros negros se produce cuando la dificultad de un problema irresoluble o inviable se concentra en una región muy pequeña, fuera de la cual es fácil. No es bueno, por ejemplo, basar un esquema de encriptación en un problema cuya dificultad tiene una alta complejidad en el peor de los casos, pero cuya complejidad en el caso medio es baja, ya que si los ladrones pueden robar el banco el 10% de las veces, es suficiente para ellos.

De hecho, Alexei Miasnikov y yo demostramos que el propio problema de detención admite un agujero negro: para algunos de los modelos de computación estándar, existe un método para resolver el problema de detención con probabilidad $1$ utilizando la medida de densidad asintótica natural en el espacio de los programas. Explico más detalles en esta respuesta de MO .

Answer 2

Programación funcional total permite una considerable libertad de programación con garantía de terminación. No se obtienen bucles ilimitados, pero se puede seguir utilizando recursividad estructural .

Un ordenador de este tipo estaría conectado al mundo exterior a través de sensores. Si permitimos recursividad vigilada entonces obtenemos un buen marco para escribir algoritmos que procesen los datos y que puedan garantizar que, de vez en cuando, el robot produzca una salida, en lugar de desaparecer en sus propios pensamientos.

No sé si esto responde a tu pregunta, pero parece encajar. Una máquina de este tipo no podría hacer su propia tabla de transición de estados, pero sería capaz de "programarse a sí misma" haciendo uso de funciones de orden superior para construir nuevas funciones.