Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

можно перестроить машину 50? в машину СО?', вычисляющую ту же функцию /, и как оценить время работы этой машины. Именно, 93?' работает сначала как 93?, имитируя t ^ (Р)

тактов автомата 91, на что затрачивается, как это видно из (4), не более чем 4 (| Р | + ^ (Р) + 1) ^ (Р) тактов; да­ лее, она должна привести сложившуюся к тому времени запись к стандартному виду заключительной тьюринговой конфигурации. Очевидно, для этого головке достаточно «пройтись» вперед и назад вдоль упомянутой записи, длина которой не превосходит | Р | + 2г^ (Р).

Итак, для общего времени, затрачиваемого машиной 93?', получается оценка

§ 24. ЗАКЛЮЧИТЕЛЬНЫЙ

Настоящий параграф состоит из отдельных примечании к основ­ ному тексту книги. Некоторые из них (I—V) включают библиогра­ фические ссылки и имеют целью облегчить выбор литературы для читателя, заинтересованного в дальнейшем изучении предмета'. Другие (VI—V111) носят характер общих заключительных замеча­ ний.

туральных чисел), уточняющее интуитивное представление о таком свойстве (натуральных чисел), которое можно алгоритмически рас­ познавать. Его определение таково:

Г90

в противном случае.)

Другое важное понятие, которым мы явно не пользовались, это

что в (*) элементы из М не обязаны располагаться в порядке возрас­ тания; кроме того, в (*) допускаются повторения.)

Способ перенесения этих и других определении на нечисловые множества естествен; например, множество слов перечислимо, если при арифметической интерпретации этих слов (см. п. 11.1) полу­ чается перечислимое множество натуральных чисел. Легко показать, что всякое разрешимое множество перечислимо. Обратное, вообще говоря, неверно. Например, самоприменимые шифры образуют перечислимое, но не разрешимое множество. То же самое верно и для

к данной конфигурации, или оператор \х порождает бесконечный процесс). Хотя в основном тексте мы избегали рассмотрение частич­ ных функций, совсем нетрудно обнаружить, что многие из установ­

реализации этой процедуры выясняется, какие «готовые» резуль­ таты нужно запрашивать и как они влияют па дальнейший ход про­

сокую степень неразрешимости, чем проблемч 91.

191

Изучение вычислимых функций, разрешимых и перечислимых множеств, условных алгоритмов и соответствующих им степеней не­ разрешимости всегда занимало центральное место в теории алгорит­ мов. Систематическое изложение этого материала можно найти в книгах:

таких проблем. К сожалению, в рамках этой книги нет возможности

в теории алгоритмов, и оно еще не нашло достаточно полного отра­ жения в монографической литературе. Книга Б . А. Трахтенброта «Сложность алгоритмов и вычислений (спецкурс для студентов НГУ, Новосибирск, 1967) систематизирует часть материала, отно­

рова, то пока здесь можно ссылаться только на журнальную лите­ ратуру.

I I I . Теорию программирования для реальных вычислительных машин можно рассматривать как прикладной раздел современной теории алгоритмов, в котором находят свое воплощение и дальней­ шее развитие многие идеи из более абстрактивных ее разделов. Так, например, одна из центральных проблем теории программиро­

тизации программирования. Именно программист на удобном для себя языке записывает алгоритм, и далее машина переводит эту за­ пись («руководствуясь» транслятором) на машинный язык, т. е. вырабатывают обычную программу из машинных команд (в смысле §6). См. Е. А. Жоголев и Н. П. Трифонов, Курс программирования. М., «Наука», 1971.

IV . Наряду с одномерными автоматами Неймана можно рассмат­ ривать и двумерные, трехмерные и т. д. Д ж . фон Нейман развил те­ орию автоматов такого типа не только для изучения их вычислитель­ ных способностей, но также для моделирования процесса самовос­ произведения. Имеется русский перевод его книги; (См. Д ж . фон Нейман. Теория самовоспроизводящихся автоматов. М., «Мир», 1971).

192

V. Подробные сведения исторического характера, обзор дости­ жений советских математиков в области теории алгоритмов и в смеж­

Это вовсе не означает, что среди единичных задач, объединя­ емых этим классом, имеются такие, которые неразрешимы. Напри­ мер, теоремы из п. 15.2 не следует понимать так, что существует такой шифр, о котором в принципе невозможно сказать, является ли он самоприменимым или нет.

Это означает лишь, что рассматриваемый тип задач является столь общим и широким, что единого алгоритма для решения всех задач данного типа не существует. В этом случае целью математи­ ческих исследований является последовательное создание все более и более широких алгоритмов, позволяющих сводить к автоматичес­ кому вычислению все более и более обширные подклассы задач дан­ ного типа.

Во-вторых, теоремы об алгоритмической неразрешимости по­ казывают, что математика не сводится к построению алгоритмов, что процесс познания в математике не может быть до конца автоматизи­ рован. Уже в отдельных, сравнительно узких областях математики

алгоритмических процессов весьма широка и й ней относятся не только вычислительные процессы, встречающиеся в математике. Более того, для многих процессов, которые обычно принято считать очень трудными и сложными, можно теоретически построить алго­ ритмы, являющиеся по своей идее достаточно простыми; практичес­ кие же трудности, встречаемые при реализации этих процессов,

ти, к процессам игры (и в частности, игры в шахматы), где успех во многом зависит от умения обозреть большее число вариантов для выбора оптимального варианта.

Создание и дальнейшее усовершенствование быстродействующих вычислительных машин значительно расширяет число практически

которых практически доступных (на данном уровне) алгоритмов не существует. Поэтому «чистое» доказательство алгоритмической раз­ решимости некоторой проблемы, т. е. такое доказательство сущест-

193

195