S programming language

the development of computability theory in [cite:@computability_davis_1994] is based on a specific programming language $\text{[math]}$ . 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
$\text{[math]}$ are called input variables of $\text{[math]}$ . the symbol $\text{[math]}$ will be called the output variable of $\text{[math]}$ and the symbols
$\text{[math]}$ are called the local variables of $\text{[math]}$ . the subscript 1 is often omitted; i.e., $\text{[math]}$ stands for $\text{[math]}$ and $\text{[math]}$ for $\text{[math]}$ . unlike the programming languages in actual use, there is no upper limit on the values these variables can assume. thus from the outset, $\text{[math]}$ must be regarded as a purely theoretical entity. nevertheless, readers having programming experience will find working with $\text{[math]}$ very easy.
in $\text{[math]}$ we will be able to write "instructions" of various sorts; a "program" of $\text{[math]}$ will then consist of a list (i.e., a finite sequence) of instructions. for example, for each variable $\text{[math]}$ there will be an instruction:
$\text{[math]}$ a simple example of a program of $\text{[math]}$ is
$\text{[math]}$ "execution" of this program has the effect of increasing the value of $\text{[math]}$ by 2. in addition to variables, we will need "labels." in $\text{[math]}$ the symbols
$\text{[math]}$ are called labels of $\text{[math]}$ , once again the subscript 1 can be omitted. a statement is one of the following:
$\text{[math]}$ where $\text{[math]}$ may be any variable and $\text{[math]}$ may be any label.
we will use the special convention that the output variable $\text{[math]}$ and the local variables $\text{[math]}$ , initially have the value 0. we will sometimes indicate the value of a variable by writing it in lowercase italics. thus $\text{[math]}$ is the value of $\text{[math]}$ .
instructions may or may not have labels. when an instruction is labeled, the label is written to its left in square brackets. for example,
$\text{[math]}$ an instruction is either a statement (in which case it is also called an unlabeled instruction) or $\text{[math]}$ followed by a statement (in which case the instruction is said to have $\text{[math]}$ as its label or to be labeled $\text{[math]}$ ). 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.
[cite:;taken from @computability_davis_1994 chapter 2 programs and computable functions]

$\text{[math]}$ [cite:;taken from @computability_davis_1994 chapter 2.2 some examples of programs]

let $\text{[math]}$ be any program in the language $\text{[math]}$ and let $\text{[math]}$ be $\text{[math]}$ given numbers. we form the state $\text{[math]}$ of $\text{[math]}$ which consists of the equations
$\text{[math]}$ together with the equations $\text{[math]}$ for each variable $\text{[math]}$ in $\text{[math]}$ other than $\text{[math]}$ . we will call this the initial state, and the snapshot $\text{[math]}$ , the initial snapshot.

<<>>case 1. there is a computation $\text{[math]}$ of $\text{[math]}$ beginning with the initial snapshot. then we write $\text{[math]}$ for the value of the variable $\text{[math]}$ at the (terminal) snapshot $\text{[math]}$ .
<<>>case 2. there is no such computation; i.e. there is an infinite sequence $\text{[math]}$ beginning with the initial snapshot where each $\text{[math]}$ is the successor of $\text{[math]}$ . in this case $\text{[math]}$ is undefined.

for any program $\text{[math]}$ and any positive integer $\text{[math]}$ , the function $\text{[math]}$ is said to be computed by $\text{[math]}$ . a given partial function $\text{[math]}$ (of one or more variables) is said to be partially computable if it is computed by some program. that is, $\text{[math]}$ is partially computable if there is a program $\text{[math]}$ such that
$\text{[math]}$ for all $\text{[math]}$ . 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 $\text{[math]}$ of $\text{[math]}$ variables is called total if $\text{[math]}$ is defined for all $\text{[math]}$ . 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.
[cite:;taken from @computability_davis_1994 chapter 2.4 computable functions]

