Машина Минского

Материал из WEGA
Версия от 16:21, 19 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Машина Минского''' (''Minsky machine'') - модель вычислений, по своим вычислительны...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Машина Минского (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], из каждого из которых выходит по две дуге. Для каждого набора начальных значений счетчиков результат М.М. либо не определен, если машина зацикливается, либо представляет собой вектор значений счетчиков, если машина достигает конечного оператора. Для любой частично-рекурсивной функции существует задающая ее М.М.

Литература

[Котов]