4635
правок
Машина Минского: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
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>, из каждого из которых | ||
| Строка 13: | Строка 13: | ||
Для любой частично-рекурсивной функции существует задающая ее '''машина Минского''' | Для любой частично-рекурсивной функции существует задающая ее '''машина Минского''' | ||
==Литература== | ==Литература== | ||
* Котов В.Е. Сети Петри. — М.: Наука, 1984. | |||