Q10

MCQMarks unknown

Suppose we have a function HALTS which when applied to any arbitrary function $f$ and its arguments will say TRUE if function $f$ terminates for those arguments and FALSE otherwise. Example: Given the following function definition. FACTORIAL (N) = IF (N=0) THEN 1 ELSE N*FACTORIAL (N-1) Then HALTS (FACTORIAL, 4) = TRUE and HALTS (FACTORIAL, -5) = FALSE Let us define the function FUNNY (f) = IF HALTS (f) THEN not (f) ELSE TRUE

(A)

Show that FUNNY terminates for all functions $f$ .

(B)

use (a) to prove (by contradiction) that it is not possible to have a function like HALTS which for arbitrary functions and inputs says whether it will terminate on that input or not.

Loading…