Register Machine - Historical Development of The Register Machine Model

Historical Development of The Register Machine Model

Two trends appeared in the early 1950s—the first to characterize the computer as a Turing machine, the second to define computer-like models—models with sequential instruction sequences and conditional jumps—with the power of a Turing machine, i.e. a so-called Turing equivalence. Need for this work was carried out in context of two "hard" problems: the unsolvable word problem posed by Emil Post—his problem of "tag"—and the very "hard" problem of Hilbert's problems—the 10th question around Diophantine equations. Researchers were questing for Turing-equivalent models that were less "logical" in nature and more "arithmetic" (cf Melzak (1961) p. 281, Shepherdson-Sturgis (1963) p. 218).

The first trend—toward characterizing computers—seems to have originated with Hans Hermes (1954), Rózsa Péter (1958), and Heinz Kaphengst (1959), the second trend with Hao Wang (1954, 1957) and, as noted above, furthered along by Zdzislaw Alexander Melzak (1961), Joachim Lambek (1961), Marvin Minsky (1961, 1967), and John Shepherdson and Howard E. Sturgis (1963).

The last five names are listed explicitly in that order by Yuri Matiyasevich. He follows up with:

"Register machines are particularly suitable for constructing Diophantine equations. Like Turing machines, they have very primitive instructions and, in addition, they deal with numbers" (Yuri Matiyasevich (1993), Hilbert's Tenth Problem, commentary to Chapter 5 of the book, at http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm. )

It appears that Lambek, Melzak, Minsky and Shepherdson and Sturgis independently anticipated the same idea at the same time. See Note On Precedence below.

The history begins with Wang's model.

Read more about this topic:  Register Machine

Other articles related to "model, machine":

Historical Development of The Register Machine Model - Cook and Reckhow (1973) Describe The RAM
... (1973) cite Hartmanis (1971) and simplify his model to what they call a Random access machine ( RAM—i.e ... a machine with indirection and the Harvard architecture) ... back to Melzak (1961) but with a much simpler model than Melzak's ...

Famous quotes containing the words model, machine, historical, development and/or register:

    Your home is regarded as a model home, your life as a model life. But all this splendor, and you along with it ... it’s just as though it were built upon a shifting quagmire. A moment may come, a word can be spoken, and both you and all this splendor will collapse.
    Henrik Ibsen (1828–1906)

    The momentary charge at Balaklava, in obedience to a blundering command, proving what a perfect machine the soldier is, has, properly enough, been celebrated by a poet laureate; but the steady, and for the most part successful, charge of this man, for some years, against the legions of Slavery, in obedience to an infinitely higher command, is as much more memorable than that as an intelligent and conscientious man is superior to a machine. Do you think that that will go unsung?
    Henry David Thoreau (1817–1862)

    We can imagine a society in which no one could survive as a social being because it does not correspond to biologically determined perceptions and human social needs. For historical reasons, existing societies might have such properties, leading to various forms of pathology.
    Noam Chomsky (b. 1928)

    The work of adult life is not easy. As in childhood, each step presents not only new tasks of development but requires a letting go of the techniques that worked before. With each passage some magic must be given up, some cherished illusion of safety and comfortably familiar sense of self must be cast off, to allow for the greater expansion of our distinctiveness.
    Gail Sheehy (20th century)

    Genius ... is the capacity to see ten things where the ordinary man sees one, and where the man of talent sees two or three, plus the ability to register that multiple perception in the material of his art.
    Ezra Pound (1885–1972)