Объектно-транзакционные модели программ на алгоритмических языках

Данная работа посвящена вопросу представимости программ, написанных на алгоритмических языках, с помощью формализмов, базирующихся на идее применения предельной частично транзакционной памяти, включающей единственную транзакционную ячейку и множество обычных ячеек. При этом предполагается, что такие формализмы основаны на понятии сети объектов, представляющих как основные, так и вспомогательные элементы решающей задачи. Объекты функционируют в памяти указанного вида, выполняя методы, содержащие исключительно ветвящийся код, лишенный циклов. Циклы при таком подходе заменяются многократным специальным пересогласованием сети объектов, схожим с реализованным в классической транзакционной памяти. Исходя из самых общих представлений о процессе решения задачи в некоторой предметной области, впервые вводится концепция объектно-транзакционной модели и формулируются их основные свойства. При формулировании структуры и основных принципов функционирования объектно-транзакционных моделей используются методы дискретной математики, теории алгоритмов. Вводится понятие предельной частично транзакционной памяти, содержащей единственную транзакционную ячейку со специальным согласованием. Описываются особенности согласования такой памяти в контексте предлагаемых моделей. Выдвигается гипотеза о реализуемости произвольных алгоритмов с помощью объектно-транзакционных моделей. Описаны основные принципы функционирования таких моделей, сформулированы их основные свойства. Вводятся понятия предельных непараллельной и параллельной моделей. Доказывается, что предельная непараллельная модель способна выполнить произвольный разрешимый по Тьюрингу алгоритм. Доказывается, что предельная параллельная модель из K+2 узлов эквивалентна системе из K параллельно работающих машин Тьюринга и, соответственно, способна выполнить произвольный разрешимый по Тьюрингу алгоритм, подразумевающий наличие K параллельных ветвей. Таким образом, выдвинутая в работе гипотеза о реализуемости произвольных алгоритмов доказана.

последовательный алгоритм, модель программы, транзакционная память, специальное согласование, предельные теоремы, объектно-транзакционная модель, машина Тьюринга, теория, параллельный алгоритм, реализуемость алгоритмов