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

• Автор: Рогожин, Юрий Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 160 с. : ил.

Оглавление
0 Введение
0.1 Актуальность темы исследования
0.2 Цель и задачи работы
0.3 Содержание диссертационной работы
0.4 Основные используемые понятия и обозначения
1 Универсальные машины Тьюринга
1.1 Эквивалентность определений УМТ
1.2 Ограничения для машин Тьюринга и универсальность
1.3 Общие принципы построения УМТ, моделирующих таг-
системы
1.4 УМТ с 22 состояниями и 2 символами
1.5 УМТ с 10 состояниями и 3 символами
1.6 УМТ с 7 состояниями и 4 символами
1.7 УМТ с 5 состояниями и 5 символами
1.8 УМТ с 4 состояниями и 6 символами
1.9 УМТ с 3 состояниями и 10 символами
1.10 УМТ с 2 состояниями и 18 символами
2 Проблема бессмертия для машин Тьюринга
2.1 Проблема бессмертия для классов ТМ и РМ
2.2 Проблема бессмертия для класса СМ
2.3 Униформная проблема остановки
2.4 Униформная проблема остановки для класса Х]М
3 Биомолекулярные вычисления на базе эрНсп-операций
3.1 Определения и основные понятия
3.2 Пример
3.3 3-Ы имитируют любую грамматику
3.4 Расширенная З-Ы может порождать любой «чистый» формальный язык
3.5 Универсальная расширенная 3-Ц система
3.6 ТУБН системы степени 2 порождают любой рекурсивно
перечислимый язык

3.7 Универсальная ТТ)Н система степени

4 Заключение
5 Рисунки
6 Ссылки

О Введение
0.1 Актуальность темы исследования
Создание и изучение различных формальных моделей компьютеров и вычислительных алгоритмов очень валено для понимания истинной природы вычислений. Новые подходы для построения будущих компьютеров (таких как квантовые, генетические, молекулярные или какие либо другие) могут возникнуть из этого анализа. Исследование ограничений этих формальных моделей есть хороший способ понимания возможностей современных и будущих компьютеров.
Открытие, что имеются универсальные компьютеры, которые в принципе очень просты, является базисом компьютерной теории и практики. В данной работе представлен ряд теоретических моделей компьютеров: классическая модель - машины Тьюринга, и современные модели биомо-лекулярного компьютера, основанные на эрЦс-операциях.
Одна из первых теоретических моделей компьютера была предложена в 1936 году А.Тьюрингом [84], одним из основателей информатики и вычислительной техники. Она называется, в его честь, (одноленточной) машиной Тьюринга, или короче МТ, и является базовой для других моделей компьютеров и вычислений. Основная причина такого огромного значения этой модели заключается в ее простоте, элегантности и гибкости, и в том факте, что шаг вычисления машиной Тьюринга элементарен как с операционной, так и с коммуникационной точек зрения.
То, что возможно построить конкретную машину Тьюринга, которая при подходящем кодировании может выполнить работу любой другой машины Тьюринга, является одним из основных результатов информатики и вычислительной техники. Универсальная машина, построенная Тьюрингом, содержала несколько сот команд.
Поиски универсальной машины Тьюринга минимального размера начались с работы Клода Шеннона [83] в 1956 году. С тех пор многими учеными делались попытки построить минимальные универсальные машины Тьюринга, поскольку это представляет определенный теоретический и практический интерес. Основными мотивами здесь были следующие: научный интерес, поиск принципов, обуславливающих мощь гене-

Функция / называется частично рекурсивной, если (1) это есть базовая функция, (и) получается в результате операции композиции из частично рекурсивных функций, (ш) определяется рекурсивной схемой из частично рекурсивных функций, (гу) определяется операцией минимизации из всюду определенной частично рекурсивной функции.
Напомним, что всюду определенная частично рекурсивная функция является общерекурсивной (рекурсивной) функцией.
В информатике принят Тезис Тьюринга-Черча, который говорит о том, что любой интуитивный алгоритм можно представить подходящей машиной Тьюринга, а любая интуитивно вычислимая функция есть частично рекурсивная функция.
Одним из главных результатов информатики есть доказательство существования универсальной машины Тьюринга, т.е. конкретной машины Тьюринга 1/, которая по кодам любой другой произвольной машины Тьюринга Р и входных данных для нее а выдает тот же результат Ъ (код результата Ь), что и машина Р [84].
Этот результат может быть перефразирован для частично рекурсивных функций. Например, существует частично рекурсивная фунция двух переменных и(х,у), универсальная для семейства всех одноместных частично рекурсивных функций, т.е. все одноместные частично рекурсивные функции можно расположить в ряд:
и(0,у),и(1,у)
Тезис Тьюринга можно перефразировать и так: не существует универсального компьютера, превосходящего по вычислительным возможностям универсальную машину Тьюринга.
Зафиксируем некоторое стандартное эффективное перечисление (нумерацию) программ (наборов команд) всех машин Тьюринга, так что каждому натуральному числу х ставится в соответствие набор команд, стоящий на х + 1-м месте в этом перечислении. Процесс перечисления дает как а) алгоритм для перехода от произвольного числа х к соответствующему набору команд Тг (машине Тьюринга Тх), так и б) алгоритм перехода от набора команд машины Тьюринга Т к такому числу х, что Т