Машина Минского: различия между версиями
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>, из каждого из которых | ||
выходит по две дуге. Для каждого набора начальных значений счетчиков результат ''' | выходит по две дуге. Для каждого набора начальных значений счетчиков результат '''машины Минского''' | ||
либо не определен, если машина зацикливается, либо представляет собой | либо не определен, если машина зацикливается, либо представляет собой | ||
вектор значений счетчиков, если машина достигает конечного оператора. | вектор значений счетчиков, если машина достигает конечного оператора. | ||
Для любой частично-рекурсивной функции существует задающая ее ''' | Для любой частично-рекурсивной функции существует задающая ее '''машина Минского''' | ||
==Литература== | ==Литература== | ||
[Котов] | [Котов] | ||
Версия от 11:40, 24 ноября 2009
Машина Минского (Minsky machine) - модель вычислений, по своим вычислительным возможностям равномощная машине Тьюринга. Машина Минского состоит из конечного числа счетчиков [math]\displaystyle{ x_1, \ldots, x_n }[/math] и программы, представляющей собой орграф с двумя выделенными вершинами: начальный и конечный операторы. Другие вершины программы --- это либо операторы прибавления единицы вида [math]\displaystyle{ x_i:=x_i+1 }[/math], из которых исходит по одной дуге, либо операторы условного вычитания единицы вида [math]\displaystyle{ if\ x_i\neq 0\ then\ x_i:=x_i-1 }[/math], из каждого из которых выходит по две дуге. Для каждого набора начальных значений счетчиков результат машины Минского либо не определен, если машина зацикливается, либо представляет собой вектор значений счетчиков, если машина достигает конечного оператора. Для любой частично-рекурсивной функции существует задающая ее машина Минского
Литература
[Котов]