261 views

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 f) THEN not (f f) ELSE TRUE

1. Show that FUNNY terminates for all functions $f$.

2. 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.

0

GIVEN 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

and FUNNY (f) = IF HALTS (f f) THEN not (f f) ELSE TRUE

TO prove

FUNNY (f) = IF HALTS (f f) THEN not (f f) ELSE TRUE   always terminate

proof

halt give two output true and false only one of them

case1 let take first halt(ff) false and put in the given function i.e

FUNNY (f) = IF HALTS (f f) THEN not (f f) ELSE TRUE

FUNNY (f) = IF false  THEN not (f f) ELSE TRUE so this will return true

case1

let halt(ff)=true

then

FUNNY (f) = IF true THEN not (f f) ELSE TRUE   eq1

it will execute not (ff) which in turn give True (proof of this in case 1)

put this value in eq1 you will get true

so in both case it always terminate

1
2