Theory of Computation

2.3    URM COMPUTATIONS AND THEIR ARITHMETIZATION

We now return to the systematic development of the basic theory of partial recursive functions, with a view of gaining an insight in the inherent limitations of the computing processes. Instrumental to this study is a mathematical characterization of what is going on during a URM computation as well as a mathematical “coding”, as a primitive recursive predicate, of the statement “the URM M, when presented with input x has a terminating computation, coded by the number y” —the so-called Kleene-predicate. We achieve this “mathematization” via a process that Gödel (1931) invented in his paper on incompleteness of arithmetic, namely, arithmetization. The arithmetization of URM computations is our first task in this section. This must begin with a mathematically precise definition of “URM computation”.

As an “agent” executes some URM’s, M, instructions, it generates at each step instantaneous descriptions (IDs)—intuitively, “snapshots”—of a computation. The information each such description includes is simply the values of each variable of M, and the label (instruction number) of the instruction that is about to be executed next—the so-called current instruction.

In this section we will arithmetize URMs and their computations—just as Gödel did in the case of formal arithmetic and its proofs (loc. cit.)—and prove a cornerstone result of computability, the “normal form theorem” of Kleene that, essentially, says that the URM programming ...