[5 marks] Suppose a function HALTS, when applied to an arbitrary function f…
PYQ GATE 1999
[5 marks] Suppose a function HALTS, when applied to an arbitrary function f and its arguments, returns TRUE if f terminates on those arguments and FALSE otherwise. For example, given the function
FACTORIAL(N) = IF (N = 0) THEN 1 ELSE N * FACTORIAL(N - 1)HALTS(FACTORIAL 4) = TRUE, whereas HALTS(FACTORIAL -5) = FALSE.
Define FUNNY by
FUNNY(f) = IF HALTS(f f) THEN NOT(f f) ELSE TRUE(a) Show that FUNNY terminates for all functions f.
(b) Use (a) to prove by contradiction that no function like HALTS can decide whether an arbitrary function terminates on an arbitrary input.
Sign up free to check your answer
Sign up freeLoading lesson…

