Programs for Arithmetic
IU Relief
Skip Navigation
1#: A Text Register Introduction to Computability Theory

red horizontal line
red horizontal line
red horizontal line
Programs for Arithmetic

LESSON Two


bb representation


Addition


Multiplication


Primitive recursive functions


Partial computable functions


Welcome

The main point of working with 1# is that it gives an explicit treatment of some of the most important results of the theory of computation. This was the reason the language was formulated and developed. Nobody ever intended 1# to be used very widely.

At the same time, once we have 1# or some other programming language, it will be of some interest to check that we really can use it to do computation. This lesson is mainly a verification that you can use 1# to send a rocket to the moon. That is, it hints that one could theoretically use 1# to do any numerical computations that could be done with any computer. So this backs up the claim that our very simple language 1# is computationally complete.

For the most part, this lesson is optional. The specific results on arithmetic are not going to be used later. The definitions of primitive recursive function and computable function are important in computability theory. But if you already know them from other sources and are willing to believe that 1# is a Turing-complete formalism, then you should feel free to work through this lesson quickly, or even to skip it altogether. The sections introduced by the harpist



are the most optional of all; these will not be used in the main parts of this tutorial.




bb representation

Before we get look at arithmetic, we have to decide on how numbers are to be represented. There are lots of ways to do this, and we need to settle on a choice.

We've already seen the unary representation of numbers. We could continue on with this. The main reason against it has to do with zero: we would like our words to be non-empty words, and so we cannot use the empty word to represent zero. One way around this is to represent the number n by the unary n + 1. This could be confusing, and so we'll use a different representation of numbers. Ours is called the backwards binary or bb representation.

As a first step, you should remember or look up the binary or base 2 representation of numbers. Here are some examples:
Decimal binary
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001
Decimal binary
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
16 10000
17 10001
18 10010
19 10011

This again is the binary representation. We can't use it, since we don't have a symbol 0 around. So we change the 0s to #s. And after that, we turn the number around, getting the backwards binary representation. Here are the first 20 numbers again, in this form:

Decimal bb
0 #
1 1
2 #1
3 11
4 ##1
5 1#1
6 #11
7 111
8 ###1
9 1##1
Decimal bb
10 #1#1
11 11#1
12 ##11
13 1#11
14 #111
15 1111
16 ####1
17 1###1
18 #1##1
19 11##1


Removing superfluous #s

One touchy point about bb representations is that all bb representations should either be the word # or else end in a 1. Here is a program that strips off superfluous #s at the end of a word in R1. It uses the first three registers It also converts an empty R1 to a #.

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


The successor function

Here is a program succ which takes a bb representation of a number n and outputs the bb representation of n+1.

1##### Cases on R1
1111111111 111### Go forward 13
1111111111### Go forward 10 to the tan section
11# Add 1 to R2
move1,2 from Lesson 1
1111### Go forward 4 to the move2,1 section
11## Add # to R2
1111111111 111#### Go backward 13 (to the top)
11# Add 1 to R2
move2,1 from Lesson 1

Here is how the program works: as long as a 1 is seen in R1, a # is put in R2; the program then loops to the top. On encountering the first #, the program goes to the blue part: it adds a 1 in R2 and then copies the rest of R1 to the end of R2. If the original input is empty, a 1 is put in R2. And after all of this, R2 is moved back to R1. The full code is shown below.

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


Comparison

Here is a program compare which takes words in R1 and R2 and decides if they are symbol-for-symbol the same. If so, it 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#

The original contents of R1 and R2 are destroyed in the process.




Addition

Here is a program add which adds numbers. 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####

This program implements the usual algorithm for addition using carrying. It is also possible to get a program for addition using some of the work that we'll see soon on primitive recursion.




Multiplication

Having seen a program for addition, we next look at multiplication.

We seek a program times with the following features: Given m in R1 and n in R2 the program computes the sum m x n and puts it in R1. At the end, all other registers are empty (and in particular the original inputs m and n are lost). As with addition, we want to work with bb representations.

Recall that with addition, our program was designed to implement the usual carrying algorithm. We could do the same for multiplication, but this is not the best choice for us. Although it is more familiar, it is less general; so the ideas used in the traditional algorithm are not going to be useful in other contexts. The basic idea in our treatment is that multiplication satisfies two recursion equations:


m x 0 = 0

m x (n + 1 ) = (m x n) + m


