Bueno, no podemos estar seguros de ninguna manera …
Ver: problema de detención
El problema de detención es un problema de decisión sobre las propiedades de los programas de computadora en un modelo fijo de cómputo de Turing completo, es decir, todos los programas que se pueden escribir en algún lenguaje de programación dado que sea lo suficientemente general como para ser equivalente a una máquina de Turing. El problema es determinar, dado un programa y una entrada al programa, si el programa finalmente se detendrá cuando se ejecute con esa entrada. En este marco abstracto, no hay limitaciones de recursos en la cantidad de memoria o tiempo requerido para la ejecución del programa; puede tomar mucho tiempo y usar arbitrariamente mucho espacio de almacenamiento antes de detenerse. La pregunta es simplemente si el programa dado alguna vez se detendrá en una entrada particular.
- ¿Cómo dibuja una línea en la pantalla un programa de gráficos por computadora? Del código de alto nivel al nivel de la tarjeta gráfica, ¿qué sucede?
- Cómo saber si debo optar por CSE en pregrado después de la clase 12
- ¿Qué tiene el programa de Sistemas Simbólicos en Stanford que produce tan increíbles alums?
- ¿Es la informática fotónica el futuro?
- Si pudieras formar un equipo ideal para diseñar, implementar y mantener un sistema operativo distribuido comercial, ¿quién estaría en él y con qué título?
Por ejemplo, en pseudocódigo, el programa:
mientras (verdadero) continúe
no se detiene; más bien, continúa para siempre en un bucle infinito. Por otro lado, el programa
imprimir “¡Hola, mundo!”
se detiene
Si bien decidir si estos programas se detienen es simple, los programas más complejos resultan problemáticos.
Un enfoque para el problema podría ser ejecutar el programa durante un cierto número de pasos y verificar si se detiene. Pero si el programa no se detiene, se desconoce si el programa finalmente se detendrá o se ejecutará para siempre.
Turing demostró que no puede existir un algoritmo que siempre decida correctamente si, para un programa arbitrario dado y su entrada, el programa se detiene cuando se ejecuta con esa entrada; La esencia de la prueba de Turing es que cualquier algoritmo de este tipo puede contradecirse y, por lo tanto, no puede ser correcto.
