1207
правок
Model of computation: различия между версиями
Материал из WikiGrapp
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
impossible for other models) and the cost of various operations. | impossible for other models) and the cost of various operations. | ||
The best-known example of a model of computation is the '''Turing machine'''. | The best-known example of a model of computation is the '''[[Turing machine]]'''. | ||
As all our models, a Turing machine also operates in discrete times. | As all our models, a Turing machine also operates in discrete times. | ||
It consists of a finite state machine controller, | It consists of a finite state machine controller, | ||
| Строка 10: | Строка 10: | ||
Depending on the current state and | Depending on the current state and | ||
symbol read on the current sell of the tape, the machine can change its state, write a symbol in the current sell | symbol read on the current sell of the tape, the machine can change its state, write a symbol in the current sell | ||
and move the head to the left or right. Unless otherwise specified, a Turing machine is '''deterministic''', i.e. | and move the head to the left or right. Unless otherwise specified, a Turing machine is '''[[Deterministic Turing machine|deterministic]]''', i.e. | ||
permits at most one next action at any step in a computation. | permits at most one next action at any step in a computation. | ||
| Строка 19: | Строка 19: | ||
input. Some of the symbols on the tape might thus be disregarded. | input. Some of the symbols on the tape might thus be disregarded. | ||
Let <math>T</math> be a '''nondeterministic Turing machine'''. When scanning a specific symbol in a specific state, | Let <math>T</math> be a '''[[nondeterministic Turing machine]]'''. When scanning a specific symbol in a specific state, | ||
<math>T</math> may have several possibilities for its behavior. Otherwise, a nondeterministic Turing machine | <math>T</math> may have several possibilities for its behavior. Otherwise, a nondeterministic Turing machine | ||
is defined as a deterministic one. A word <math>\alpha</math> is accepted iff it gives rise to an accepting | is defined as a deterministic one. A word <math>\alpha</math> is accepted iff it gives rise to an accepting | ||
| Строка 28: | Строка 28: | ||
The tape of a Turing machine can be viewed both as an input and output channel and as a potentially infinite external memory. | The tape of a Turing machine can be viewed both as an input and output channel and as a potentially infinite external memory. | ||
The basic difference between Turing machines and other types of automata can be briefly described as follows. | The basic difference between Turing machines and other types of automata can be briefly described as follows. | ||
A '''finite automaton''' has only an internal memory deter\-min\-ed by its finite state set; | A '''[[finite automaton]]''' has only an internal memory deter\-min\-ed by its finite state set; | ||
the input tape is not used as an additional memory. A finite automaton just reads the input in one sweep from | the input tape is not used as an additional memory. A finite automaton just reads the input in one sweep from | ||
the left to right. In a '''linear-bounded automaton''', the external memory is bounded from above by the size of | the left to right. In a '''[[linear-bounded automaton]]''', the external memory is bounded from above by the size of | ||
the input word (or by a linear function of it, which amounts to the same thing). | the input word (or by a linear function of it, which amounts to the same thing). | ||
In a '''pushdown automaton''', the access to the information in the infinite external memory is very limited and | In a '''[[pushdown automaton]]''', the access to the information in the infinite external memory is very limited and | ||
is based on the principle ''first in-last out''; | is based on the principle ''first in-last out''; | ||
a pushdown automaton is a finite automaton combined with a potentially infinite pushdown tape. | a pushdown automaton is a finite automaton combined with a potentially infinite pushdown tape. | ||
| Строка 38: | Строка 38: | ||
Hence, clearly, a Turing machine is more general than the other model of computation we have considered. | Hence, clearly, a Turing machine is more general than the other model of computation we have considered. | ||
It is also a '''general model''': every algorithm (in the intuitive sense) can be realized as a | It is also a '''general model''': every algorithm (in the intuitive sense) can be realized as a | ||
Turing machine ('''Church's thesis'''). | Turing machine ('''[[Church's thesis]]'''). | ||
| Строка 45: | Строка 45: | ||
In this model, arithmetic operations are allowed to compute the address of a memory register. | In this model, arithmetic operations are allowed to compute the address of a memory register. | ||
Other names are ''' Abstract machine''' and ''' Abstract computer'''. | Other names are ''' [[Abstract machine]]''' and ''' [[Abstract computer]]'''. | ||
