

Glossary
of the main technical terms
used in the tutorial notes
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 nonempty 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 "firstin, firstout" 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, . . .
selfreplicating program A selfreplicating 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 zeroargument 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:
word In this subject, a word is a nonempty 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.) 