![[Under Construction]](images/undercon.gif){kind=small}
There is an infinite set that is not too big. - John von Neumann (1903-1957)
| The program for the Univeral Register Machine |
|
| Introduction to the program for the Univeral Register Machine |
|
Introduction Register machines won't be found in a company or at home. They are only theoretical machines for mathematics and computer science. Register machines and turing machines have the same origin, the history of the latter starting at around 1900. The german mathematician David Hilbert (1862-1943) presented a proposal on the international mathemathician congress in Paris 1900: to root the whole mathematical theorems to a small amount of axioms. These axioms should be independent of each other and as simple as possible. Starting on these axioms, all theorems would be proofed. Hilbert thought that there may be a, yet undefined, way to give and proof every mathematical theorem. This hypothesis is known as Entscheidungsproblem. 1931 the austrian mathematician Mathematiker Kurt Gödel (1906-1978) found the Unvollständigkeitssatz. This theorem says that there exist mathematical systems which contain really true mathematical theorems, but truth can't be proofed in this system. Gödel showed that this is true for the axioms of peano. So the Entscheidungsproblem can't be solved for 'our normal' mathematics. To investigate further on the Entscheidungsproblem the british mathematician Alan Mathison Turing (1912-1954) did some experiments with general algorithms. At this time the computing machines were nearly 300 years old. There were Blaise Pascals (1623-1662) machine, able to subtract and Charles Babbages (1782-1871) 'Analytical Engine' and finally Hermann Holleriths (1860-1929) machine to analyse the data of the census of population. All these machines working with a fixed algorithm. But the advancement of the 'Analytical Engine' of Charles Babbage had some parts to allow variable algorithms. The looms of Joseph Marie Jaquard had a variable algorithm too: they were controlled by punch cards. Turing invented a (hypothetical) machine, which later got his name: the turing machine. This machine is able to convert an input into an output, where the input and output is represented by a series of symbols, which are filed on a strip. The turing machine doesn't know anything about arithmetical operations, it only has inner states, a table of transformation rules from one state to another and a read-write-head, which moves along the strip and may read and write from the strip. So the turing machine is a programmable machine, however a theoretical abstract one. This machine may be best described as a some type of tape recorder. The magnetic tape contains works both as input source and output destination. The machine now runs in the way, that it read one symbol from the input. The transformation rules are used to get the new state of the machine, which symbol is to be written and in which direction the read-write-head is to be moved along the strip/tape. To define an algorithm for the turing machine, there is only a table with transformation rules needed. Such a rule may be 'if the machine is in state A and symbol X is read then the new state is B and symbol Y is to be written, finally the read-write-head is to be moved to the left'. A table of this type may also be called a program for turing machines. Then the program, the table with the transformation rules, is fixed for the whole runtime of the machine. The turing machine has to be started manually, it will stop if it reaches state 'STOP'.
When experimenting with various algorithms for turing machines there is always the question if an algorithm/program delivers a result or if it runs forever. This so called Halteproblem is defined as: Does an algorithm exists which computes if a turing machine program stops in finite time? Turing found that it's only possible to prove this for single algorithms and that there are algorithms where it's not possible to find an answer in finite time. There is no general solution to the Halteproblem On the way to this answer Turing found that there is a special turing machine program which simulates every turing machine with any program (for example a turing machine with multible read-write-heads). He showed the existence of the universal turing machine program.
In the book 'Computerdenken' from Roger Penrose
Studying functions computable by turing machines one can prove that they are partial recursive functions and vice versa
The turing machine is not the only mathematic model equivalent to the partial recursive functions. Gödel (1906-1978), Herbrand (1908-1931), Kleene (1909-1994) and Markov (1856-1922) all followed different ways. Church himself invented the l-Calculus, Emil Post (1897-1954) the so called posts machine. The register machine of J.C. Shepherdson and H.E. Sturgis The way to this will be split in three parts: first the universal register machine program will be implemented as C++ program - a simulator for register machines and interpreter for register machine programs in C++. This interpreter will result directly from the operation breakdown of the register machine. After this step we will transform C++ code to register machine code on a general basis. This will create a compiler. Both steps together will lead to the third step: The interpreter from the first step is to be compiler with the compiler from the second step into register machine code. The final result will be a interpreter of register machine programs as register machine program: the universal register machine program as register machine program. Recommended reading:
Footnotes:
|