although the program s_programming_language.html is a perfectly well-defined program of our languahe $\text{[math]}$ . we may think of it as having arisen in an attempt to write a program that copies the value of $\text{[math]}$ into $\text{[math]}$ . and therefore containing a "bug" because it does not handle 0 correctly. the following slightly more complicated example remedies this situation.
$\text{[math]}$ as we can easily convince ourselves, this program does copy the value of $\text{[math]}$ into $\text{[math]}$ for all initial values of $\text{[math]}$ . thus, we say that it computes the function $\text{[math]}$ . at first glance. $\text{[math]}$ '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
$\text{[math]}$ has the effect (ignoring the effect on the value of $\text{[math]}$ ) of an instruction
$\text{[math]}$ 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 $\text{[math]}$ has a nonzero value. thus the condition $\text{[math]}$ is always true and hence the next instruction performed will be the instruction labeled $\text{[math]}$ . now $\text{[math]}$ is not an instruction in our language $\text{[math]}$ , but since we will frequently have use for such an instruction, we can use it as an abbreviation for the program segment s_programming_language.html. such an abbreviating pseudoinstruction will be called a macro and the program or program segment which it abbreviates will be called its macro expansion.
[cite:;taken from @computability_davis_1994 chapter 2]

note that although the program of s_programming_language.html does copy the value of $\text{[math]}$ into $\text{[math]}$ , in the process the value of $\text{[math]}$ is "destroyed" and the program terminates with $\text{[math]}$ 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 $\text{[math]}$ several times to shorten the program. of course, if challenged, we could produce a legal program of $\text{[math]}$ by replacing each $\text{[math]}$ by a macro expansion. these macro expansions would have to use a local variable other than $\text{[math]}$ so as not to interfere with the value of $\text{[math]}$ in the main program.)
$\text{[math]}$ in the first loop, this program copies the value of $\text{[math]}$ into both $\text{[math]}$ and $\text{[math]}$ , while in the second loop, the value of $\text{[math]}$ is restored. when the program terminates, both $\text{[math]}$ and $\text{[math]}$ contain $\text{[math]}$ 's original value and $\text{[math]}$ .
we wish to use this program to justify the introduction of a macro which we will write
$\text{[math]}$ the execution of which will replace the contents of the variable $\text{[math]}$ by the contents of the variable $\text{[math]}$ while leaving the contents of $\text{[math]}$ unaltered. now, this program s_programming_language.html functions correctly as a copying program only under our assumption that the variables $\text{[math]}$ and $\text{[math]}$ are initialized to the value 0. thus, we can use the program as the basis of a macro expansion of $\text{[math]}$ 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
$\text{[math]}$ which will have the effect of setting the contents of $\text{[math]}$ equal to 0. the corresponding macro expansion is simply
$\text{[math]}$ where, of course, the label $\text{[math]}$ is to be chosen to be different from any of the labels in the main program. we can now write the macro expansion of $\text{[math]}$ by letting the macro $\text{[math]}$ precede the program which results when $\text{[math]}$ is replaced by $\text{[math]}$ and $\text{[math]}$ is replaced by $\text{[math]}$ in program s_programming_language.html. the result is as follows:
$\text{[math]}$

a program with two inputs that computes the function
$\text{[math]}$ is as follows:
$\text{[math]}$ again, if challenged we would supply macro expansions for " $\text{[math]}$ " and " $\text{[math]}$ " as well as for the two unconditional branches. note that $\text{[math]}$ is used to preserve the value of $\text{[math]}$ .

