¿La tesis de Church-Turing también se aplica a la inteligencia artificial?

8

Según la tesis de Church-Turing, es imposible diseñar un algoritmo para decidir el problema de detención.

¿La palabra algoritmo en este contexto incluye inteligencia artificial o no, es decir, la tesis de Church-Turing también se aplica a la inteligencia artificial?

¿Es posible diseñar un sistema de inteligencia en el futuro para decidir este problema o, según la tesis de Church-Turing, ninguna IA también podrá decidir el problema de detención?

computability artificial-intelligence halting-problem church-turing-thesis M ama D
fuente
2
Es poco probable que un sistema de IA pueda decidir algo (en el sentido formal y determinista), pero si pudiera violaría la tesis de Church-Turing o la indecidibilidad del problema de Detención. (El último si está escribiendo en un lenguaje completo de Turing, el primero de lo contrario.)
Raphael
¿Por qué crees que es posible que la Tesis de Charch-Turing no cubra (o preocupe) la inteligencia artificial?
babou
@babou porque incluye no determinismo, aprendizaje, etc. Hay problemas no solucionables que AI nos da una muy buena aproximación de la solución.
M ama D
44
@Drupalist: pero la capacidad de decisión de algún problema solo significa que existe un algoritmo tal que para cualquier entrada dada desde el espacio de entrada del problema, se producirá la salida correcta. Entonces, sí, un algoritmo de IA (o cualquier otro algoritmo) podría dar buenas aproximaciones para el problema de detención, pero esto no implicará una capacidad de decisión.
Roy O.

Respuestas:

18

La tesis de Church-Turing dice que la noción informal de un algoritmo como secuencia de instrucciones coincide con las máquinas de Turing. De manera equivalente, dice que cualquier modelo razonable de computación tiene el mismo poder que las máquinas de Turing.

Una inteligencia artificial es un programa de computadora, es decir, un algoritmo. Si la tesis de Church-Turing es válida, entonces podría implementar ese algoritmo en una máquina de Turing. Como las máquinas de Turing no pueden decidir su propio problema de detención, se deduce que, según la tesis de Church-Turing, las inteligencias artificiales no pueden decidir el problema de detención de las máquinas de Turing.

David Richerby
fuente
Por otro lado, si la IA se escribió en algún tipo de computadora analógica o circuito infinito no uniforme, entonces el problema de detención para las máquinas de Turing está de vuelta en el tablero.
DanielV
3
@DanielV Un circuito infinito no uniforme no ayuda. Si tiene una descripción computable, no puede resolver el problema de detención; Si no tiene una descripción computable, no puede construirla.
David Richerby
No se puede construir con una máquina de Turing. Eso no significa que no significa que su existencia sea más paradójica que 2 puntos que están separados por una distancia arbitraria.
DanielV
2
@DanielV ¿Cómo va a decirle a su electricista qué puertas poner en el norte¿Circuito si no hay una descripción computable?
David Richerby
1
@DanielV Hay algunos problemas que simplemente no puede calcular. Debe poder decidir cuándo ha resuelto el problema, así como cuál es la respuesta. En el caso del problema de detención, no hay forma de determinar que ha resuelto el problema, y ​​mucho menos averiguar cuál es la respuesta.
Más claro el