Финитность и детерминированность простых программ для кинетической машины Кирдина

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

Содержание:

1. Введение
2. Понятие кинетической машины Кирдина
3. Модели выполнения программы
4. Программы, состоящие из одной команды
5. Заключение