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 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.