О формальных моделях компьютеров и вычислений

Оглавление
0 Введение 4
0.1 Актуальность темы исследования............................. 4
0.2 Цель и задачи работы...................................... 13
0.3 Содержание диссертационной работы......................... 17
0.4 Основные используемые понятия и обозначения............... 33
1 Универсальные матпипы Тьюринга 37
1.1 Эквивалентность определений УМТ........................... 37
1.2 Ограничения для машин Тьюринга и универсальность ... 41
1.3 Общие принципы построения УМТ, моделирующих таг-системы ..................................................... 50
1.4 УМТ с 22 состояниями и 2 символами ...................... 54
1.5 УМТ с 10 состояниями и 3 символами....................... 57
1.0 УМТ с 7 состояниями и 4 символами....................... 59
1.7 УМТ с 5 состояниями и 5 символами....................... 61
1.8 УМТ с 4 состояниями и б символами....................... 65
1.9 УМТ с 3 состояниями и 10 символами...................... 69
1.10 УМТ с 2 состояниями и 18 символами...................... 72
2 Проблема бессмертия для машин Тьюринга 77
2.1 Проблема бессмертия для классов ТМ и РМ.................. 78
2.2 Проблема бессмертия для класса СМ........................ 93
2.3 Униформная проблема остановки............................. 96
2.4 Униформная проблема остановки для класса IIМ..............103
3 Бпомолекулярные вычисления на базе .чрПст^-опораций 114
3.1 Определения и основные понятия............................114
3.2 Пример....................................................117
3.3 3-И имитируют любую грамматику............................119
3.4 Расширенная З-И может порождать любой «чистый» формальный язык ................................................123
3.5 Универсальная расширенная 3-Н система.....................126
3.6 ТУБЫ системы степени 2 порождают любой рекурсивно перечислимый язык............................................130
2
3.7 Универсальная ТХ'ОН система степени 2 137
4 Заключение I44
5 Рисунки 148
6 Ссылки 153
3
О Введение
0.1 Актуальность темы исследования
Создание и изучение различных формальных моделей компьютеров и вычислительных алгоритмов очень важно для понимания истинной природы вычислений. Новые подходы для построения будущих компьютеров (таких как квантовые, генетические, молекулярные или какие либо другие) могут возникнуть из этого анализа. Исследование ограничений этих формальных моделей есть хороший способ понимания возможностей современных и будущих компьютеров.
Открытие, что имеются универсальные компьютеры, которые в принципе очень просты, является базисом компьютерной теории и практики. В данной работе представлен ряд теоретических моделей компьютеров: классическая модель - машины Тьюринга, и современные модели биомолекул ярного компьютера, основанные на врНо-шй-операциях.
Одна из первых теоретических моделей компьютера была предложена в 1936 году А.Тьюрингом [84], одним из основателей информатики и вычислительной техники. Она называется, в его честь, (одноленточной) машиной Тьюринга, или короче МТ, и является базовой для других моделей компьютеров и вычислений. Основная причина такого огромно1ч> значения этой модели заключается в ее простоте, элегантности и гибкости, и в том факте, что шаг вычисления машиной Тьюринга элементарен как с операционной, так и с коммуникационной точек зрения.
То, что возможно построить конкретную машину Тьюринга, которая при подходящем кодировании может выполнить работу любой другой машины Тьюринга, является одним из основных результатов информатики и вычислительной техники. Универсальная машина, построенная Тьюрингом, содержала несколько сот команд.
Поиски универсальной машины Тьюринга минимального размера начались с работы Клода Шеннона [83] в 1956 году. С тех пор многими учеными делались попытки построить минимальные универсальные машины Тьюринга, поскольку это представляет определенный теоретический и практический интерес. Основными мотивами здесь были следующие: научный интерес, поиск принципов, обуславливающих мощь гене-
4
тических информационных процессов, также стремление к минимизации размера и повышению производительности компьютеров.
Мы рассматриваем обычные детерминированные одноголовочные машины Тьюринга с одной одномерной бесконечной в обе стороны лентой. Как уже говорилось, в 1956 году Клод Шеннон сформулировал проблему построения минимальной универсальной машины Тьюринга и в качестве меры сложности предложил использовать произведение тп числа т состояний и числа п символов машины Тьюринга (т.е. максимально возможное количество команд в программе машины Тьюринга). Возможно также в качестве меры сложности рассматривать число команд, реально ис пользуемых в программе машины Тьюринга.
В литературе имеется несколько различных вариантов определения универсальной машины Тьюринга (в дальнейшем кратко УМТ) (А.Нозаки [65], М.ДэвиС [о, 38], А.И.Мальцев [8], М.Минский [64, 13], X.Роджерс [77] и ряд других).
Эти варианты характеризуют два различных подхода в определении понятия УМТ, которые можно назвать «функциональным» (универсальная машина - это такая машина, которая способна вычислять любую частично рекурсивную функцию) и «имитационным» (универсальная машина - это такая машина, которая способна моделировать работу любой машины Тьюринга, или нормального алгорифма Маркова, или таг-системы, или других подобных алгоритмических систем). Отметим, что мы не рассматриваем «нетрадиционные» варианты определения УМТ, например с «динамическим остановом» (т.е. «универсальные» машины, которые не останавливаются в процессе работы, а результат считывается с ленты в случае выполнения некоего условия для последовательных конфигураций машины), а также определения, допускающие построение «универсальной» машины, результатом работы которой может быть конечное множество значений. В диссертации устанавливается эквивалентность соответствующих этим подходам определений УМТ. Отметим также, что доказательство этого результата достаточно просто, а сам результат характеризует позицию, занимаемую автором в вопросе определения понятия УМТ.
В середине 60-х годов П.Фишер [42] и С.Аандераа [30] изучали возможность существования универсальных машин Тьюринга в зависимости от
5
ограничений, накладываемых на операционные возможности и на мощности алфавита символов и алфавита состояний машин Тьюринга.
Машина Тьюринга может за один такт выполнить три операции:
а - записать в рассматриваемую ячейку новый символ (может быть тот же самый),
<)' - сдвинуть головку на одну ячейку ленты вправо, влево или оставить ее на месте,
</ перейти в новое состояние (может быть то же самое).
Пусть Х,У 6 {«,<$,<?}• ХУ обозначает, что за один такт могут выполняться операции X и У, X V У обозначает, что за один такт могут выполняться операции X или У (одновременно выполняться они не могут). Тогда, например, да V ад обозначает, что за один такт машина может либо записать символ и перейти в новое состояние, либо записать символ и сдвинуть головку. Определим следующие классы машин Тьюринга:
тм - qaS
FM - qa V qS V аб
SM - да V аб
DM - gS V аб
РМ - qa V дб
AM - gVaS
ВМ - да V 5
СМ - qS V а
им - q V а V 6
Указанными классами исчерпываются все возможности (мы не рассматриваем классы таких машин Тьюринга, которые не могут выполнить хотя бы одну из трех операций а, 6 или q). Классы SM, DM и UM были введены П.Фишером, классы AM, ВМ, СМ и FM введены автором. Соотношения между этими классами показаны на Рис.1. Обозначим иерархию этих подклассов машин Тьюринга как ТТМ (formalisms for Turing machines).
Класс TM - это класс обычных машин Тьюринга, класс РМ, известный также под названием машины Поста, это подкласс машин Тьюринга,
6
которые за один такт работы не могут одновременно выполнить операции а и г5, то есть записать символ и сдвинуть головку. Машины Поста, наряду с машинами Тьюринга, широко используются в литературе по теории алгоритмов и информатике. Класс ОМ - это подкласс машин Тьюринга, которые не могут одновременно выполнить операции q и а. Класс 5Л/ - это подкласс машин Тьюринга, которые не могут одновременно выполнить операции д и Л. Класс ОМ - это подкласс машин Тьюринга, которые за один такт работы выполняют только одну из трех операций о, ц или 6.
Классы ЯЛ/, АМ, ВМ и СМ - это промежуточные классы, которые позволили автору дополнить и завершить иерархию ТТАЛ.
К.Шенноном было показано, что существуют универсальные машины как в классе ТМ с 2 состояниями, так и в классе ГМ с 2 символами (известно также, что УМТ с одним состоянием быть не может, как не может быть УМТ с одним символом). Обозначим этот факт как ТМ(2,2). Первый аргумент в пыражении ТМ(2,2) обозначает минимальное число состояний универсальной машины в классе ТЛ/, второй аргумент - минимальное число символов универсальной машины в этом же классе.
С.Аандераа, П.Фишер и П.Хупер показали, что имеет место РМ(3,2), ОМ(2,2) и 8М(2,3). Здесь представляется важным тот факт, что запрет на одновременное выполнение операций а и 6 влечет невозможность построения УМТ с 2 состояниями, а запрет на одновременное выполнение операций ц и 6 - невозможность построения УМТ с 2 символами.
Автору удалось показать, что можно построить универсальную машину как в классе ИМ с 3 состояниями, так и в классе 1/М с 3 символами, т.е. показать иМ(3,3). Все известные и полученные автором результаты суммированы на Рие.2.
Далее будем рассматривать вопрос о существовании универсальных машин в зависимости от числа символов и числа состояний в классе ТМ.
Пусть ЫТМ{т,п) будет класс универсальных машин Тьюринга с т состояниями и п символами.
Универсальные машины Тьюринга можно строить различными способами, в частности напрямую имитируя другие машины Тьюринга. Однако последний способ требует сложного кодирования и декодирования программы машины Тьюринга и, соответственно, объем программы
7
универсальной машины, полученный таким образом, будет значителен (см. например, С.Ватанабе [4]). М.Минский предложил в качестве очень простого базиса для вычислимости использовать таг-системы и им была построена УМТ с 7 состояниями и 4 символами, которая имитировала таг-системы.
УМТ, построенная М.Минским в классе ЫТМ(7,4), имела неразрешимую проблему остановки, но имела также серьезный недостаток, который был отмечен автором диссертации в 1981 году: эта машина перед остановкой повреждала выходной результат на ленте (восстановить невозможно).
Р.Робинсон (76] в 1991 году также отметил этот дефект универсальной машины Минского и предложил свой правильный вариант универсальной машины в классе UTМ (7,4).
Автором метод Минского построения универсальных машин с помощью моделирования таг-систем усовершенствован и освобожден от вышеупомянутого недостатка, что и позволило построить наименьшие по объему из известных универсальные машины Тьюринга.
Это универсальные машины в классах UTМ(22,2), ИТМ( 10,3), UTM{7,4), ЫТМ(5,5), ЫТМ{4,б), ЫТМ{3,10) и UTM{2,18).
Р.Робинсон рассматривал также число команд, реально используемых в программе машины Тьюринга. Его универсальная машина в классе UTМ{7,4) использовала 27 команд, в то время как аналогичная машина автора использует 26 команд. Отметим также, что представленные автором универсальная машина в классе £/ТЛ4(5,5) использует 23 команды, а универсальная машина в классе ЫТМ{А, 6) использует 22 команды, что является наименьшим из известных в настоящее время числом команд универсальной машины Тьюринга.
Л.М.Павлоцкой [14,15] показано, что в классах UTМ (3,2) nUTM(2,3) универсальных машин не существует. Используя другие методы В.Дейкерт, М.Кудлек [40] и М.Кудлек [54] установили аналогичный результат для класса ЫТМ{2,2).
Из полученных автором результатов и из результатов Л.М.Павлоцкой следует, что не исследованными на универсальность (т.е. пуст или нет данный класс) осталось 49 классов UTM(m,n) (см. Рис.З).
Отметим также, что поиски универсальных минимальных по объему
S
алгоритмов ведутся также в других алгоритмических формализмах.
Например, П.Хупер [48] построил универсальные машины Тьюринга с 2 состояниями 3 символами и 2 лентами, а также с 1 состоянием, 2 символами и 4 лентами. Л.Призе [73] рассматривал задачу Шеннона для т.н. двумерных машин Тьюринга, а М.Марженстерн [55] - для т.н. нестирающих машин Тьюринга. Результаты по малым регистровым машинам представлены И.Кореи [52]. Хорошие обзоры по данной проблематике были опубликованы М.Марженстерном [56, 58]. Обзор по универсальным полиномам представлен Ю.В.Матияссвичем [63].
Формальные модели компьютеров и вычислений предоставляют возможность исследовать проблему сложности вычислений, которая составляет одну из важнейших проблем информатики (см. Д.Сэвидж [28], а также другие важные проблемы, которые возникают естественным образом при исследовании абстрактных компьютеров.
Одними из таких проблем являются проблема бессмертия (immortality problem) и униформная проблема остановки (uniform halting problem) для машин Тьюринга, характеризующие одно из свойств абстрактного компьютера - а именно, имеется или не имеется у него входной набор данных, на которых он работает вечно. Алгоритмическая неразрешимость этих проблем для машин Тьюринга (для класса ТМ) была установлена соответственно П.Хупером [47] и Г.Германом [46].
Сформулируем эти проблемы. Пусть проблема бессмертия кратко обозначается как ПБ, а униформная проблема остановки как УПО. Предварительно приведем несколько определений.
Конфигурацией машины Тьюринга называется совокупность, образованная последовательностью символов, содержащихся в ячейках ленты МТ, состоянием, в котором находится МТ, и номером (или положением на ленте) рассматриваемой ячейки.
Конфигурация бессмертна если, начиная с нее работу, машина Тьюринга никогда не остановится.
Конфигурация может быть как бесконечной, так и конечной. В последнем случае вся лента машины Тьюринга, за исключением конечного числа ячеек, пуста.
В формулировке проблемы бессмертия конфигурация может быть как конечной, так и бесконечной. Если ограничиться только конечными кон-
9
фигурациями, то ПБ получает название - униформная проблема остановки (У ПО).
ПБ формулируется так: дать разрешающую процедуру (алгоритм), котором по любой данной машине Тьюринга позволяет ответить на вопрос, имеет или не имеет ота машина бессмертную конфигурацию.
П.Хупер, Г.Герман и В.Тлюстен [29] изучали ПБ и У ПО для классов 5М, ОМ, РМ и иМ в зависимости от мощности алфавита символов и алфавита состояний. Автором это изучение было продолжено (также и для оставшихся классов РМ, ЛМ, РМ и СМ иерархии ТТМ) и полностью завершено для ПБ (см. Рис.4).
Отметим, что результат автора о разрешимости ПБ для класса машин Поста (РМ) с тремя состояниями является в какой-то степени неожиданным, а результат автора ОМ (4,2) означает, что П.Хупер допустил неточность, когда он утверждал, что ПБ разрешима для класса всех ОМ.
Результаты для УПО отражены на Рис.5. Отметим, что автором совместно с Н.Пукаловой было показано, что УПО неразрешима для машин из класса Г/А/ с 4 символами (тем самым было показано, что УПО неразрешима для всего класса ОМ), однако, как показано автором, УПО для машин из класса ОМ с 2 символами разрешима. Вопрос, разрешима или нет УПО для машин из класса ИМ с 3 символами, остается открытым. Сравнение с Рис.2 позволяет высказать Предположение, что результаты для УПО. так же как и результаты об универсальности, могут быть следующие: ВМ(З.З) и 11М(3,3).
Молекулярные вычисления, известные также под именами бномоле-кулярные вычисления, биовычисления или ДНК-вычисленпя, являются новым подходом к вычислениям и используют биомолекул я рные операции для решения вычислительных проблем. Первые успешные эксперименты в этом направлении были проведены Л.Адлеман (31, 32] в решении задачи нахождения гамильтонова пути в графе. Основная идея заключалась в кодировании данных последовательностями ДНК, и применения к ним технологии молекулярной биологии для выполнения вычислительных операций. Как показали первые эксперименты и теоретические исследования, молекулярные вычисления обладают большим потенциалом,
10
чтобы превзойти вычисления на обычных электронных компьютерах. Ожидается, что для определенного класса задач (которые хорошо распараллеливаются), ДНК-компьютеры будут иметь огромное преимущество по сравнению с кремниевыми с точки зрения скорости, энергетической эффективности и экономного хранения информации (Lila Kari [49, 50]).
Однако, несмотря на достигнутый прогресс, существуют серьезные препятствия различного рода (технологические, теоретические) на пути создания реального биокомпьютера. Поэтому, гак как исследования в этом направлении только начаты, они проводятся в двух направлениях:
(а) исследование различных технологий молекулярной биологии для вычислительных целей,
(б) нахождение удобных формальных моделей для биовычислений.
В последнем направлении разрабатываются формальные модели и дается их математическое обоснование (например, способность осуществлять универсальные вычисления или порождать любой рекурсивно перечислимый язык), а также разрабатываются молекулярные алгоритмы решения известных трудных задач (например, ограниченной проблемы соответствия Поста, проблемы выполнимости для булевских формул и
др.).
В своей статье Т.Хед [44] описал связи между молекулярными вычислениями и теорией формальных языков. Т.Хед рассматривал молекулы как слова над некоторым конечным алфавитом и энзимы как splicing-правила. Splicing-правила могут применяться к двум молекулам. Обе молекулы разрываются в определенных фиксированных местах, определяемых splicing-правилами и рекомбинируются (соединяются), причем начальный отрезок одной молекулы - с оставшимся отрезком другой молекулы. Идеи Т.Хеда привлекли внимание многих ученых, занимающихся теорией формальных языков. Так, например, Г.Пэун, Г.Розенберг, А.Саломаа [69] задались вопросом, какие классы формальных языков порождаются молекулярными компьютерами, где первоначальные молекулы и энзимы из заданных классов формальных языков. Е.Ксухаж-Варжу, Л.Кари, Г.Пэун [37] модифицировали концепцию Т.Хеда и предложили систему п test-tube, кратко n-tt (другое название - communicating distributed Н systems). Здесь любой test-tube есть Head-система (11-система) с дополнительным фильтром. За один макро-шаг работы ка-
11
ждый test-tube порождает новые молекулы согласно его стартовым молекулам и его множеству splicing-правил. После этого, результаты каждого test-tube проходят через фильтры остальных test-tube. Те молекулы, которые смогли пройти через фильтр test-tube і, 1 < і < п, образуют новые стартовые молекулы для /-того test-tube для следующего макро-шага.
Этот новый процесс, фильтрующий результаты одного test-tube в другой, увеличивает вычислительные возможности молекулярного компьютера. Назовем n-tt систему конечной, если первоначально каждый test-tube содержит (бесконечно много) копий молекул из конечного множества молекул и обладает только конечным набором splicing-правил. Известно, что конечные І-tt системы порождает только регулярные множества молекул [71]. Тем не менее, конечная 2-й система может порождать не регулярные множества молекул. К.Феррстти, Ж.Маури, К.Зандрон [41] показали, что любое рекурсивно перечислимое множество молекул порождается соответствующей конечной 9-tt системой (или конечной 6-tt системой, если допустить простое кодирование порожденных молекул). Заметим, что эти авторы улучшили свой результат [86], где они показали, что любое рекурсивно перечислимое множество молекул порождается соответствующей конечной 10-tt системой.
Напомним, что проблема вхождения неразрешима для рекурсивно перечислимых языков. Это означает, что не существует алгоритма Л, который по любому данному слову ю и по данному языку L отвечает на вопрос, принадлежит ли слово w языку L или нет. Более того, существует фиксированный язык U, такой, что не существует алгоритма Л, который по любому слову w отвечает на вопрос, будет ли w элементом U или нет. Так, тривиальное следствие из этого результата следующее: не существует алгоритма, который может вычислить, какие молекулы порождаются конечной б-lt системой. Т.е. результаты конечной б-tt системы не могут быть алгоритмически предсказаны (определены). Автором совместно с М.Марженстериом (Франция) и Л.Призе (Германия) упомянутые выше результаты были существенно улучшены и было показано, как порождать любой рекурсивно перечислимый язык в конечной расширенной З-tt системе (или в конечной 4-tt системе), а также, как построить конечную универсальную расширенную З-tt систему. Вопросы «Существует ли конечная универсальная 2-tt система?» и «Могут ли ко-
12
нечные 2-tt системы порождать любой рекурсивно перечислимый язык?» остаются открытыми (известно однако, что конечные i-tt системы порождают только регулярные языки).
Отметим, что позже Г.Пэун [68] представил другое доказательство этого результата. Его работа содержит также хороший обзор по данной проблематике.
Другая модификация бнокомпьютера на основе splicing-операций была предложена Г.Пэуном [67] - это так называемые time-varying distributed Н systems (degree n, n > 1) - в дальнейшем TVDH-смстемы степени п, п > 1.
TVDH-сигтема степени n, n > 1 есть splicing система, которая имеет специальные свойства: в различные моменты времени она использует различные множества splicing-правил (эти множества правил называются степенями TVDH-системы). Переход от одного множества правил к другому цнклнчен. Г.Пэун показал, что любой рекурсивно перечислимый язык может быть порожден TVDH-системой степени не менее, чем 7. Автором совместно с М.Марженстерном этот результат был существенно улучшен и было показано, как с помощью TVDH-систем степени не менее, чем 2, порождать любой рекурсивно перечислимый язык, а также как строить универсальную TVDH-снстсму степени не ниже, чем 2.
Вопросы «Возможно ли построить универсальную TVDH систему степени 1?» и «Могут ли TVDH системы степени 1 порождать любой рекурсивно перечислимый язык?», остаются открытыми.
0.2 Цель и задачи работы
Основной целью работы является исследование понятия универсального алгоритма, нахождение ограничений формальных моделей вычислительных алгоритмов (универсальность/нсуниверсальность, разрешимость / неразрешимость), для лучшего понимания возможностей реальных и будущих компьютеров (в частности, бномолекулярных компьютеров). В работе ставились следующие задачи:
Рассмотреть различные определения универсальной машины Тьюринга и предложить обобщающее определение этого понятия.
13
- Исследовать возможность существования универсальных машин Тьюринга в зависимости от ограничений, накладываемых на операционные возможности и на мощности алфавита символов и алфавита состояний машин Тьюринга, дополнить и логически завершить иерархию подклассов машин Тьюринга, предложенную P.Fischer.
Модифицировать способ М.Минского построения малых универсальных машин Тыоринга с целью освобождения его от недостатков (приводящих к построению УМТ, которая «портит» результат) и с целью построения УМТ с наименьшим количеством команд.
- Пост1>оить наименьшие по объему (т.е. по количеству команд) универсальные машины Тьюринга.
- Решить проблему бессмертия для различных подклассов машин Тьюринга.
- Решить униформную проблему остановки для класса VМ, подкласса машин Тьюринга, которые могут за один такт работы выполнить только одну из трех микроопераций машины Тьюринга.
- Исследовать формальные модели биомолекулярного компьютера: Н-системы с тремя test-tube и TVDH-системы с двумя компонентами, показать их способность проводить универсальные вычисления или порождать любое рекурсивно перечислимое множество.
Методы исследования Для достижения цели работы и решения поставленных задач использовался аппарат математической логики, теории графов, теории формальных языков, теории алгоритмов, а также компьютерное моделирование.
Научная новизна Все основные результаты диссертации являются новыми и опубликованы в работах автора. В диссертации получены следующие основные результаты:
1) предложено обобщающее определение понятия универсальной машины Тьюринга;
14