Anonymous user
Register Machine Model of Computation: Difference between revisions
Register Machine Model of Computation (view source)
Revision as of 00:20, 26 November 2017
, 6 years agono edit summary
| [unchecked revision] | [unchecked revision] |
No edit summary |
No edit summary |
||
Line 23:
It has to be understood that these models were 'mechanical' only in the sense of being built on a set of rules; they were not very useful for developing a physical computing device. Of them all, the UTM was the closest, as it was described in terms of an imaginary mechanism consisting of a reading and writing head and an infinitely long paper tape. While it was not a practical design, it demonstrated that the mechanical calculators of the time had a solid theoretical basis, and more importantly, re-introduced the concept (originally proposed by Charles Babbage) of a ''programmable'' computation device.
In 1955, linguist [https://en.wikipedia.org/wiki/Noam_Chomsky Noam Chomsky] worked out an hierarchy for categorizing [https://en.wikipedia.org/wiki/Formal_grammar formal grammars] in terms of both the [https://en.wikipedia.org/wiki/Generative_grammar grammars capable of generating sentences in them], and the mathematical models for 'recognizing' grammatically-correct sentences mechanically. He demonstrated that not only did the same [Chomsky Hierarchy] apply to both how sentences can be generated mechanically, and how they can be recognized mechanically, but also that the levels of the hierarchy corresponded to certain degrees of computability - and specifically, that his [https://en.wikipedia.org/wiki/Unrestricted_grammar Type-0 grammars] (also called ''unrestricted grammars'') were ''recursively enumerable'', and hence required a Turing-complete mechanism to recognize or generate. ▼
=== Early Electromechanical and Electronic Computers ===
Line 39 ⟶ 34:
This led to the creation of a new model which could describe these limitations and allow them to determine what they were. This new model, the ''[https://en.wikipedia.org/wiki/Linear_bounded_automaton Linear-Bounded Automaton]'', a variant of the Turing machine with a finite available memory (it is usually described in terms of the reader having access to a finite, contiguous part of an infinite tape, hence the term 'linear bounded'). This allowed for study of the memory requirements of different classes of computations, and similar models were developed for studying the time requirements.
=== Finite Automata and the Chomsky Hierarchy ===
Meanwhile, work on understanding the more abstract forms continued, and a wide variety of Turing-complete computation models were formulated, along with many provably less powerful models. While the Church-Turing thesis served as a hypothetical limit for these, it remained a conjecture, and it wasn't entirely clear how the different models related to each other - especially those which were not Turing-complete.
▲In 1955, linguist [https://en.wikipedia.org/wiki/Noam_Chomsky Noam Chomsky] worked out an hierarchy for categorizing [https://en.wikipedia.org/wiki/Formal_grammar formal grammars] in terms of both the [https://en.wikipedia.org/wiki/Generative_grammar grammars capable of generating sentences in them], and the mathematical models for 'recognizing' grammatically-correct sentences mechanically. He demonstrated that not only did the same [Chomsky Hierarchy] apply to both how sentences can be generated mechanically, and how they can be recognized mechanically, but also that the levels of the hierarchy corresponded to certain degrees of computability - and specifically, that his [https://en.wikipedia.org/wiki/Unrestricted_grammar Type-0 grammars] (also called ''unrestricted grammars'') were ''recursively enumerable'', and hence required a Turing-complete mechanism to recognize or generate.
=== Counters, Accumulators, Stacks, and Registers ===
However, the question of whether the machines could ''in principle'' be Turing-complete if given an infinite resource - memory, presumably - remained. This led to the creation of a set of abstract models for machines similar to those in actual use, but without the memory limits of a LBA.
== 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.
| |||