Saludos Dijkstra escribió que incluso unas pocas líneas de código aparentemente simple podrían ser irremediablemente ambiguas. En al menos un trabajo, que no puedo encontrar ahora para salvar mi vida, dio un pequeño programa de ejemplo para demostrar esta ambigüedad. ¿Alguien puede señalarme un artículo suyo donde incluya uno de estos ejemplos?
Lee esto:
http://en.wikipedia.org/wiki/Halting_problem#Recognizing_partial_solutions
http://www.cs.ucsb.edu/~pconrad/cs40/08S/notes/ tiene buena cobertura; buscar "problema de detención"
Hay varias formas de la contradicción de detención esencial.
def halts( code_block ):
# Some magical code
def whistler():
while halts(whistler):
sys.whistle( 1 )
¿El "silbador" silba cero, una vez o un número infinito de veces?
Si la halts()función determina que la función whistlerparece detenerse, la función whistlerno puede detenerse.
Si la halts()función determina que la función whistlerno parece detenerse, la función se whistlerdetiene.
Por lo tanto, la halts()función no puede existir.
FILE_NOT_FOUND;)¿Estás seguro de que el papel fue de Dijkstra? Reflections on Trusting Trust de Ken Thompson parece que podría ser lo que estabas pensando. Demuestra cómo los programas absolutamente simples, directos y correctos podrían terminar haciendo algo absolutamente inesperado que no es visible en absoluto en la fuente. Incluso si no es lo que estaba pensando, es un documento que vale la pena leer.
Yendo en una dirección diferente, si quieres excelentes ejemplos de programas cortos con un comportamiento sorprendente, el concurso de C es genial. Por ejemplo, mire al ganador de 2008 . El desafío consistía en escribir un programa de línea de comando para dejar en blanco parte de una imagen, de tal manera que la imagen se borrara visualmente a la perfección, pero el archivo retiene cierta información sobre la parte eliminada de la imagen. Y de tal manera que su código pueda pasar la revisión del código. (Puede elegir el formato en el que se almacena la imagen).
fuente