Сборник методов нейроинформатики

2. Понятие кинетической машины Кирдина

Пусть L–алфавит символов.L^*– множество всех конечных слов или цепочек в алфавитеL. Обрабатываемой единицей является ансамбль словMиз алфавитаL, который отождествляется с функциейF_Mс конечным носителем наL^*,принимающей неотрицательные целые значения –F_M: L^* N  {0}. ЗначениеF_M(s)интерпретируется как число экземпляров словаsв ансамблеM.

Обработка состоит в совокупности элементарных событий, которые происходят недетерминированно и параллельно. Элементарное событие S: MM’состоит в том, что из ансамбляMизымается ансамбльK^–(это возможно, если для всехs ) и добавляется ансамбльK⁺, т.е.. АнсамблиK^–иK⁺однозначно задаются правилами или командами, которые объединяются в программу. Команды могут быть только трех видов:

Пусть u, w, v, f, g, k, q, s– терминальные символы, обозначающие некоторые цепочки символов из L, являющиеся подцепочками слов изL^*.

1. Распад. uvw  uf + gw

где u, w– произвольные,v, f, g– фиксированы. Распад однозначно задается тройкой цепочек(v, f, g). ОбозначимP₁множество таких троек.

При применении этой команды функция F_Mизменит свои значения следующим образом:

F_M’(uvw) = F_M(uvw)–1 ,

F_M’(uf) = F_M(uf)+1 ,

F_M’(gw) = F_M(gw)+1.

Команда распада применима, если F_M(uvw) > 0.

2. Синтез. uk + qw  usw

u, w– произвольные,k, q, s– фиксированы. Синтез однозначно задается тройкой цепочек(k, q, s).ОбозначимP₂множество таких троек.

При применении этой команды функция F_Mизменит свои значения следующим образом:

F_M’(uk) = F_M(uk)–1 ,

F_M’(qw) = F_M(qw)–1 ,

F_M’(usw) = F_M(usw)+1.

Команда синтеза применима, если F_M(uk) > 0, F_M(qw) > 0.

3. Прямая замена.uvw  usw

u, w– произвольные,v, s– фиксированы. Прямая замена однозначно задается парой цепочек(v, s). ОбозначимP₃множество таких пар.

При применении этой команды функция F_Mизменит свои значения следующим образом:

F_M’(uvw) = F_M(uvw)–1 ,

F_M’(usw) = F_M(usw)+1.

Команда прямой замены применима, если F_M(uvw) > 0.

Программа P применимак ансамблюM, если хотя бы одна его команда применима кM. ПрограммаP однозначно определяется множествамиP₁_,P₂иP₃.

Таким образом, элементарное событие Sоднозначно определяется правилом p, содержащимся в списке команд программыP, и ансамблемK^–, определяемым этим правилом, таким, чтоF_K^–(s)F_M(s)для любогоs.Допустимоеэлементарное событиеSдля ансамбляMи программыP– это такое, для которого существует правилоp, содержащeeся в списке команд программыP, и значения функцииF_Mдля слов, стоящих в левой части этого правила, положительны.

Скажем, что Nдопустимых событийсовместны, если, где– изымаемый ансамбль дляi-го события.

Ансамбль Mявляетсяфинальным для данной программыP, если никакая команда программы к нему не применима.

Программа P называетсяфинитнойдля данного ансамбляM, если, применяя к нему команды программы в любом порядке, пока это возможно, мы обязательно получим некоторый финальный ансамбль.

Программа Pявляетсядетерминированной для ансамбляM, если все финальные ансамбли совпадают.

Ансамбль Mбудем называть«райским садом»для программыP, если он не может быть получен ни из одного ансамбля применением программыP.

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

Содержание