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

37,996 questions
45,492 answers
131,517 comments
48,590 users