The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
208 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 (69k points) | 208 views

Please log in or register to answer this question.



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

33,687 questions
40,230 answers
114,266 comments
38,783 users