# Answer 3: Calculator without Digit Buttons

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-Registers Machine

Now, we define a two-registers machine. We use `a` and `b` to denote two registers storing natural number values (including zero). Register 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 also have non-conditional goto instruction, 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-Registers Machine

Now, we define a many-registers machine, which is equivalent to the Turing machine. We use `r1`, `r2`, ... to denote registers storing natural number values (including zero). Register 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