1#: a Text Register Machine Introduction
to Computability
Theory
Lawrence S. Moss
Welcome
This web site is an introduction to the basic notions
of computability theory, working with a variant of register machines.
The two key differences between our treatment and
more standard approaches are
Our work is based on a
machine model and is therefore quite concrete,
in contrast to developments that start with murecursion or the
ChurchTuring thesis.
We prove and use the Recursion Theorem. In fact, our
version of register machines was designed with results like
the Recursion Theorem and the existence of selfreplicating
program in mind.
We include a Java interpreter. A good deal of the learning
is done in the course of writing programs.
A text register machine is similar to the register machines that one sees
in the literature. The main differences are that the registers do not hold
numbers but rather words from a fixed alphabet. The instructions
add items to these words, and they also examine the first symbols
of the words.
In addition, the instructions that run a text register machine
must themselves be words over the same alphabet.
In more technical terms, we have a machine with queues
but no tape, and the machine directly manipulate words of the same
general type as its own
programs.
Here is another way to look at it:
A Post machine is a finite automaton controlling a queue.
Our proposal amounts to using many queues instead of just one;
to working with a twoletter alphabet instead of two symbols and a blank;
and finally, to work from the start with a particular encoding of these machines
via words on the same twoletter alphabet.
Because our emphasis is more on the programs than the automata, we
have chosen to name this formalism with a derivative of register machine.
This project began as a proposal to answer the following question:
What is the simplest setting in which one can formalize the notion that
computer programs can operate on other programs? The
centerpiece of our answer is
a programming language called 1#. This language is intended to be
extremely simple: it has only two symbols (1 and #) and five types
of basic instructions. If you would like to see the full language,
please click on the link "1# in a nutshell" on the left bar.
The point of 1#
is to illustrate explicit register
machine constructions of selfreplication and the Recursion Theorems
of computability theory. The goal is to provide tools to explore
these themes that are very simple to explain and use, and yet
rich enough to provide the explicit programs of interest.
1# would not be a good tool for other computational purposes.
What is it called, and what are all the cartoons for?
The language is called 1# after the two symbols in its alphabet.
It also
has the feature
that the smallest program in it is the name of the language itself.
We could have used 0 (or any other symbol) instead of #.
The reason for using the # is that it plays a different role
in the syntax from the 1.
The # symbol is pronounced in many different ways:
sharp, hash, check, octothorpe, pound, numero, etc.
Accordingly, you may pronounce the name of the language any way
you like.
The cartoons of musicians are by James Thurber. Their
purpose is to make working through the tutorial more fun.
There are fixed cartoons for the beginning and ending of each
page, and the sections inside each tutorial are also marked:
the drummer indicates an essential section, and the harpist
a section whose material is for the most part not needed in
the rest of our work.
An important part of our work will be done on the accompanying interpreter.
It can be obtained from
this link.
To run it, you'll need Java 1.5 or 5 on your computer.
As of this writing, one would dowload the interpreter and
then run the web pages from this site.
At some point in the future, the web pages themselves will
be bundled with the interpreter.
This interpreter was written by Jiho Kim.
A flowchart program, and other tools,
are available
here.
These include
a formatter, a parser that allows programmers to
write in a shorthand language closer to English, and
a tool that allows one to design a flowchart and have it translated
into either the official 1# language or to the shorthand.
They were mainly written by Jon Baumann during his senior
year as an IU undergraduate.
Scheme tools
There is also a Scheme interpreter, with additional accompanying tools.
It was written by Will Byrd.
For this, please follow this link.
Using 1# as an introduction to computability theory
Being based on register machines, it should
be no harder to pick up than other basic machine models
in the theory of computation. The advantage of our treatment
is that one gets to the central theoretical results
like the smn Theorem and the existence of universal programs
quickly, and does so in an explicit manner that should be
helpful to many students. The main disadvantage is that
the particular formalism studied here is not useful for other purposes.
The material could be used either as the
end of a course on automata theory/computability theory,
or as the beginning of a course on computability theory itself.
For the most part, the material develops in a stepbystep
fashion: each point uses a fair amount from what came before. But
it is possible to take a shortcut through some of the material,
especially for people who are
mainly interested in selfreplicating programs
and the Recursion Theorems. For such people, we indicate sections
which could be omitted by starting them with the harpist cartoon
rather than the drummer.
Tutorial lessons
We have seven tutorial lessons linked to the interpreter.
Each of these is intended to take one or two classroom lectures.
The lessons contain numerous exercises that could either serve
as homework or as springboards for classroom discussions.
The lessons also can be done as individual selfstudy.
Using 1#, one can present the elementary parts of the theory
of computation in a very downtoearth way. At the same time,
one can present important results like the Recursion Theorem,
results which often are missing from beginning classes.
This should be the main attraction of using this tool.
Publications
If you would like to read an expository
paper on this topic, please see
"Recursion Theorems and SelfReplication Via Text Register Machine
Programs", in the Bulletin of the European Association for
Theoretical Computer Science, vol. 90, 2006, pp.
You can get a version of this paper
here.
There is also a paper on a theoretical point related to
register machines, investigating what can and cannot be
computed with only one register.
You can find the paper
by clicking here.
The status of the material as of the end of 2009
My vision for the material here has been changing over the
years. Last year
I taught a class on this material,
and I expect to continue polishing this tutorial web text.
I also am writing course notes in a more traditional format.
I feel that the web text that you are reading should be usable
for a variety of levels. (For example, I taught it to
students with no background in mathematics or computer science
fairly recently.) On the other hand,
the course notes are for a graduate
class. If you would like to see them, please write to me.
Getting back to the web text,
the first six lessons are around 75% done.
The lesson on 'Other models of computation' should be available
by the end of 2008. Lessons on Church's Theorem and other
undecidability results do not really use 1#, and so they exist
in the ordinary form, on paper.
