case instruction In 1#, the case instructions all end in #####. They pop an element off of a given register and then proceed in the program depending on which symbol (if any) was found. For example, the case instruction for R3 is 111#####. Here is what happens when we reach this in a program. If R3 is empty, we go to the very next instruction of the program. If the first symbol of R3 is 1, we delete that symbol and go to the second instruction after the case instruction. If the first symbol of R3 is #, we delete that symbol and go to the third instruction after the case instruction.

computable function This term has two different meanings, and it is important to keep them straight. Intuitively, a function is computable if there is some algorithm or program which computes it, ignoring all issues of time and space limitation. This is an informal concept rather than a mathematical definition. The precise definition for us involves 1#. For example, a partial function f : N --> N is computable (in our formal sense) if there is some 1# program p such that φ_p = f.

concatenate To take one word and add a second word after it, making a single bigger word in the process. For example 1# concatenated with 11 is 1#11. We often write concatenation with a + sign, and so the last fact is also written 1# + 11 = 1#11.

halt Informally, a program p halts if at some point in the execution of p, we reach a step which would transfer control to one instruction below the last instruction of p. There is a formal definition, which you can read in this part of Lesson One.

instruction In 1#, there are five types of instructions. They are given in the following chart:

For example, the instruction to add 1 to R4 is 1111#, and the instruction to go forward six instructions in the program is 111111###.

partial computable function See computable function above. The word "partial" means that the functions might be undefined on some or all elements of their domain. In computability theory, it is standard to work with partial functions.

primitive recursive function The primitive recursive functions are the smallest class of functions which contains the constant 0 functions of any finite number of numerical arguments, the successor function on N, and the projection functions of any finite number of numerical aruments; and the class must also be closed under composition and primitive recursion.

program A 1# program is a non-empty sequence of instructions, run together as a big word.

queue In computer science, a queue is a data structure which whose items are processed in a "first-in, first-out" manner. This is a bit like a line of people at a counter. (There are some variations on this notion which are not pertinent here.) The registers in our machine are queues because symbols get added to one end and are removed from the other. Registers here are also unbounded queues.

Recursion Theorem This usually refers to Kleene's Second Recursion Theorem. In our setting, here is its statement: Let p be any word. Consider φ_p as a function of two words φ_p(q,r). Then there is a program q* such that for all words r, φ_p(q*,r) = φ_q*(r)

register (1) a place in a real or ideal computer where some data is stored and where it can be changed. (2) the contents of such a place: that is, a sequence of 1s and #s which changes over the course of a computation. The registers in our machine are called R1, R2, . . .

self-replicating program A self-replicating program is a program p which when run on all empty register eventually halts with p itself in R1.

total function A function on some domain is total if it is defined on all elements of the domain. In mathematics, functions are total unless specified otherwise. Subjects like computability theory are exceptions to this; they study classes of functions including partial functions of various sorts.

universal program A universal program for zero-argument function is a program u with the following features: Let p be any program of 1#, or indeed any word on {1,#}. Let x be any word on {1,#}, including possibly the empty word. Then the following are equivalent:

1. If p is started with all empty registers, then eventually we halt with x in R1.
2. If u is started with p in R1 and all other registers are empty, then eventually we halt with x in R1.

word In this subject, a word is a non-empty finite sequence of 1s and #s. For example, 11 and #1## are both words. (It is more standard to allow the empty sequence to be a word as well, but we do not want to do this.)