Resumen: Según el teorema de Rice, todo es imposible. ¡Y sin embargo, hago cosas supuestamente imposibles todo el tiempo!
Por supuesto, el teorema de Rice no dice simplemente "todo es imposible". Dice algo más específico: "Cada propiedad de un programa de computadora no es computable".
(Si desea dividir pelos, cada propiedad "no trivial". Es decir, propiedades que todos los programas posses o no hay programas poseen son trivialmente computable. Pero cualquier otra propiedad no es computable.)
Eso es lo que dice el teorema, o parece decir. Y presumiblemente un gran número de personas muy inteligentes han verificado cuidadosamente la exactitud de este teorema. ¡Pero parece desafiar completamente la lógica! ¡Existen numerosas propiedades de los programas que son triviales para calcular! Por ejemplo:
¿Cuántos pasos ejecuta un programa antes de detenerse? Decidir si este número es finito o infinito es precisamente el problema de detención, que no es computable. ¡Decidir si este número es mayor o menor que algunos finitos es trivial! Simplemente ejecute el programa por hasta pasos y vea si se detiene o no. ¡Fácil!
Del mismo modo, ¿utiliza el programa más o menos de unidades de memoria en sus primeros pasos de ejecución? Trivialmente computable.
¿El texto del programa menciona una variable llamada ? Un análisis textual trivial revelará la respuesta.
¿El programa invoca el comando ? Nuevamente, escanee el texto del programa buscando ese nombre de comando.
Veo un montón de propiedades que lo hacen parecer no computables así; por ejemplo, ¿cuántas adiciones realiza una ejecución completa del programa? Bueno, eso es casi lo mismo que preguntar cuántos pasos realiza el programa, que es prácticamente el problema de detención. Pero parece que hay un montón de propiedades de programas que son realmente fáciles de calcular. Y, sin embargo, el teorema de Rice insiste en que ninguno de ellos es computable.
¿Que me estoy perdiendo aqui?
fuente
Respuestas:
Para los propósitos de esta discusión, un "programa" es un fragmento de código que siempre toma un número entero como entrada y se ejecuta para siempre o devuelve un número entero. Decimos que dos programas y g son extensionalmente iguales si calculan la misma función, es decir, para cada número n , tanto f ( n ) como g ( n ) se ejecutan para siempre, o ambos terminan y generan el mismo número.f g n f(n) g(n)
Una propiedad extensional de los programas es una propiedad que respeta la igualdad extensional, es decir, si f y g son extensionalmente iguales, entonces ambos tienen la propiedad P o ambos no la tienen.P f g P
Aquí hay algunos ejemplos de propiedades no extensivas:
k
. (Podemos cambiar el nombre de las variables).Estoy seguro de que ha notado que enumeré precisamente sus supuestos contraejemplos al teorema de Rice, que dice:
Hay otra forma de explicar esto: debe distinguir entre un programa y la función que calcula. Muchos programas diferentes calculan la misma función (todos son extensionalmente iguales). El teorema de Rice trata sobre las propiedades de las funciones, no sobre las propiedades de los programas que las computan.
fuente
Malentendido fundamental:
El teorema de Rice trata las propiedades semánticas (propiedades de la función calculada por un programa, por ejemplo, dominio o rango de valores). A lo que se refiere son propiedades sintácticas (propiedades del programa , como el tiempo de ejecución o cuántas variables se utilizan).
Parece que no se sabe mucho por las propiedades sintácticas; ver a esta pregunta .
fuente