Index of Programs
IU Relief
Skip Navigation
1#: A Text Register Introduction to Computability Theory

red horizontal line
red horizontal line
red horizontal line
Programs
The main programs mentioned in the text, along with what they do and the code for them
add

Given m in R1 and n in R2 (represented in bb), the program computes the sum m + n (again, represented in bb) and puts it in R1. At the end, all other registers Ďare empty (and in particular the original inputs m and n are lost).

1##### 111### 111111### 111111111### 11##### 1111111111 11111111111 11111111111 111### 1111111111 11111111111 11111### 1111111111 11111111111 111111### 11##### 1111111111 11111111111 11### 1111111111 11111111111 1111111### 1111111111 11111111111### 11##### 1111111111 11111111111### 1111111111 11111111### 1111111111 111111111### 1##### 111### 111111### 111111111### 11##### 1111111111 1### 1111111111 111111### 111111111### 11##### 1111111111 111### 1111111111### 1111111111 1### 11##### 111### 11111111### 1### 111# 1111111111 11111111111 11111111111 1#### 111## 1111111111 11111111111 11111111111 111#### 111# 1111111111 11111111111#### 111## 1111111111 11111111111 11#### 1### 111##### 111111### 111### 1## 1111#### 1# 111111####


bump

This program takes a program p in R1 and a unary number 1n in R2, and it returns a program which is just like p except that all of the register numbers have been "bumped up" by n.

1# 1## 1## 1## 1## 1## 1## 1##### 1### 1### 1### 1##### 1# 11### 111### 1# 11111#### 1##### 1# 11### 1111111111 11### 1# 11## 11##### 1# 11### 1111### 1# 11# 111111#### 1## 1111111111 1111111111#### 1##### 1# 11### 1111111111 111### 1# 11## 11##### 1# 11### 1111### 1# 11# 111111#### 1## 1## 1111111111 11111111111 11111111111 1111#### 1##### 1# 11### 111111### 1# 1## 1## 1## 1111111111 11111111111 11111111111 11111111111 11#### 1##### 1# 11### 1111111### 1# 1## 1## 1## 1## 1111111111 11111111111 11111111111 11111111111 11111111111 1#### 1##### 1# 11### 1111111111 111111### 1# 11## 11##### 1# 11### 1111### 1# 11# 111111#### 1## 1## 1## 1## 1## 1111111111 11111111111 11111111111 11111111111 11111111111 11111111111 111111111####


compare

Compares the contents of R1 and R2. If they are exactly the same (except for spaces), the program outputs a 1 in R1; if not, it leaves R1 empty.

1##### 111111### 111111111### 11##### 1111111111 1### 1111111111### 111111#### 11##### 1111111111 11111### 111111### 11111### 11##### 111### 1111111111 111#### 1### 1##### 111### 11#### 111#### 11##### 1111### 11#### 111#### 1#


clear1

Clears R1 out.

1##### 111### 11#### 111####
By changing the first 1#### to 1n, we clear Rn.


copym,n,p

This program copies Rm to Rn, using Rp as a temporary storage register. When it is run, Rp should be empty, or else Rn would also get whatever is in Rp to begin with.

1m##### 11111111### 1111### 1n## 1p## 11111#### 1n# 1p# 11111111#### 1p ##### 111111### 111### 1m## 1111#### 1m# 111111####
One has to put in unary numbers for m, n, and p. These also should be different numbers.


diag

When diag is run with a word x in R1, the result is φwrite(x) + x in R1.
And running that gives φx(x) in R1.

1##### 11111111111### 111111### 11## 111# 111## 111## 1111111#### 11# 111# 111## 11111111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111####


length

Takes a program in R1 and tells how many instructions it has, written out as a unary number into R2. If R1 does not contain a program, then we do not care what this program does.
1##### 1111111### 11#### 11# 1##### 111### 111111#### 111####


move2,1

It moves the contents of R2 onto the end of R1, emptying R2 in the process.

11#####111111###111###1##1111####1#111111####

The general schema for movem,n is

1m #####111111###111### 1n##1111#### 1n#111111####


popn

Pops the first item from Rn.

1n##### 1### 1###


self

Outputs itself in R1.

1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1## 1## 1# 1# 1# 1## 1# 1# 1# 1## 1## 1# 1# 1# 1## 1## 1# 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1# 1# 1# 1## 1# 1# 1# 1## 1## 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1##### 11111111111### 111111### 11## 111# 111## 111## 1111111#### 11# 111# 111## 11111111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111####


u

A "universal program" in the following sense: If u is started with p in R1 and all other registers are empty, then eventually we halt with x in R1, where x is the result of starting p in R1 with all other registers empty.

See Lesson Six for the explicit code.


write

When write is started with x in R1 and R2 empty, we eventually halt with a word y = φwrite(x) in R1 and all other registers empty. Then running y with R1 empty results in x back in R1 and all other registers empty.
In symbols, φ φwrite(x)( ) = x.

1#####111111111###11111###11#11##11##111111####11#11##
111111111####11### ##111111###111###1##1111####1#111111####




Last updated: 22 November 2007
Comments: lsm at cs dot indiana.edu
Copyright 2014, The Trustees of Indiana University
Copyright Complaints