PAM machine emulator

A RAM machine is an abstract computer that is Turing complete and belongs to the register machine class. It is equivalent to the universal Turing machine, while more visual and convenient in proving the correctness of the algorithms. In this topic, I will tell you how it works and attach references to the working implementation of the PAM machine emulator with some interesting examples.

The abstract model of a PAM machine (RAM: Random Access Machine) assumes the existence of an infinite set of registers, each of which is capable of storing an integer number of any length. Register index can be any integer (including negative). The program for the PAM machine is the final set of instructions modifying the memory registers; you can look at it as a very simple assembler. The study of the machine will begin with a review of a set of commands.

HALT

The most simple instruction, ordering the machine to stop the execution to achieve it.

READ

The machine must support I / O, and the READ operation is designed to enter numbers from the keyboard (or other stream, however, we should not forget that we are dealing with an abstract model, where the main thing is to provide input for the algorithm so that a massive problem can be solved). The number is entered in the register [0] , this register will continue to be considered “special”.
')

WRITE

Displays (on the screen) the number stored in [0] . No more arguments.

LOAD x / [x] / [[x]]

More cunning instruction - writes an arbitrary value to [0] . The value can be set constant: LOAD 5 , for example. Or copied from another cell: LOAD [3] - here the value from the third register is copied to zero. Or by using dual addressing: LOAD [[3]] - the number from the register to which the third register “refers” to will get to “zero”. Thus, it is clear that the machine supports indirect addressing.

STORE [x] / [[x]]

Writes a value from [0] to the specified cell. Either direct addressing is available: STORE [1] or indirect: STORE [[1]] .

NEG

Draws the sign of the number in [0] . Accordingly, -3 will be replaced by 3 , zero has no sign.

LSHIFT x / [x] / [[x]]

Performs a bitwise left shift of the number in [0] on the specified argument; available constant, direct address, indirect address. For example, LSHFIT [[3]] multiplies the value in [0] by two to the power of the register value referenced by [3] .

RSHIFT x / [x] / [[x]]

Performs a bitwise right shift, arguments and meaning are similar to LSHIFT. The classic model does not allow the use of signed numbers as LSHIFT / RSHIFT arguments.

ADD x / [x] / [[x]]

Adds the value indicated by the function argument to [0] . Available constant, direct addressing, indirect.

And finally, useful for organizing cycles and conditions:

JUMP tag

Unconditional jump to the specified line of code or label.

Jg tag

Go to the specified label if the value in the zero register is strictly positive.

That's all!

But what about the other arithmetic operations? Yes, the classical model does not imply redundant instructions, so they will have to be implemented through addition. As a small puzzle I propose to implement:

• multiplying m by n (faster than O (max (m, n)) );
• square m (faster than O (m) );
• degree m (faster than O (m * log (m)) );
• root of arbitrary degree (recall the Newton method).

A more difficult task is to consider the assessment of the complexity and correctness of the implementation of each method (but here it is much simpler than on a Turing machine).

One of the simplest properties of the machine is the ease of detecting the deadlock state (stable useless state): if during the transition to the same label the values ​​of the registers remained the same, then we “stuck”.

I enclose an example of the simplest program (hopefully self-evident), which summarizes the N numbers entered from the keyboard (other examples in the archive with the executable file of the emulator):



For some variety (to be honest, initially, in order to “have fun” for kids at school), I added a few primitives (dot and line) to draw graphic elements with which you can create something funny. For example:



You can download the implementation at this link , and the source here . The quality of the sources, as well as the language in which they are written (yes, this is Delphi) is not worth much fault, I wrote them many years ago and I am surprised that everything works. The implementation supports long arithmetic and emulates an infinite number of registers, but we know that the memory of the physical machine is not unlimited :)

Good luck trying!