The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
248 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.

asked in Theory of Computation by Veteran (59.7k points) | 248 views
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

 

Please log in or register to answer this question.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,384 questions
49,872 answers
164,905 comments
65,881 users