Sentido común de inteligencia artificial - Ciencia - Computabilidad de las máquinas de Turing
¿Todos los problemas matemáticos se pueden resolver con ordenadores?
Como se demostró en el artículo anterior "Busy Beaver", ¿podría el castor quedarse atrapado en un bucle infinito y no poder detenerse? Este problema matemático aparentemente simple no puede resolverse completamente con una computadora o no es computable.
La computabilidad se refiere a si un problema matemático puede ser resuelto por una computadora en un número limitado de pasos.
En primer lugar, tiene que ser un problema matemático, no un problema tipo "hazme una hamburguesa" que requiera cambios físicos reales.
En segundo lugar, debe ser un paso finito, y si el algoritmo para el problema está mucho más allá de la potencia de cálculo que las computadoras pueden tener actualmente, entonces también debería considerarse incomputable.
La computabilidad de los problemas de investigación evita perder el tiempo luchando involuntariamente en un pozo sin fondo.
La computabilidad es para problemas específicos, y hay dos tipos principales de problemas:
También hay problemas de búsqueda (¿se puede encontrar una estructura coincidente x en el objeto Y) y problema de optimización ( se pueden encontrar múltiples soluciones). (Cuál de múltiples soluciones es mejor).
Una máquina de Turing es un modelo informático abstracto que teóricamente puede implementar un número infinito de algoritmos. Existen varios otros modelos informáticos similares (modelos de funciones) que se consideran equivalentes de Turing o propiedades de Turing completas. >
Como se muestra arriba, la teoría de la recursión se originó en la década de 1930, por Kurt Gödel, Alonzo Church, Rozsa - Propuesta por Rózsa Péter, Alan Turing, Stephen Kleene y Emil Post.
Ya en 1936, Church y Turing se inspiraron en el teorema de incompletitud de Gödel, es decir, es imposible que un programa algorítmico juzgue correctamente la autenticidad de cualquier problema matemático. Esta teoría llegó a ser conocida como teorema de Church-Turing y definió el significado del concepto de computabilidad: cualquier función que pueda calcularse algorítmicamente es una función computable.
La introducción de la computabilidad también significa que los científicos han reconocido problemas incomputables, lo que demuestra que efectivamente hay problemas en matemáticas que no se pueden resolver de manera eficiente.
También existen computabilidad relativa y grados de Turing que describen el grado de computabilidad.