4194
правки
Машина Минского: различия между версиями
Материал из WEGA
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Машина Минского''' (''Minsky machine'') - модель вычислений, по своим вычислительны...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>, из каждого из которых | ||
выходит по две дуге. Для каждого набора начальных значений счетчиков результат ''' | выходит по две дуге. Для каждого набора начальных значений счетчиков результат '''машины Минского''' | ||
либо не определен, если машина зацикливается, либо представляет собой | либо не определен, если машина зацикливается, либо представляет собой | ||
вектор значений счетчиков, если машина достигает конечного оператора. | вектор значений счетчиков, если машина достигает конечного оператора. | ||
Для любой частично-рекурсивной функции существует задающая ее ''' | Для любой частично-рекурсивной функции существует задающая ее '''машина Минского''' | ||
==Литература== | ==Литература== | ||
[Котов] | [Котов] | ||
