1,645 views
6 votes
6 votes

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.

1 Answer

4 votes
4 votes

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

Related questions

28 votes
28 votes
4 answers
1
Kathleen asked Sep 23, 2014
4,044 views
Given that $A$ is regular and $(A \cup B)$ is regular, does it follow that $B$ is necessarily regular? Justify your answer.Given two finite automata $M1, M2$, outline an ...
3 votes
3 votes
3 answers
3
go_editor asked Feb 8, 2018
1,796 views
Consider the set of relationsEMP (Employee-no. Dept-no, Employee-name, Salary)DEPT (Dept-no. Dept-name, Location)Write an SQL query to:Calculate, for each department numb...
27 votes
27 votes
2 answers
4
Arjun asked Dec 17, 2016
3,084 views
Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.