Computability Theory

3 Programs and Machines

In this chapter, we focus on another way of formalizing the concept of effective cal-

culability, namely register-machine programs. Our first goal is to show that all general

recursive partial functions are also computable by register machines. This fact will

allow us to apply our work in Chapter 2 to see that a great many everyday functions

are register-machine computable. Using this, we will be able to construct a universal

program, that is, a program to compute the partial function 8(w, x) = the result of

applying the program coded by w to the input x.

3.1 Register Machines

Recall from Chapter 1 that a register-machine program is a finite sequence of instruc-

tions of the following types:

l

“Increment r,” I r (where r is a numeral ...