¿PROBLEMA DE DETENER DETENER VS. TEOREMA AUTOMÁTICO QUE PROBA?
https://cs.stackexchange.com/questions/127161
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
En la teoría del tutorial de computación ofrecido por el árbol de complejidad (acabo de comenzar el segundo video), habla sobre cómo se desarrolló el problema de detención para demostrar que las matemáticas no pudieron ser automatizadas.Últimamente, he escuchado un poco sobre el teorema automático / automático que demuestra: algunas personas incluso están postulando que algunos matemáticos del día serán reemplazados por máquinas.Mi pregunta es: ¿Necesitamos encontrar un fallo en el razonamiento del problema de detener para demostrar que las matemáticas pueden ser automatizadas?(O es el problema de detención, en la edad del aprendizaje automático, reducido a una buena descripción histórica del pasado ...)
Solución
La noción de automatización de matemáticas es una vaga, y eso es la responsabilidad de la discrepancia aquí.
Una interpretación sería: para automatizar las matemáticas sería producir una máquina $ m $ que podría decir si una oración dada es verdadera (o, más débilmente débilmente , demostrable a partir de algunos axiomas acordados como $ \ mathsf {zfc} $ ). Incluso la versión más débil se descarta por la incomputabilidad del problema de detención.
Otra interpretación es: para automatizar las matemáticas es producir una máquina $ m $ que encontrará pruebas de todas las demostrables (de nuevo, desde el conjunto de axiomas acordado ) oraciones. Tenga en cuenta que $ m $ es no se requiere para determinar si una oración es demostrable en primer lugar, simplemente para encontrar una prueba si Dicha prueba existe en absoluto . Este es posible a través de la búsqueda de fuerza bruta.
Por supuesto que el segundo tipo de automatización es altamente inviable - en general, Tomará ridículamente largo para encontrar pruebas de teoremas . Pero eso no afecta a su posibilidad en principio. Este es realmente el punto de partida de la demostración del teorema automatizado: la búsqueda trivialmente a prueba de la fuerza bruta es posible y, trivialmente, es horrible en general, podemos encontrar estrategias de búsqueda de pruebas inteligentes en algunos casos de Interés ? (Y aquí es donde la teoría de la complejidad entra en la imagen.)
Otros consejos
Está combando dos significados posibles de la frase "Las matemáticas pueden ser automatizadas":
- ", cualquier teorema puede ser probado verdadero o falso por un algoritmo"
- "La actividad práctica de probar los teoremas, como lo realiza actualmente los humanos, puede ser realizado por las computadoras de una manera económicamente viable"
Debido al problema de detención, es imposible que cualquier algoritmo pueda demostrar o refutar todos los teoremas. ¡Pero esto se aplica tan bien a los humanos en cuanto a las computadoras!
No es necesario que haya un defecto en la prueba de la indecisión del problema de detención para (teóricamente), el trabajo de los matemáticos humanos se vuelva obsoleta. Una máquina no tiene que ser capaz de resolver problemas indecibles para eliminar la función de trabajo de los matemáticos humanos, solo tiene que ser capaz de probar los teoremas de interés de manera más eficiente de lo que los humanos pueden . Esta es una no cuestión de computabilidad o complejidad computacional asintótica pero de economía.
No hay razón para pensar que los cerebros humanos son únicos superiores al demostrar los teoremas matemáticos. Además, debido a la paradoja de Moravec , debemos esperar que Las computadoras pueden ser mejores para demostrar teoremas que los humanos. Un cerebro humano es un saco de carne cuya historia evolutiva incluye prácticamente ninguna recompensa de fitness para el fenotipo de "puede resultar difíciles de los teoremas". Así que esperaríamos que podamos ver una computadora que sea superinteligente en el área de demostrar teoría antes de lo que esperaríamos ver una computadora que sea superinteligente en el área de, digamos, cazando Megafauna.
creo que esta pregunta debería darte la respuesta.
En resumen, si P= NP, entonces, una computadora puede ser probada alguna conjetura con una prueba de longitud razonable.
