PUERTA | PUERTA CS 1999 | Pregunta 58

[Pregunta de 5 puntos]

Supongamos que tenemos una función HALTS que cuando se aplica a cualquier función arbitraria f y sus argumentos dirá VERDADERO si la función f termina para esos argumentos y FALSO de lo contrario. Ejemplo, dada la siguiente definición de función.

FACTORIAL (N) = IF(N=0) THEN 1 ELSE N*FACTORIAL (N-1)
Then HALTS(FACTORIAL 4)= TRUE and HATS(FACTORIAL -5)=FLASE

Let us define the function FUNNY(f) = IF HALTS(ff) THEN not(ff) ELSE TRUE

una. Muestre que FUNNY termina para todas las funciones f

b. Use (a) para probar (por contradicción) que no es posible tener una función como HALTS que para funciones y entradas arbitrarias diga si terminará en esa entrada o no.

Respuesta:
Explicación:
Cuestionario de esta pregunta