4624
правки
Машина Минского: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Машина Минского''' (''Minsky machine'') - модель вычислений, по своим вычислительны...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Машина Минского''' (''Minsky machine'') | '''Машина Минского''' (''[[Minsky machine]]'') — | ||
модель вычислений, по своим вычислительным возможностям равномощная | модель вычислений, по своим вычислительным возможностям равномощная | ||
''машине Тьюринга''. ''' | ''[[машина Тьюринга|машине Тьюринга]]''. '''Машина Минского''' состоит из конечного числа счетчиков | ||
<math>x_1, \ldots, x_n</math> и программы, представляющей собой орграф | <math>x_1, \ldots, x_n</math> и программы, представляющей собой [[орграф]] | ||
с двумя выделенными вершинами: начальный и конечный операторы. | с двумя выделенными [[вершина|вершинами]]: начальный и конечный операторы. | ||
Другие вершины программы | Другие вершины программы — это либо операторы прибавления единицы | ||
вида <math>x_i:=x_i+1</math>, из которых исходит по одной дуге, либо | вида <math>\,x_i:=x_i+1</math>, из которых исходит по одной [[дуга|дуге]], либо | ||
операторы условного вычитания единицы вида | операторы условного вычитания единицы вида | ||
<math>if\ x_i\neq 0\ then\ x_i:=x_i-1</math>, из каждого из которых | <math>if\ x_i\neq 0\ then\ x_i:=x_i-1</math>, из каждого из которых | ||
выходит по две дуге. Для каждого набора начальных значений счетчиков результат ''' | выходит по две дуге. Для каждого набора начальных значений счетчиков результат '''машины Минского''' | ||
либо не определен, если машина зацикливается, либо представляет собой | либо не определен, если машина зацикливается, либо представляет собой | ||
вектор значений счетчиков, если машина достигает конечного оператора. | вектор значений счетчиков, если машина достигает конечного оператора. | ||
Для любой частично-рекурсивной функции существует задающая ее ''' | Для любой частично-рекурсивной функции существует задающая ее '''машина Минского''' | ||
==Литература== | ==Литература== | ||
* Котов В.Е. Сети Петри. — М.: Наука, 1984. | |||