These enable us to multiply as a form of iterated addition. For example, suppose we want to multiply m = 4 (##1) by n = 3 (11). We use i as a temporary index which will go from 0 (#) up to n as we do our work.

We start with i= #, and our first recursion equation tells us that m x i = #. This is our first current value. Then we compare i with n. If the two were equal, then our value # would be m x n. If not, we go ahead. (In this case, the two are not the same.) Otherwise, we first want to add # + ##1 to get ##1. This is our new current value. Second, we update i to # + 1 = 1.

We compare i with n. If the two were equal, then our value ##1 would be m x n. If not, we go ahead. (In this case, the two are not the same.) Otherwise, we first want to add ##1 + ##1 to get ###1. This is our new current value. Second, we update i to # + 1 = #1.

Continuing, we again compare i with n. If the two were equal, then our value ###1 would be m x n. If not, we go ahead. (As before, the two are not the same.) Otherwise, we first want to add ##1 + ###1 to get ##11. This is our new current value. Second, we update i to #1 + 1 = 11.

Continuing, we again compare i with n. The two are indeed equal, and our value ##11 is m x n..



The description above leads to some "pseudocode":

1. (initialization) add # to R3 and also add # to R4
2. copy R2 to R5 using R6
3. copy R3 to R6 using R7
4. compare R5 and 56:
if equal, goto "cleanup", if not go ahead
5. copy R1 to R5 using R6
6. move R4 to R6
7. add R5 to R6, leaving the answer in R5
8. move R5 to R4
9. take the successor of R3, using R5
10. go back to the main loop, step 2
11. the "cleanup" stuff: clear R1, R2, and R3
12. move R4 to R1

We next want to fill in this pseudocode by actual 1# programs. For most of the steps, we use move programs from earlier. Step 4 uses compare from above, along with bump from earlier. Similarly, step 9 uses the add function from just above.

1. add # to R3 and # to R4
111##
1111##

2. copy R2 to R5 using R6
11##### 11111111### 1111### 11111## 111111## 11111#### 11111# 111111# 11111111#### 111111##### 111111### 111### 11## 1111#### 11# 111111####

3. copy R3 to R6 using R7
111##### 11111111### 1111### 111111## 1111111## 11111#### 111111# 1111111# 11111111#### 1111111##### 111111### 111### 111## 1111#### 111# 111111####

4. compare R5 and 56. This is φbump(compare,4)
11111##### 111111### 111111111### 111111##### 11111111111### 1111111111### 111111#### 111111##### 111111111111111### 111111### 11111### 111111##### 111### 1111111111111#### 1### 11111##### 111### 11#### 111#### 111111##### 1111### 11#### 111#### 11111#

followed by
11111##### 111### 1111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111### 1#

5. copy R1 to R5 using R6
1##### 11111111### 1111### 11111## 111111## 11111#### 11111# 111111# 11111111#### 111111##### 111111### 111### 1## 1111#### 1# 111111####

6. move R4 to R6
1111##### 111111### 111### 111111## 1111#### 111111# 111111####

7.add R5 to R6, leaving the answer in R5. This is φbump(add,4)
11111##### 111### 111111### 111111111### 111111##### 1111111111 11111111111 11111111111 111### 1111111111 11111111111 11111### 1111111111 11111111111 111111### 111111##### 1111111111 11111111111 11### 1111111111 11111111111 1111111### 1111111111 11111111111### 111111##### 1111111111 11111111111### 1111111111 11111111### 1111111111 111111111### 11111##### 111### 111111### 111111111### 111111##### 1111111111 1### 1111111111 111111### 111111111### 111111##### 1111111111 111### 1111111111### 1111111111 1### 111111##### 111### 11111111### 1### 1111111# 1111111111 11111111111 11111111111 1#### 1111111## 1111111111 11111111111 11111111111 111#### 1111111# 1111111111 11111111111#### 1111111## 1111111111 11111111111 11#### 1### 1111111##### 111111### 111### 11111## 1111#### 11111# 111111####

8. move R5 to R4
11111##### 111111### 111### 1111## 1111#### 1111# 111111####

9. take the successor of R3, using R5. We modify the program succ from above.
111##### 1111111111 111### 1111111111### 11111# 111#####111111###111### 11111##1111#### 11111#111111#### 1111### 11111## 1111111111 111#### 11111# 11111#####111111###111### 111##1111#### 111#111111####

10. go back to the main loop, step 2
1111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 11111111111 1111111####

11. the "cleanup" stuff: clear R1, R2, and R3; also 12: move R4 to R1
1##### 111### 11#### 111####
11##### 111### 11#### 111####
111##### 111### 11#### 111####
1111##### 111111### 111### 1## 1111#### 1# 111111####



The full program is

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

The parts of the program that are shaded red are special to the multiplication algorithm. The point is that if we wish to write a program for something similar, we could keep the outside "shell" and just modify the red lines above. Your first exercise below asks you to do just that.


Exercises

Exercise 1 Modify the multiplication program to compute exponentiation. This would be a program exp with the following property: when started with the bb representation of m in R1 and n in R2, the program eventually halts with the bb representation of mn in R1.

Exercise 2 In our work on multiplication, we assumed addition and worked with it to get multiplication. Now forget about our program for addition, and using only the program succ for the successor function, construct a program for addition.

Exercise 3 Write a program which, when started with n in bb in R1, gives n! in R1. [Here n! is the factorial function. Remember that 0! = 1 and (n+1)! = (n+1) x n!.]

Exercise 4 Write two programs which convert back and forth from unary to binary representation.




Primitive recursive functions
We next define the set of primitive recursive functions of numbers. Each primitive recursive function is a function of some fixed number of arguments, but different primitive recursive functions will be functions of different numbers of arguments. We write f(x1, . . . xk) to indicate that f is a function of k arguments. So the input to f is k numbers (in a fixed order), and the output is again a number.

It is the smallest collection F of functions with the following two properties:

  1. F contains the constant function z(x) = 0; that is, the constant function of one argument with value 0.

  2. F contains the successor function s(x) = x+1.

  3. F contains all of the projection functions pjk, where 1 <= j <= k, and pjk is defined by

    pjk (x1, . . . xk) = xj
  4. F is closed under composition. This means that if f(x1, . . . xk) is a primitive recursive function, and if

    g1(x1, . . . xn), . . ., gk(x1, . . . xn)
    are all primitive recursive, then so is h(x1, . . . xn) given by
    h(x1, . . . xn) = f(g1(x1, . . ., xn),. . ., g(x1, . . . xn))
  5. F is closed under primitive recursion. This means then so is f(x1, . . . xk, xk+1), given by

    f(x1, . . ., xk, 0) = g(x1, . . ., xk)
    f(x1, . . . xk, n+1) = h(x1, . . . xk, f(x1, . . . xk, n), n)



Partial computable functions This part has yet to be written.


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