The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
328 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) THEN not (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 (52k points) | 328 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

 

1 Answer

+1 vote

(a). FUNNY(f) takes as input a function $f$. Now we have a function HALTS which tells us whether $f$ halts or not. i.e., if HALTS returns TRUE $f$ halts and if HALTS returns FALSE $f$ won't halt. 

So, in FUNNY, we can call HALT(f) and if the return value is

  1. TRUE, then we call function $f$ and return its negated value. 
  2. FALSE, then we just return TRUE

Since, HALT function exist and is guaranteed to return for any input function and since we are calling $f$ only when it is known to terminate, FUNNY(f) will terminate for any input function $f.$

(b). We can use FUNNY(f) to determine is a function $f$ does not terminate (non-halting problem) which is a known undecidable (not even semi-decidable) problem. 

answered by Veteran (407k points)
0

I am not getting this part of the question

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

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
49,530 questions
54,139 answers
187,354 comments
71,068 users