Computability Theory

22 Computability Theory

program always halts, no matter what. But it is easy to make a while program that

never halts.

We say that a k-place partial function f on N is while-computable if there exists

a while program P that, whenever started with a k-tuple Ex assigned to the variables

X

1

, . . . , X

k

and 0 assigned to the other variables, behaves as follows:

l

If f (Ex) is defined, then the program eventually halts, with X

0

assigned the value f (Ex).

l

If f (Ex) is undefined, then the program never halts.

The loop-computable functions are defined in the analogous way. But there is the

difference that any loop-computable function is total.

Theorem:

(a) A function ...