Новая редакция
Старую редакцию см. здесь.
Машина Кузьмина. (Управляемая недетерминированная машина Тьюринга) Раcсчитывая, что читатель знаком с МТ, оформим описание останавливаясь на отличиях предлагаемой машины от МТ.
Машина Кузьмина представляет собой перечислимое множество ячеек (концептов) и перечислимое множество управляющих устройств (можно считать их головками, кому это удобно) назначение которых – адресация (активация) концептов. Номер концепта будем называть адресом.
Ячейка (а не головка как у МТ) имеет множество состояний S (возможно бесконечное). Пока событием будем называть состояние концепта. Это не противоречит интуитивному представлению о событии как о процессе изменения состояния потому что факт изменения состояния определяется анализом на принадлежность новому состоянию (истинность события), и зачастую событие имеет имя этого нового состояния.
Каждое событие может иметь конечное множество подписок. Подписка — номер концепта к которому осуществляется переход управляющего устройства и при условии истинности события, которому принадлежит подписка.
Работа машина заключается в адресации (активации) концепта. При активации концепта, запускается анализ на истинность всех событий концепта (анализ не изменяет состояние концепта и потому может выполняться одновременно для всех событий) имеющих подписки, и при истинности этих событий машина активирует концепты с номерами, указанными в подписках (одновременно, если истинных событий с подписками больше одного). При отсутствии подписок адресация выполняет предназначенную функцию в зависимости от вида адресации (чтение-запись-выполнение-инициализация). На чем работа и заканчивается.
Виды адресацииАдресация имеет 4 вида:
1. Адресация для чтения. Читает значение концепта. Генерирует событие «Чтение»
2. Адресация для записи. Записывает новое значение. Генерирует событие «Запись»
3. Адресация для выполнения. Генерирует событие «Выполнение»
4. Адресация для инициализации. Генерирует события «Инициализация» и «Выполнение».
Архитектура компьютераРеализация машины представляет собой почти классическую архитектуру с несколькими шинами адресации, и несколькими процессорами. Шины адресации реализуют кроме классических адресаций для чтения/записи/выполнение еще и инициализацию. Т.е. создание новых концептов.
Шины адресации перед активацией, формируют собственный стек для параметров и динамических переменных. Каждый процессор при запуске формирует собственный стек, и имеет собственные регистры.
Память представлена не массивом ячеек стандартного размера, а множеством концептов единой структуры. Графически содержимое такой машины можно представить графом с концептами-вершинами и ребрами-подписками. (А-ритм)
В чем отличие?Отличие становиться заметным, когда мы обращаем внимание на то, что у нас много процессоров и шин адресации.
В классической архитектуре программа выполняется так, как пишется. Последовательность операторов О1, О2…. Оn. которые изменяют состояние. Затем оператор If- анализирующий текущее состояние и переход в зависимости от текущего состояния.
У нас же переход осуществляется непосредственно в момент изменения состояния. И последовательность выполнения операторов зависит не от их порядка в тексте, а в порядке указанном парой событие – подписка.
Т.е. обычную программу можно представить в виде алгоритма (или блок-схемы) выполняющейся пошагово. Т.е. одним исполнителем.
Работу предложенной машины можно представить алгоритмом выполняемым несколькими исполнителями.
В общем случае одновременно могут происходить переходы по нескольким подпискам по нескольким событиям, что порождает недетерминизм и двусмысленность в определении алгоритма как порядка или последовательности выполнения.
О каком порядке и последовательности может идти речь при ОДНОВРЕМЕННОМ процессе. В общем случае МК гарантирует только порядок выполнения пары событие-подписка и назовем такую модель выполнения А-ритмом.
Объявление события перечислением.
Объявление событий эквивалентно определению множеств состояний. Перечислимые типы таким образом перечислением значений одновременно определяют и одноименные события. Перечислимые типы определяются группой концептов, имя каждого из группы представляет концепт в группе и хранится как индекс этого концепта в группе.
Если концепты в группе –значения, то имя концепта имеет еще два смысла. В операторах как значение концепта с индексом, а при формировании подписки обозначают событие, заключающееся в равенстве переменной этому значению. Рассмотрим на примере определения типа Boolean.
Boolean Определим тип Boolean как именованную группу (имя группы непосредственно после открывающей скобки без пробела) из двух концептов типа токен (4 разряда) с именами "!" и "¬" и значениями 0 и 1:
{Boolean Token {"!" 0 #True.» "¬" 1 #False. »}}
Теперь для переменной F определенной ниже с начальным значением -!
Boolean F ! #Определение переменной типа Boolean и присвоение значения Истина. »
Формирование подписки на событие True.
F ! ((a +b) (F= ¬)) #По значению истина складываем a +b. И присваиваем значение False.»
Аналог оператора If:
F {! a+b ¬ a-b) #По значению истина складываем a+b. Иначе a-b.»
Знаки «!» и « ¬»являются значениями в операторе и событием.
Так же с помощью группы определим события, заложенные в архитектуре машины.
Определение событий адресации. Класс «|»Event "|" Token { "←" 0 #Запись» "→" 1 #Чтение» "|" 2 # Выполнение» ":" 3 #Инициализация» }
Compare
{Compare Token { "=" 0 #Равно»">" 1 #Больше.» "<" 2 #Меньше.» }}
Определение событий данных. Класс «:» Event ":" Token {"_" 0 #Отсутствует значение.» "=" 1 # Ноль» ">" 2 # Положительное.»
"<" 3 #Отрицательное.» Even 4 #Четное» Uneven 5 #Не четное» "~" 6 #Изменение значения.» }
События, определяемые перечислимыми типами, определяют синтаксис объявления событий, и это первый шаг в понимании.
Прошу прощения за неаккуратность в форматировании.
Более подробно можно посмотреть в ролике здесь
https://www.youtube.com/watch?v=-ftPk409-6U Там же введение в программирование недетерминированной машины. И попытка объяснить разницу между блок схемой и А-Ритмом.
А здесь методы мышления в программировании.
https://www.youtube.com/watch?v=iX7_JU2OTlI
Вход
FAQ
Поиск
