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 (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: G G "Increment r," I r (where r is a numeral for a natural number): The effect of this instruc- tion is to increase the contents of register r by 1. The machine then proceeds to the next instruction in the program (if any). "Decrement r," D r (where r is a numeral for a natural number): The effect of this instruction