the development of computability theory in (Martin Davis, Ron Sigal, Elaine J. Weyuker, 1994) is based on a specific programming language
. we will use certain letters as variables whose values are numbers. (in this context the word number will always mean nonnegative integers, unless the contrary is specifically stated.) in particular, the symbols
are called input variables of
. the symbol
will be called the output variable of
and the symbols
are called the local variables of
. the subscript 1 is often omitted; i.e.,
stands for
and
for
. unlike the programming languages in actual use, there is no upper limit on the values these variables can assume. thus from the outset,
must be regarded as a purely theoretical entity. nevertheless, readers having programming experience will find working with
very easy.
in
we will be able to write "instructions" of various sorts; a "program" of
will then consist of a list (i.e., a finite sequence) of instructions. for example, for each variable
there will be an instruction:
a simple example of a program of
is
"execution" of this program has the effect of increasing the value of
by 2. in addition to variables, we will need "labels." in
the symbols
are called labels of
, once again the subscript 1 can be omitted. a statement is one of the following:
where
may be any variable and
may be any label
we will use the special convention that the output variable
and the local variables
, initially have the value 0. we will sometimes indicate the value of a variable by writing it in lowercase italics. thus
is the value of
.
instructions may or may not have labels. when an instruction is labeled, the label is written to its left in square brackets. for example,
an instruction is either a statement (in which case it is also called an unlabeled instruction) or
followed by a statement (in which case the instruction is said to have
as its label or to be labeled
). a program is a list (i.e., a finite sequence) of instructions. the length of this list is called the length of the program. it is useful to include the empty program of length 0, which of course contains no instructions.
a program that computes the function
.
let
be any program in the language
and let
be
given numbers. we form the state
of
which consists of the equations
together with the equations
for each variable
in
other than
. we will call this the initial state, and the snapshot
, the initial snapshot.
- blk-S-program-exec-case-1case 1. there is a computation
of
beginning with the initial snapshot. then we write
for the value of the variable
at the (terminal) snapshot
.
- blk-S-program-exec-case-2case 2. there is no such computation; i.e. there is an infinite sequence
beginning with the initial snapshot where each
is the successor of
. in this case
is undefined.
for any program
and any positive integer
, the function
is said to be computed by
. a given partial function
(of one or more variables) is said to be partially computable if it is computed by some program. that is,
is partially computable if there is a program
such that
for all
. here this equation must be understood to mean not only that both sides have the same value when they are defined, but also that when either side of the equation is undefined, the other is also.
a given function g of m variables is called total if
is defined for all
. a function is said to be computable if it is both partially computable and total.
partially computable functions are also called partial recursive, and computable functions, i.e., functions that are both total and partial recursive, are called recursive. the reason for this terminology is largely historical.
although the program fig-s-lang-1 is a perfectly well-defined program of our languahe
. we may think of it as having arisen in an attempt to write a program that copies the value of
into
. and therefore containing a "bug" because it does not handle 0 correctly. the following slightly more complicated example remedies this situation.
as we can easily convince ourselves, this program does copy the value of
into
for all initial values of
. thus, we say that it computes the function
. at first glance.
's role in the computation may not be obvious. it is used simply to allow us to code an unconditional branch. that is, the program segment
has the effect (ignoring the effect on the value of
) of an instruction
such as is available in most programming languages. to see that this is true we note that the first instruction of the segment guarantees that
has a nonzero value. thus the condition
is always true and hence the next instruction performed will be the instruction labeled
. now
is not an instruction in our language
, but since we will frequently have use for such an instruction, we can use it as an abbreviation for the program segment fig-s-lang-3. such an abbreviating pseudoinstruction will be called a macro and the program or program segment which it abbreviates will be called its macro expansion.
note that although the program of fig-s-lang-2 does copy the value of
into
, in the process the value of
is "destroyed" and the program terminates with
having the value 0. of course, typically, programmers want to be able to copy the value of one variable into another without the original being "zeroed out." this is accomplished in the next program. (note that we use our macro instruction
several times to shorten the program. of course, if challenged, we could produce a legal program of
by replacing each
by a macro expansion. these macro expansions would have to use a local variable other than
so as not to interfere with the value of
in the main program.)
in the first loop, this program copies the value of
into both
and
, while in the second loop, the value of
is restored. when the program terminates, both
and
contain
's original value and
.
we wish to use this program to justify the introduction of a macro which we will write
the execution of which will replace the contents of the variable
by the contents of the variable
while leaving the contents of
unaltered. now, this program fig-s-lang-4 functions correctly as a copying program only under our assumption that the variables
and
are initialized to the value 0. thus, we can use the program as the basis of a macro expansion of
only if we can arrange matters so as to be sure that the corresponding variables have the value 0 whenever the macro expansion is entered. to solve this problem we introduce the macro
which will have the effect of setting the contents of
equal to 0. the corresponding macro expansion is simply
where, of course, the label
is to be chosen to be different from any of the labels in the main program. we can now write the macro expansion of
by letting the macro
precede the program which results when
is replaced by
and
is replaced by
in program fig-s-lang-4. the result is as follows:
a program with two inputs that computes the function
is as follows:
again, if challenged we would supply macro expansions for "
" and "
" as well as for the two unconditional branches. note that
is used to preserve the value of
.
we now present a program that multiplies, i.e. that computes
. since multiplication can be regarded as repeated addition, we are led to the "program"
of course, the "instruction"
is not permitted in the language
. what we have in mind is that since we already have an addition program, we can replace the macro
by a program for computing it, which we will call its macro expansion. at first glance, one might wonder why the pair of instructions
was used in this program rather than the single instruction
since we simply want to replace the current value of
by the sum of its value and
. the sum program in fig-s-lang-5 computes
. if we were to use that as a template, we would have to replace
in the program by
. now if we tried to use
also as the variable being assigned, the macro expansion would be as follows:
what does this program actually compute? it should not be difficult to see that instead of computing
as desired, this program computes
. since
is to be added over and over again, it is important that Xx not be destroyed by the addition program. Here is the multiplication program, showing the macro expansion of
:
we associate with each program
of the language
a number, which we write
, in such a way that the program can be retrieved from its number. to begin we arrange the variables in order as follows:
next we do the same for the labels:
we write
for the position of a given variable or label in the appropriate ordering. thus
.
now let
be an instruction (labeled or unlabeled) of the language
. then we write
where
- if
is unlabeled, then
; if
is labeled
, then
;
- if the variable
is mentioned in
, then
;
- if the statement in
is
then or 1 or 2, respectively; - if the statement in
is
then .
some examples:
the number of the unlabeled instruction
is
whereas the number of the instruction
is
note that for any given number
there is a unique instruction
with
. we first calculate
. if
,
is unlabeled; otherwise
has the
th label in our list. to find the variable mentioned in
, we compute
and locate the
th variable
in our list. then, the statement in
will be
and
is the
th label in our list.
finally, let a program
consist of the instructions
. then we set
since godel numbers tend to be very large, the numbers of even rather simple programs usually will be quite enormous. we content ourselves with a simple example:
calling these instructions
and
, respectively, we have seen that
. since
is unlabeled,
thus, finally, the number of this short program is
note that the number of the unlabeled instruction
is
thus, by the ambiguity in Gödel numbers, the number of a program will be unchanged if an unlabeled
is tacked onto its end. of course this is a harmless ambiguity; the longer program computes exactly what the shorter one does. however, we remove even this ambiguity by adding to our official definition of program of
? the harmless stipulation that the final instruction in a program is not permitted to be the unlabeled statement
. with this last stipulation each number determines a unique program.
we can construct, for each
, a program
which computes
. that is, we shall have for each
,
the programs
are called universal for example,
can be used to compute any partially computable function of one variable, namely, if
is computed by a program
and
, then
. the program
will work very much like an interpreter. it must keep track of the current snapshot in a computation and by "decoding" the number of the program being interpreted, decide what to do next and then do it.