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

1. Our work is based on a machine model and is therefore quite concrete, in contrast to developments that start with mu-recursion or the Church-Turing thesis.

2. 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 self-replicating program in mind.

3. We include a web-based interpreter for our text register machine language. 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 two-letter 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 two-letter 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 self-replication 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.

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.

This enables one to run text register machine programs on any computer connected to the internet.

This interpreter was written by Jiho Kim.

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.

There is also a Scheme interpreter, with additional accompanying tools. It was written by Will Byrd. For this, please follow this link.

Melvin Zhang wrote a CLI for 1# in C++ 11. It reads a 1# program via stdin and outputs R1 to stdout. It is also able to show the configuration of the registers as it runs via stderr. For this, see this link.

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 s-m-n 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 step-by-step 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 self-replicating 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.

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 self-study.

Using 1#, one can present the elementary parts of the theory of computation in a very down-to-earth 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.

If you would like to read an expository paper on this topic, please see "Recursion Theorems and Self-Replication 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.

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.