Máquina de Gödel

Una máquina Gödel es un programa informático hipotético que se mejora a sí mismo y resuelve problemas de manera óptima. Utiliza un protocolo recursivo de auto-mejora en el que reescribe su propio código cuando puede probar que el nuevo código proporciona una mejor estrategia.​​ La máquina fue inventada por Jürgen Schmidhuber (propuesta por primera vez en 2003 ​), pero lleva el nombre de Kurt Gödel, quien inspiró las teorías matemáticas.​

La máquina Gödel a menudo se discute cuando se trata de problemas de metaaprendizaje, también conocido como "aprender a aprender". Las aplicaciones incluyen la automatización de las decisiones humanos y la transferencia de conocimiento entre múltiples tareas relacionadas, y pueden conducir al diseño de arquitecturas de aprendizaje más robustas y generales.​ Aunque teóricamente posible, no se ha creado una implementación completa. ​

La máquina Gödel a menudo se compara con la AIXItl de Marcus Hutter, otra especificación formal para una inteligencia general artificial . Schmidhuber señala que la máquina Gödel podría comenzar implementando AIXItl como su subprograma inicial y auto modificarse después de encontrar pruebas de que otro algoritmo para su código de búsqueda será mejor. ​

Limitaciones

Los problemas tradicionales resueltos por una computadora solo requieren una entrada y proporcionan alguna salida. Las computadoras de este tipo tenían su algoritmo inicial "hardcodeado".​ Esto no tiene en cuenta el entorno natural dinámico y, por lo tanto, este era uno de los obstáculos que debía superar la máquina Gödel.

Sin embargo, la máquina Gödel tiene sus propias limitaciones. Cualquier sistema formal que abarque la aritmética es defectuoso o permite enunciados que no se pueden probar en el sistema pero se pueden probar en otro sistema: véase, por ejemplo, el teorema de Goodstein. ​ Por lo tanto, incluso una máquina Gödel con recursos computacionales ilimitados debe ignorar esas auto-mejoras cuya efectividad no puede probar.

Variables de interes

Hay tres variables que son particularmente útiles en el tiempo de ejecución de la máquina Gödel. ​

• En algún momento $t$, La variable ${\text{time}}$ tendrá el equivalente binario de $t$. Esto se incrementa de manera constante durante todo el tiempo de ejecución de la máquina.

• Cualquier entrada destinada a la máquina Gödel desde el entorno natural se almacena en variable $x$. Es probable el caso de que $x$ mantenga diferentes valores para diferentes valores de variable ${\text{time}}$ .

• Las salidas de la máquina Gödel se almacenan en variables $y$, dónde $y(t)$ sería la cadena de bits de salida en algún momento $t$ .

En cualquier momento dado $t$, dónde $(1\leq t\leq T)$, el objetivo es maximizar el éxito futuro o la utilidad. Una función de utilidad típica sigue el patrón $u(s,\mathrm {Env} ):S\times E\rightarrow \mathbb {R}$ :

$u(s,\mathrm {Env} )=E_{\mu }{\Bigg [}\sum _{\tau ={\text{time}}}^{T}r(\tau )\mid s,\mathrm {Env} {\Bigg ]}$

dónde $r(t)$ es una entrada de recompensa de valor real (codificada dentro de $s(t)$ ) en el momento $t$, $E_{\mu }[\cdot \mid \cdot ]$ denota el operador de expectativa condicional con respecto a alguna distribución posiblemente desconocida $\mu$ de un conjunto $M$ de posibles distribuciones ($M$ refleja todo lo que se sabe sobre las posibles reacciones probabilísticas del entorno) y lo mencionado anteriormente ${\text{time}}=\operatorname {time} (s)$ es una función del estado $s$ que identifica de forma exclusiva el ciclo actual. Note que tenemos en cuenta la posibilidad de extender la vida útil esperada a través de acciones apropiadas .

Instrucciones utilizadas por técnicas de prueba

La naturaleza de las seis instrucciones de modificación de la prueba a continuación hace que sea imposible insertar un teorema incorrecto en la prueba, lo que trivializa la verificación de la prueba. ​

get-axiom (n)

Añade la n-ésima axioma como un teorema a la secuencia del teorema actual. A continuación se muestra el esquema de axioma inicial:

