Indecidible
Acabo de demostrar que si tenemos un algoritmo - con ciertas características-, entonces es imposible saber de antemano si se puede obtener una explicación de su respuesta en tiempo finito o no; incluso si el algoritmo en sí siempre termina.
No quiero entrar mucho en detalles, pero quiero hablar un poco de la forma en que lo demostré porque me pareció un método interesante y que no había visto antes - aunque definitivamente no es una idea revolucionaria ni mucho menos.
Primero demostré que es imposible decidir si el algoritmo original termina o no. Esto fue relativamente fácil, demostrando que puedo simular una Máquina de Turing con algoritmos que tienen las características que yo requiero. Perfecto, pero eso no me sirve para demostrar que, aún si el algoritmo termina, no puedo saber si su explicación también lo hace.
Entonces ideé una transformación. Es simplemente una función que transforma un algoritmo A en otro f(A), tal que f(A) siempre termina. Pero lo interesante del caso es que ¡la explicación de f(A) se comporta idéntica a A! A termina si y sólo si la explicación de f(A) termina.
Como no puedo saber si A termina, entonces tampoco puedo saber si la explicación de f(A) termina. Pero f(A) siempre termina. Por lo tanto, el hecho de que un algoritmo termine no me da información suficiente para decidir si sus explicaciones lo hacen también.
Uf. Me mareé de explicarlo.
3 comentarios:
Could you give us more details about this function f??
No mames, fuera de broma, me quedó bastante claro y si, me gustó, aunque como bruno, qué más puedes decir de f?
Un abrazo
Es difícil hablar de f sin meterme en detalles, pero lo intentaré.
La idea principal es generar un algoritmo que pueda generar el mismo resultado de dos formas distintas. Así, cuando se ejecuta, sólo lo genera una vez, pero si quieres explicar el resultado tienes que usar las dos formas (dar las dos explicaciones).
Y ahí viene el punto importante, puedo poner una regla que genera algo nuevo _únicamente si el resultado ya se generó dos veces_.
Si combino eso, con el input de la máquina A, obtengo lo que llamé f(A), que siempre termina cuando no quiero explicaciones (simplemente genera el resultado en un paso), pero si quiero explicar, usa dos pasos para generar el resultado por duplicado, y luego genera el input de A, permitiéndole después ejecutar A, dentro de la explicación.
Lo sé, un poco confuso, pero espero se entienda al menos un poco.
Saludos!
Publicar un comentario