1Hash

The title of this article is not correct because of technical limitations. The correct title is actually 1#.

1# is a 5 instruction register machine language.

Add 1 to Rn	Add # to Rn	Go forward n	Go backward n	Cases on Rn
1n#	1n##	1n###	1n####	1n#####

Registers are processed as queues: first in, first out. All numbers are written in unary. The first two types of instructions add symbols to the right ends of the registers.

Case instructions pop symbols from the left ends. They work as follows:

• If Rn is empty, we go to the very next instruction.
• If the first symbol of Rn is 1, delete it and count down two instructions.
• If the first symbol of Rn is #, delete it and count down three instructions.

Instructions are sequences of 1s and #s, and programs are sequences of instructions. In the interpreter, spaces inside of instructions don't count. You may enter each instruction on a line of its own, and you also may skip lines. Alternatively, a program may look like a long sequence of instructions run together.

When treating # as 0, each program is its own Gödel number.

Implementations are offered by the language designer in Java, as well as r5rs and r6rs scheme.

Computational class

1# is Turing-complete, even if only a single register is available. The easiest way to show this is probably via simulation of DownRight; change each cell of the (finite) program into a sequence of commands that push to the register, then shift from the register and go down (i.e. jump to the code that was compiled from the cell below) if a 1 was popped or right if a # was popped.

External resources

• Paper (PDF) describing 1#