Editing One-instruction set computer (section)

=== Arithmetic machine ===
In an attempt to make Turing machine more intuitive, Z. A. Melzak consider the task of computing with positive numbers. The machine has an infinite abacus, an infinite number of counters (pebbles, tally sticks) initially at a special location S. The machine is able to do one operation: 
<blockquote>
Take from location X as many counters as there are in location Y and transfer them to location Z and proceed to instruction y.

If this operation is not possible because there is not enough counters in X, then leave the abacus as it is and proceed to instruction n. <ref>{{cite journal |title=An informal arithmetical approach to computability and computation |author=Z. A. Melzak |date=2018-11-20 |orig-date=September 1961 |journal=[[Canadian Mathematical Bulletin]] |volume=4 |issue=3 |pages=279–293 |doi=10.4153/CMB-1961-032-6 |doi-access=free}}</ref></blockquote>
In order to keep all numbers positive and mimic a human operator computing on a real world abacus, the test is performed before any subtraction. Pseudocode:

 '''Instruction''' <syntaxhighlight lang="nasm" inline>melzak X, Y, Z, n, y</syntaxhighlight>
     '''if''' (Mem[X] < Mem[Y])
         '''goto''' n
     Mem[X] -= Mem[Y]
     Mem[Z] += Mem[Y]
     '''goto''' y

After giving a few programs: multiplication, gcd, computing the ''n''-th prime number, representation in base ''b'' of an arbitrary number, sorting in order of magnitude, Melzak shows explicitly how to simulate an arbitrary Turing machine on his arithmetic machine.

;{{mono|MUL p, q}}
:<syntaxhighlight lang="nasm">
multiply:
  melzak P, ONE, S, stop                ; Move 1 counter from P to S. If not possible, move to stop.
  melzak S, Q, ANS, multiply, multiply  ; Move q counters from S to ANS. Move to the first instruction.
stop:
</syntaxhighlight>
where the memory location P is ''p'', Q is ''q'', ONE is 1, ANS is initially 0 and at the end ''pq'', and S is a large number. 

He mentions that it can easily be shown using the elements of recursive functions that every number calculable on the arithmetic machine is computable. A proof of which was given by Lambek<ref name="lambek">{{cite journal |title=How to program an infinite abacus |author=J. Lambek |date=2018-11-20 |orig-date=September 1961 |journal=[[Canadian Mathematical Bulletin]] |volume=4 |issue=3 |pages=295–302 |doi=10.4153/CMB-1961-032-6 |doi-access=free}}</ref> on an equivalent two instruction machine : X+ (increment X) and X− else T (decrement X if it not empty, else jump to T).