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* (*ID*s)—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 ...

Start Free Trial

No credit card required