Register Machine Model of Computation: Difference between revisions

This page is intended to present an overview of the theoretical Register Machine model of computation, which is the conceptual basis for most real-world CPU designs. While it is assumed that anyone coming here will be at least passingly familiar with the concepts, it is meant to give a review of the topic to eliminate any misconceptions newcomers may have.

 

The earliest computational models, both developed in the early 1920s, were ''[https://en.wikipedia.org/wiki/%CE%9C-recursive_function recursive function theory]'' and ''recursive set theory'', both of which were used for developing a set of rules for performing computations and proving theorems.

 

 

The next significant model to arise was the ''[https://en.wikipedia.org/wiki/Lambda_calculus lambda calculus]'', created by Alonzo Church in 1935. This was a simpler model of functions than the existing type of recursive function theory, but was demonstrated to have the same computational power as RFT. Church postulated that this these two models were, in fact, as complete as any sequential model could ever be.

 

 

The Turing Machine, in its basic form as described in the paper "[https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf On Computable Numbers, with an Application to the ''Entscheidungsproblem'']", is thought of as a machine consisting of a tape read/writer and an infinitely long paper tape divided into cells containing data - one can think of the cells as boxes drawn on the tape to mark where a particular datum was. For each operation, the Turing Machine would position itself over a cell, read the datum in the cell, and based on that datum, decide whether to write a datum in a cell (whether the same one or a different one), move to another cell, or stop running and eject the tape in its current state as its final output. In his paper, he initially described each machine having a fixed set of responses to the data, stored separately in an ''action table'', and a fixed set of states which the data could put it into. He then proceeded

 

In doing so, he showed that it was possible to design a variant of the Turing Machine that could simulate any other possible Turing machine; this ''Universal Turing Machine'' (UTM) demonstrated the same kind of generality as RF and λ-Calculius, and he expanded on Church's premise that these three models represented the absolute limit of sequential computation, which became known as the ''[https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis Church-Turing Thesis]''. While it is not proven, it is generally accepted that it is likely to be correct, with the result that ''[https://en.wikipedia.org/wiki/Turing_completenessTuring Completeness]'' became the benchmark for the computing power of any mechanical model.

== The Random Access Machine model ==

The Random-Access Machine is an abstract model that closely resembles the structure of a conventional computer. It consists of a data memory divided into a set of cells, arranged linearly and monotonically (that is to say, the cells follow each other in a strictly numeric order, and each cell is the same 'size' in the address space - which doesn't ''necessarily'' reflect its capacity to hold data), where the cells can be accessed by a numeric address; an instruction memory, which may or may not be the same as the data memory, but is similarly structured; a set of operations which it can perform; a set of instructions, encoded in a form which could be held in a set of memory cells, which act to direct which operation to perform; and a Program Counter, which holds the address of a cell in the instruction memory which encodes which operation to perform next.