[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 free

Explore the full course: Zero To Hero

Loading lesson…