• Los axiomas de hardware especifican formalmente cómo los componentes de la máquina podrían cambiar de un ciclo a otro.
• Los Axiomas de Recompensa definen el costo computacional de la instrucción de hardware y el costo físico de las acciones de salida. Los Axiomas relacionados también definen la vida útil de la máquina Gödel como cantidades escalares que representan todas las recompensas/costos.
• Los axiomas del entorno restringen la forma en que se producen nuevas entradas x a partir del entorno, en base a secuencias anteriores de entradas y.
• Axiomas de incertidumbre/manipulación de cadenas Los axiomas son axiomas estándar para la aritmética, el cálculo, la teoría de probabilidad y la manipulación de cadenas que permiten la construcción de pruebas relacionadas con valores variables futuros dentro de la máquina Gödel.
• Los Axiomas de estado inicial contienen información sobre cómo reconstruir partes o todo el estado inicial.
• Los axiomas de utilidad describen el objetivo general en forma de función de utilidad u .

appy-rule(k, m, n)

Toma el índice k de una regla de inferencia (como modus tollens, modus ponens ), e intenta aplicarlo a los dos teoremas previamente probados m y n. El teorema resultante se agrega a la prueba.

delete-theorem(m)

Elimina el teorema almacenado en el índice m en la prueba actual. Esto ayuda a mitigar las restricciones de almacenamiento causadas por teoremas redundantes e innecesarios. Los teoremas eliminados ya no pueden ser referenciados por la función de apply-rule.

set-switchprog(m, n)

Reemplaza switchprog S ^p _m:n, siempre que sea una subcadena no vacía de S^p .

check()

Verifica si se ha alcanzado el objetivo de la búsqueda de pruebas. Un teorema objetivo establece que, dada la función de utilidad axiomatizada actual u (Elemento 1f), la utilidad de un cambio de p al switchprog actual sería mayor que la utilidad de continuar la ejecución de p (que seguiría buscando switchprog alternativos).​ Esto se demuestra en la siguiente descripción de la función decodificada check() para la máquina Gödel:

$D_{KA}={\frac {d_{\text{pore}}}{3}}u={\frac {d_{\text{pore}}}{3}}{\sqrt {\frac {8\kappa NT}{\pi M_{A}}}}$

state2theorem(m, n )

Toma dos argumentos, m y n y los intentos de convertir el contenido de S_{m: n} en un teorema.

Aplicaciones de ejemplo

Optimización NP-hard por tiempo limitado

La entrada inicial a la máquina Gödel es la representación de un grafo conectado con una gran cantidad de nodos unidos por aristas de varias longitudes. Dentro de un tiempo T dado, debería encontrar una ruta cíclica que conecte todos los nodos. La única recompensa de valor real ocurrirá en el momento T. Es igual a 1dividido por la longitud del mejor camino encontrado hasta ahora (0 si no se encontró ninguno). No hay otras entradas. El subproducto de maximizar la recompensa esperada es encontrar el camino más corto que se pueda encontrar dentro del tiempo limitado, dado el sesgo inicial. ​

Prueba rápida de teoremas

Probar o refutar lo más rápido posible que todos los enteros pares> 2 son la suma de dos números primos (conjetura de Goldbach). La recompensa es 1/t, donde t es el tiempo requerido para producir y verificar la primera prueba de este tipo. ​

Maximización de la recompensa esperada con recursos limitados

Un robot cognitivo que necesita al menos 1 litro de gasolina por hora interactúa con un entorno parcialmente desconocido, tratando de encontrar depósitos de gasolina ocultos y limitados para reabastecer ocasionalmente su tanque. Es recompensado en proporción a su vida útil y muere después de como máximo 100 años o tan pronto como su tanque esté vacío o se caiga de un acantilado, y así sucesivamente. Las reacciones ambientales probabilísticas son inicialmente desconocidas pero se supone que las reacciones ambientales difíciles de calcular son improbables. Esto permite una estrategia computable para hacer predicciones casi óptimas. Un subproducto de maximizar la recompensa esperada es maximizar la vida útil esperada.​

Ver también

• Teoremas de incompletitud de Gödel

Enlaces externos

• Página de inicio de máquinas Goedel
• Máquinas Goedel: solucionadores de problemas universales autorreferenciales que hacen mejoras automáticas demostrablemente óptimas