Аноним

Машина Минского: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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.