1279
правок
Model of computation: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Model of computation''' --- модель вычисления. A '''model of computation''' is a formal, abstract definition of a computer. Using a model, one ca…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
''' | A '''model of computation''' (''Модель вычисления'') is a formal, abstract definition of a computer. Using a model, one can easily analyze the intrinsic execution time or memory space of an algorithm while ignoring | ||
the intrinsic execution time or memory space of an algorithm while ignoring | |||
many implementation issues. There are many models of computations which differ | many implementation issues. There are many models of computations which differ | ||
in computing power (that is, some models can perform computations | in computing power (that is, some models can perform computations | ||
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, | ||
| Строка 13: | Строка 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. | ||
| Строка 22: | Строка 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 | ||
| Строка 31: | Строка 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. | ||
| Строка 41: | Строка 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]]'''). | ||
Another well-known example of a general model of computation is a '''random access machine''' (or '''RAM''') | Another well-known example of a general model of computation is a '''[[random access machine]]''' (or '''[[RAM]]''') | ||
whose memory consists of an unbounded sequence of registers, each of which may hold an integer. | whose memory consists of an unbounded sequence of registers, each of which may hold an integer. | ||
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]]'''. | ||
[[Категория:Теория автоматов]] | |||
