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.