Описание недетерминированной машины Кузьмина на пальцах

Формальное описание здесь

dou.ua/forums/topic/35914

Здесь мы рассмотрим описание недетерминированной машины Кузьмина на пальцах. Ибо не совсем понятно отличие от классической архитектуры. Вот мы и оттолкнемся от классического программирования. В основе которого алгоритмы, формализацией которых служит (как сформулировано в википедии) машина Тьюринга. Осмелюсь утверждать, что МТ это больше чем алгоритм. Для наглядности (только без рисунков) рассмотрим построение блок-схемы. Можно считать блок-схему эквивалентом алгоритма. Не думаю, что найдутся возражения.

Блок-схема

Повторим известное. Блок-схема представляет собой последовательность элементов блок-схемы прямоугольников (Q) и ромбов (E)), где прямоугольники обозначают некоторые действия, ромбы-условия. Соединяющие линии стрелки-переходы указывают порядок «выполнения» каждого элемента блок-схемы. В принципе можно считать, что линии указывают порядок поступления каждого элемента блок-схемы в некий процессор на «выполнение» и не важно кто будет выполнять голова или какая-то реальная машина. Однако, принципиально что одна голова или один процессор.

Попробуем немного переформулировать в чем заключаются действия в прямоугольниках. Где-то в них или вне их определяются данные, изменение которых мы (в программах) и называем действиями. Когда по каким-то причинам мы сочли что изменения достойны для анализа, мы ставим ромбик, обозначающий этот анализ, и заодно отметим что порядок этого анализа происходит в конкретном месте, там, где мы сочли необходимым провести его. Т.е. туда, куда указывает стрелка, исходящая из предыдущего элемента блок-схемы и после анализа, куда указывает одна или две стрелки, исходящие из ромба.

Немного размышлений.

Поговорим за состояние программы. Есть широкое толкование вместе с состоянием регистров адреса выборки команды, адреса возврата и состояние ячеек. Это может быть важно для построения системы, но для задач, решаемых обычными программистами имеет значение только изменения всех переменных. Т.е. то, что содержит информацию и представляет интерес для решаемой задач. Вот и назовем состоянием все множество текущих значений всех переменных (А), а сами переменные атрибутами. Хотя атрибуты могут определяться в прямоугольниках, оставим там только действия, которые заключаются в изменении атрибутов. Событием же назовем изменение состояния. Проверкой этого состояния у нас занимается логическое выражение в ромбе E. Так фактически это логическое выражение (в общем случае, логическая функция от переменных) и является определением события. Следующий шаг в наших рассуждениях — это приспособить получаемую конструкцию к выполнению на нескольких процессорах. Для этого разрушаем нашу блок-схему убирая все линии, определяющие порядок выполнения. К элементам блок схемы добавляем новый вид элемента — определение атрибутов, а оставшееся действия в прямоугольнике назовем подпиской. Теперь рассмотрим отдельно события. Понятно, что каждый ромбик порождает подписку (или две. По направлению Да/ Нет). И тут же замечаем, что выполнение событий может происходить одновременно на нескольких процессорах, потому как функция E не изменяет состояния. Останется без запуска по событию только самый первый элемент блок-схемы, но это легко лечится придумыванием события Вход.

И тут мы обнаруживаем что полученная блок-схема россыпью может прекрасно работать без линий. Необходимо только вовремя адресоваться к событиям! Ну, тут мы уже быстро соображаем, как с этим справится. Каждой переменной являющейся параметром для логической функции E необходимо поставить подписку на событие изменение значения. Все. Т.е. при изменении значения переменной являющейся параметром логической функции события E запустится проверка этого события. Блок-схема (или то, что было ею) заработает на машине Кузьмина. Рекомендую назвать полученную схему решения задачи А-ритмом.