Computability Theory

76 Computability Theory

This program leaves the output in register 0, with register 1 empty. Call it SUB1 from

1 to 0. If applied to the empty word, the output is also empty.

Theorem: Every n-place general recursive partial function f is register-machine com-

putable in the following sense. There is a program P such that if we start a register

machine with the triadic numerals for x

1

, . . . , x

n

in registers 1, . . . , n and λ in the

other registers and we apply program P, then the following conditions hold:

l

If f (x

1

, . . . , x

n

) is defined, then the computation eventually terminates with the tri-

adic numeral for f (x

1

, . . . , x

n

) in register 0.