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.

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. 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. Now we can define following instructions. Please note that u-v means max(u-v,0) in the following definitions. The followings are Input/Output instructins.

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. The followings are Input/Output instructins.
Naoyuki Tamura