Машина Кузьмина. (Управляемая недетерминированная машина Тьюринга.)
Введение.
Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
Это отсюда.
https://ru.wikipedia.org/wiki/%D0%9C%D0 ... 0%B3%D0%B0Развитие компьютерных технологий, современные требования к их применению, развитие программирования. появление реактивного программировани, да и сама физическая модель мира уже не удовлетворяются возможностями алгритмов по причине требований параллельной работы, содержанием которой не обязательно являются вычисления, может быть анализ данных или моделирование и управление реальными объектами как в автоматике. Кстати, именно в этой, наиболее развивающейся отрасли проблема с новыми парадигмами. Императивная явно не справляется. Ибо для управления объектами надо не только командовать (императивить), но и «слушать».
Устройство машины Тьюринга.
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки[2][3], и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
Устройство машины Кузьмина.
Начнем по порядку описания МТ останавливаясь на отличиях.
1. Лента конечна. Это ближе к жизни. Разделение ленты назовем не ячейками, а концептами.
2. Управляющее устройство назовем адресацией. Т.е. у нас несколько головок (шин адресации) каждая из которых может иметь 4- вида адресации к концептам. Виды адресации –чтение, запись, выполнение, инициализация. Каждый вид адресации имеет в себе составную часть-просто адресацию.
3. Состоянием обладает не головка, а концепт. Кроме того, вместо понятия «состояние» иногда будем применять понятие «событие». Ибо событие это переход из одного состояния в другое и обычно именуется по названию нового состояния. Исходя их этого можем отметить сразу 5 событий концептов- адресация, адресация для чтения, адресация для записи, адресация для выполнения, адресация для инициализации. Число возможных состояний ограничено 16 классами. Список классов событий ниже .
4. Устройство может перемещаться (адресоваться) к любому концепту и могут порождается подписками, как и концепты могут порождаться адресацией с инициализацией. По выполнению адресации устройство освобождается.
5. Работа машина заключается в адресации концепта и, возможно, изменения состояния адресуемого концепта. На этом функция головки завершается.
6. Каждый концепт может иметь подписки на события. Подписка это адрес (адреса, потому как может быть несколько подписок на одно событие) к которому необходимо перейти каким то видом адресации при определенном событии.
7. Функционирование машины заключается в адресации концептов, которые остаются неизменными.
8. Управление конкретной машиной осуществляется добавлением/удалением подписок.
9. Программирование заключается в создании множества концептов и оформлении подписок для необходимого функционала.