Answer 3: Generating Numbers with Unary Functions

Last modified: Wed Aug 29 22:25:43 2001 JST

Preliminaries

We use x to denote the accumulator of the calculator. Now, we can define following instructions.

x:=x+1; (when x>=0)
     sqrt; atan; cos; 1/x; x^2;

x:=x-1; (when x>=1)
     sqrt; 1/x; acos; tan; x^2;

```
x:=-x;
     10^x; 1/x; log
```
```
x:=2*x;
     10^x; x^2; log;
```
```
x:=x/2;
     10^x; sqrt; log;
```

x:=10*x; (when x>=1)
     log; x:=x+1; 10^x;

x:=x/10; (when x>=10)
     log; x:=x-1; 10^x;

x:=5*x; (when x>=1)
     x:=10*x; x:=x/2;

x:=x/5; (when x>=5)
     x:=2*x; x:=x/10;

goto L; (when x:integer)
     if integer(x) goto L;

if x<0 goto L; (when x:integer)
         10^x;
         if integer(x) goto L1;
         log;
         goto L;
     L1: log;

if x=0 goto L; (when x:integer)
         if x<0 goto L2;
         x:=-x;
         if x<0 goto L1;
         x:=-x;
         goto L;
     L1: x:=-x;
     L2:

if x<1 goto L; (when x:integer)
         if x<0 goto L;
         if x=0 goto L;

if x<K goto L; (when x:integer, K:integer constant, K>=2)
         if x<1 goto L;
         x:=x-1;
         if x<(K-1) goto L1;
         goto L2;
     L1: x:=x+1;
         goto L;
     L2: x:=x+1;

if odd(x) goto L; (when x:integer)
         x:=x/2;
         if integer(x) goto L1;
         x:=2*x;
         goto L;
     L1: x:=2*x;

if x mod 5 != 0 goto L; (when x:integer, x>=5)
         x:=x/5;
         if integer(x) goto L1;
         x:=5*x;
         goto L;
     L1: x:=5*x;

Two-Counter Machine

Now, we define a two-counter machine. We use a and b to denote two counters storing natural number values (including zero). Counter values are encoded by

    x = 2^a 5^b

At first, we define conditional goto's.

```
if a=0 goto L;
     if odd(x) goto L;
```

if b=0 goto L;
     if x<5 goto L;
     if x mod 5 != 0 goto L

Since we already have non-conditional goto instructions, we can use the following control structures, where C is one of the above conditions, or their Boolean expression combination.

```
if (C) { ... }
```
```
if (C) { ... } else { ... }
```
```
while (C) { ... }
```

Now we can define following instructions. Please note that u-v means max(u-v,0) in the following definitions.

```
a:=a+1;
     x:=2*x;
```
```
b:=b+1;
     x:=5*x;
```

a:=a-1;
     if (not a=0) {
         x:=x/2;
     }

b:=b-1;
     if (not b=0) {
         x:=x/5;
     }

a:=0;
     while (not a=0) {
         a:=a-1;
     }

b:=0;
     while (not b=0) {
         b:=b-1;
     }

a:=b;
         a:=0;
     L1: log;
         if integer(x) goto L2;
         10^x;
         x:=2*x;
         goto L1;
     L2: 10^x;

b:=a;
         b:=0;
     L1: log;
         if integer(x) goto L2;
         10^x;
         x:=5*x;
         goto L1;
     L2: 10^x;

b:=b+K; (when K:N constant, K>=2)
     b:=b+1;
     b:=b+(K-1);

b:=b-K; (when K:N constant, K>=2)
     b:=b-1;
     b:=b-(K-1);

a:=K*a; b:=0; (when K:N constant, K>=1)
     b:=a;
     a:=0;
     while (not b=0) {
         b:=b-1;
         a:=a+K;
     }

```
if b<1 goto L;
     if b=0 goto L
```

if b<K goto L; (when K:N constant, K>=2)
         if b<1 goto L;
         b:=b-1;
         if b<(K-1) goto L1;
         goto L2;
     L1: b:=b+1;
         goto L;
     L2: b:=b+1;

b:=b mod K; (when K:N constant, K>=1)
     while (not b<K) {
         b:=b-K;
     }

a:=a div K; b:=0; (when K:N constant, K>=1)
     b:=a;
     a:=0;
     while (not b<K) {
         b:=b-K;
         a:=a+1;
     }
     b:=0;

The followings are Input/Output instructins.

```
a:=b:=x;
     10^x;
```
```
x:=a;
     b:=a; log;
```
```
x:=b;
     a:=b; log;
```

Many-Counter Machine

Now, we define a many-counter machine, which is equivalent to the Turing machine. We use r1, r2, ... to denote counters storing natural number values (including zero). Counter values are encoded by

    a = 2^r1 3^r2 5^r3 ... pi^ri ...

where pi means i-th prime number.

The followings are primitive instructins.

if ri=0 goto L;
     b:=a;
     b:=b mod pi;
     if (not b=0) {
         goto L;
     }

```
ri:=ri+1;
     a:=pi*a; b:=0;
```

ri:=ri-1;
     if (not ri=0) {
         a:=a div pi; b:=0;
     }

The followings are Input/Output instructins.

r1:=a; r2:=0; r3:=0; ...
     b:=0; 10^x; b:=0;

a:=r1; b:=0; (when r2=0, r3=0, ...)
     b:=a; log; b:=a; log;

Naoyuki Tamura