we now present a program that multiplies, i.e. that computes $\text{[math]}$ . since multiplication can be regarded as repeated addition, we are led to the "program"
$\text{[math]}$ of course, the "instruction" $\text{[math]}$ is not permitted in the language $\text{[math]}$ . what we have in mind is that since we already have an addition program, we can replace the macro $\text{[math]}$ by a program for computing it, which we will call its macro expansion. at first glance, one might wonder why the pair of instructions
$\text{[math]}$ was used in this program rather than the single instruction
$\text{[math]}$ since we simply want to replace the current value of $\text{[math]}$ by the sum of its value and $\text{[math]}$ . the sum program in s_programming_language.html computes $\text{[math]}$ . if we were to use that as a template, we would have to replace $\text{[math]}$ in the program by $\text{[math]}$ . now if we tried to use $\text{[math]}$ also as the variable being assigned, the macro expansion would be as follows:
$\text{[math]}$ what does this program actually compute? it should not be difficult to see that instead of computing $\text{[math]}$ as desired, this program computes $\text{[math]}$ . since $\text{[math]}$ 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 $\text{[math]}$ :
$\text{[math]}$

[cite:;taken from @computability_davis_1994 chapter 2]

we associate with each program $\text{[math]}$ of the language $\text{[math]}$ a number, which we write $\text{[math]}$ , in such a way that the program can be retrieved from its number. to begin we arrange the variables in order as follows:
$\text{[math]}$ next we do the same for the labels:
$\text{[math]}$ we write $\text{[math]}$ for the position of a given variable or label in the appropriate ordering. thus $\text{[math]}$ .
now let $\text{[math]}$ be an instruction (labeled or unlabeled) of the language $\text{[math]}$ . then we write
$\text{[math]}$ where

if $\text{[math]}$ is unlabeled, then $\text{[math]}$ ; if $\text{[math]}$ is labeled $\text{[math]}$ , then $\text{[math]}$ ;
if the variable $\text{[math]}$ is mentioned in $\text{[math]}$ , then $\text{[math]}$ ;
if the statement in $\text{[math]}$ is $\text{[math]}$ then $\text{[math]}$ or 1 or 2, respectively;
if the statement in $\text{[math]}$ is $\text{[math]}$ then $\text{[math]}$ .

some examples:
the number of the unlabeled instruction $\text{[math]}$ is
$\text{[math]}$ whereas the number of the instruction
$\text{[math]}$ is
$\text{[math]}$ note that for any given number $\text{[math]}$ there is a unique instruction $\text{[math]}$ with $\text{[math]}$ . we first calculate $\text{[math]}$ . if $\text{[math]}$ , $\text{[math]}$ is unlabeled; otherwise $\text{[math]}$ has the $\text{[math]}$ th label in our list. to find the variable mentioned in $\text{[math]}$ , we compute $\text{[math]}$ and locate the $\text{[math]}$ th variable $\text{[math]}$ in our list. then, the statement in $\text{[math]}$ will be
$\text{[math]}$ and $\text{[math]}$ is the $\text{[math]}$ th label in our list.
finally, let a program $\text{[math]}$ consist of the instructions $\text{[math]}$ . then we set
$\text{[math]}$ 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:
$\text{[math]}$ calling these instructions $\text{[math]}$ and $\text{[math]}$ , respectively, we have seen that $\text{[math]}$ . since $\text{[math]}$ is unlabeled,
$\text{[math]}$ thus, finally, the number of this short program is
$\text{[math]}$ note that the number of the unlabeled instruction $\text{[math]}$ is
$\text{[math]}$ thus, by the ambiguity in Gödel numbers, the number of a program will be unchanged if an unlabeled $\text{[math]}$ 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 $\text{[math]}$ ? the harmless stipulation that the final instruction in a program is not permitted to be the unlabeled statement $\text{[math]}$ . with this last stipulation each number determines a unique program.
[cite:;taken from @computability_davis_1994 chapter 4.1 coding programs by numbers]

we can construct, for each $\text{[math]}$ , a program $\text{[math]}$ which computes $\text{[math]}$ . that is, we shall have for each $\text{[math]}$ ,
$\text{[math]}$ the programs $\text{[math]}$ are called universal for example, $\text{[math]}$ can be used to compute any partially computable function of one variable, namely, if $\text{[math]}$ is computed by a program $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ . the program $\text{[math]}$ 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.
[cite:;taken from @computability_davis_1994 chapter 4.3 universality]

[cite:;taken from @computability_davis_1994 chapter 5 calculations on strings]