Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы

.pdf

Скачиваний:

Добавлен:

21.10.2023

Размер:

9.86 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 / 2120 21 > Следующая >>>

4 (d +	2) + 4 (d + 4)	+	... +	4 (d + 2/) = 4 (d + t +
+ 1)	Л			(4)
Допустим теперь, что нейманов автомате вычисляет зна
чение	функции / (Р)	за	(Р)	тактов. Легко понять, как

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

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

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

*яя'(Я) <		4 ( I р 1 +		( р ) + 0		% (р) +		2 ( 1 Р I + Щ			(Р)). (
Вспомним,			наконец,		что	в	нетривиальных			ситуациях
(см. замечание в конце п. 23.1)							( P ) ^ ] P j .		Следователь
но, заменяя в (5) \| Р				\| на	(Р),		а также	1 на	^	(Р),	полу
чим;	для	нетривиальной			ситуации
	•	tm.	(Р) <	12/э т	(Р) + 6/§j (Р) <			18% (Р).
Это	и утверждается			теоремой		4.

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

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

I . Благодаря тому, что понятие «вычислимая	функция»	не зависит
от принятой .формализации понятия «алгоритм»	(п. 11.5,	11.6,	13.2,
21.4, 23.1), оно играет исключительную роль	в теории	алгоритмов
и служит основой для формулировки других	ее существенных по
нятий.
Рассмотрим, например, понятие разрешимого множества			(на

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

Г90


Множество	М	натуральных		чисел называется		разрешимым,	если
егохарактеристическая			функция	1М	вычислима.
(Напомним,	по	определению		/ д ,	(ft) = 1 при	п £ М и	= О

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

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

понятие перечислимого	множества. Непустое мноокество М перечис
лимо, если существует	вычислимая функция I такая,			что последо
вательность
	/ (1),	h (2),	/ (ft), ...	(*)
состоит в точности из	всех	элементов	множества М	(Подчеркнем,

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

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


множества		формул, выводимых из конечной системы аксиом.
Хотя	класс перечислимых					множеств и шире			класса	разрешимых
множеств, тем не менее он составляет лишь ничтожную										долю класса
всех множеств натурального ряда (первый класс счетен,											второй —
несчетен).
Заметим еще,			что обычно			в теории		алгоритмов, говоря			о вычис
лимых	функциях,		имеет		в	виду	не	только	всюду	определенные
функции,		по и частичные			функции.		Дело в том, что при			рассмотрении
некоторого алгоритма				может оказаться, что он является частичным,
т. е. при		некоторых исходных данных он вообще не								вырабатывает
никакого		результата		(например,			машина Тьюринга не применима

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

ленных

нами

фактов справедливы

на самом деле и для

частичных

функций. Например (см, теоремы из 11.5,

11.6), справедливо утверж

дение:

класс

частичных

рекурсижых

функций

совпадает

классом-

частичных

функций,

вычислимых

по

Тьюрингу.

В п. 15.2 кратко описан частный

случай метода

сводимости

ал

горитмической проблемы

91, состоящей

из

серии единичных

задач

аг, а2. ...

алгоритмической

проблеме

93,

состоящей

из

серии

единичных

задач bL, b2

В самой

общ?й

ситуации

процедура

све

дения 91 к

33 такова,

что решение

единичной задачи сц сводится к

нескольким

задачам

принятым за решенные. При этом по

ходу

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


цесса. Такие процедуры называют условными				алгоритмами,		или
алгоритмами	сведения	в отличие от обычных абсолютных			алгорит
мов. Может	оказаться,	что каждая из двух массовых проблем 91, 93
алгоритмически неразрешима, причем 91 сводима				к 23, но 93 не своди
ма к 91; содержательно это означает, что алгоритмическая					проблема
93 еще более неразрешима,			чем алгоритмическая	неразрешимая		про
блема ?[. В таком случае			говорят, что проблема	93 имеет	более	вы

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

191

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


1) В.		А. У с п е н с к и й .				Лекции о вычислимых функциях, М.
Физматгиз,			I960;
2)	А. И.			М а л ь ц е в ,		Алгоритмы и	рекурсивные	функции.
М., «Наука»,				1965.
I I .	Существование				алгоритмически		неразрешимых	проблем
(п. 15.2), а также алгоритмически разрешимых, но сложно								решаемых
проблем		(п.	20.2) было		первоначально установлено путем построе
ния искусственных, нарочито						придуманных примеров,		связанных
с самоприменимостыо					и /-самоприменимостью. Имеют			ли	место
такие	явления			для естественных проблем,			представляющих		само


стоятельный интерес? Для алгоритмической			неразрешимости это
действительно так	(см. п. 15.1, 15.3).	Что же		касается	алгоритми
чески разрешимых	проблем с высокой	нижней		оценкой	времени их
решения, (например, G оценкой типа		(п) >	2 Л ) , то лишь			сравни
тельно недавно были обнаружены достаточно «естественные»						примеры

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

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

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


сящегося		к оценке	сложности	вычислений	посредством		сигнализи
рующих		функций (п. 17.1). Что		же касается подхода,		основанного
на	оценке сложности		описания	алгоритма	(см. начало	§	17), осно
вы	которого заложены в работах А. А Маркова и А.					Н.	Колмого

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

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


вания	заключается в создании языков	программирования	высокого
уровня	(например, АЛГОЛ) и соответствующих трансляторов,			т. е.
программ перевода. Это далеко идущее обобщение идеи			входного
"языка	и программирующего алгоритма	(§10) л е ж и т е основе		автома

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

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

192

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


ных областях,		а также соответствующую библиографию								можно	най
ти в книге: История отечественной математики,								т. 4, кн. 2 (гл. V —
V I ) ,	Киев, «Наукова думка»,				1970.
Достаточно		доступное		изложение ряда		вопросов			из теории алго
ритмов и теории автоматов					содержится	в	переводных книгах:
А.	Тьюринг.	Может	ли	машина мыслить?			М.,	Физматгиз,			1960;
М. Минский Вычисления				и автоматы. М.,		«Мир»,		1971.
V I . В связи о теоремами об алгоритмической неразрешимости то
го или иного класса задач заметим, во-первых, что они не										дают	пово
да для впадания в агностицизм. Действительно, каждая										такая	тео
рема касается целого класса задач и устанавливает									неразрешимость
всех задач этого класса			единым эффективным				методом—алгоритмом.

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

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

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

(как теория	групп с конечным числом образующих и т. д.) возника
ют массовые	проблемы, решить которые не способен никакой авто
мат (т. е. никакая машина Тьюринга).
V I I . Вместе с тем приходится признать, что область применения

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

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

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

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

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

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

193

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

V I I I . Наконец, обратим еще раз внимание на то, что каждая физи чески осуществимая вычислительная машина может быть рассматри ваема лишь как некоторая приближенная модель машины Тьюринга или автомата Неймана. Именно в реальных машинах объем внешней памяти ограничен, в то время как в машине Тьюринга и в автомате Неймана фигурирует бесконечная лента. Разумеется, техническое осуществление неограниченной памяти невозможно, но значитель ное увеличение объема памяти в машинах по сравнению с уже достиг нутым уровнем не только желательно, но и вполне возможно. Имен но в этом направлении наращивания объема внешней памяти и ско рости вычисления можно ожидать дальнейших больших успехов в развитии вычислительных автоматов. Однако наряду с техническим прогрессом существенное значение имеют и чисто математические исследования, направленные на выяснение того, какие типы

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

УКАЗАТЕЛЬ
А втом ати чес к н е	в ы ч исл птел ь-
ные машины	6, 9, 46

—— —, применение 59

——- —, функционирование 58


Автоматы		Неймана 9, 161,		163
Аксиоматический			метод в	ма
	тематике 64
Активные		ячейки	137
Алгоритм 3, 5, 11, 26
—,	детерминированность			15
—,	массовость 15

—подражания 125

—приведения 38

—. точное определение 61—67

—Эвклида 11, 97

—— в машине Тьюринга 84 Алгоритмическая неразре

шимость 190

—— проблемы тождества

теории групп 135 Алгоритмические проблемы 125 "Алгоритмов качество 144 Алгоритмы игр 15

—нормальные 39

—равносильные 123

—численные 13 Алфавит 33

Арифметические					действия			11
— функции			и	отношения				111
Арифметический					блок		49
Ассоциативные				исчисления				33
Барздинь		Я-	М.		150
Безусловная			передача				управ
ления		51
Блок	управления				50
Бзббидж		Ч	4,	7,	8
Введение			фиктивных				пере
менных			101
Вершины		дерева 19
Ветви	19
Внешний		алфавит			68
Внешняя		память			115
Внутренний			алфавит			машины
71
Возможности				машин		9
Вхождение слова					34
Выделяющий				алгоритм			89
Вычислимость				по	Нейману
и Тьюрингу				182

Вычислительный процесс с участием человека-вычис лителя 47


Гильберт					Д.	14
Группы				преобразований						136
Гото		Э.			179
Дедуктивные						цепочки 34,				64
Дерево			игры			17
Десятая проблема Гильберта										14
Диофантовы						уравнения			14
Задача				о	стрелках			172
Заменяющие						алгоритмы			89
Замещения					152
Запоминающие устройства										49
Игра		11		предметов				16
—	«побеждает					чет»		17
—	в шахматы					23
Индекс				вхождения				буквы		41
— слова				41
Индуктивные						определения				101
Итерация					104
Класс			тыорингово					вычисли
	мых		функций				101
Кодирование						179
Кодовая				группа			128
Колмогоров					А.	N.	§	24
Команды					арифметические					51
— логических							операций			51

—остановки 51

—переадресации 55

—	передачи	управления			51
—	условные	51
Конечные функции				НО
Контролируемый				переход	78
Концевая вершина				19
Конфигурации			конечные		75

—Тьюринга 74 Конфигурация 74

—глубинная (левая, правая, одиночная ) 139

Копирующие алгоритмы .89

Кордемский Б. А. 16, 17 Корень дерева 19

Лабиринты		26
Левая	дихотомия			178
Левенштейн		В.	И.	179
Лейбниц	Г.	В.	63
Лемма	о замещениях				153
Логическая		функция			машины
72

195

Логические			задачи			15
Ляпунов		А.	А.	4
Мальцев		А.	И.		§	24
Марков		А.	А.	9,	33,		123,
	134,	135
Матиясевич			Ю.			В.	15,	137
Машина		несамоприменима						130
—	самопрйменима					132
—	Тьюринга 8,				9,	60,	68,	124

——, определение 68

——, отличие от современ ных машин 68

— —,	ее		работа			73
,	реализация					алгоритма
76	универсальная							125

Машинные				команды			50
Многоэтажные					и	многомерные
ленты			119
Мур	Э.	Ф.		172,		176
Мышь		в		лабиринте				25
Невозможность							алгоритма
распознавания							переводи-
мости			136
Нейман		Джон			фон 8,			124,	161
Нейманов				элемент			164
Нейманово					моделирование
машин			Тьюринга					167
Неймановы				и тыоринговы					вы
числения					179
— часы			166
Неориентированные								подста
новки			34
Новиков		П.		С.	9,	135—136
Обозреваемая					ячейка			на дан
ном		этапе			70
Ориентированные						подстанов
ки		34
Основная				гипотеза»				теории
алгоритмов					120
Память			внешняя					72,	131
— внутренняя					72,		131
Параллельная					композиция				93
Перечислимое						множество
§ 2 4
Переводимость					134
Перевод			унарной записи						чи
сел		в	десятичную					145
Повторное				применение					ал
горитма				96
Подстановки					34
Полуленты					и	параллельная
композиция 116

Последовательная композиций 91

Пост Э. 8, 135, 136 Правая дихотомия 178 Примитивная рекурсия 103

Примитивно рекурсивное опи сание ПО

Проблема распознавания вы водимости 63, 132

Проблема распознавания переводимости 134

— — применимости 132 самоприменимости 132,

133

—решения уравнений в сло вах 137

—слов 33

—— и лабиринта 36

—	— в	современной		алгебре
	42
—	эквивалентности			слов 34,
	143
—	— —	для	ассоциативных
	исчислений		135
Программа 48

— для линейных уравнений 53

Программирование						алгоритма
	Эвклида			57
Программирующие						алгорит
	мы	88,	90
Простейшие					операторы			102
Простой			путь		26
Пустое слово					38
Рабин		М.	160
Разветвление					алгоритмов			94
Различие			между			машиной
	Тьюринга				и реальной			ма
	шиной		189
Разрешимое				множество			§ 24
Ранг		19
—	дерева		19
Распознавание					выводимости			63
—	самоприменимостн и						пере
	води мости				132
—	симметрии				148,	153

— — на автомате Неймана 184 Рекуррентные (возвратные)

определения 101 Рекурсивное программиро

вание функций, вычисли мых по Тьюрингу 112

Рекурсивные	описания 108
— функции	99

196

Решение конкретной задачи

исерии задач 5

—машиной класса задач 69

Самоприменимость 132 Самосовмещение квадрата 42 Система одноадресных прика

	зов	70
—	трехадресных			приказов	70
—	Тыоринговых			машин	161
—	уравнений		в	словах	46
След процесса			150
Слово		33

Сложение и умножение в ма


	шине		Тьюринга				81,		82
Сложность				описания				алго
	ритма			144
Смежные			слова			34
Спиридович				Р.		Н.	137
Стандартные					программы				88
Стоп — состояние 73
Стандартное					задание			инфор
	мации			87
Стратегия				16
—	выигрышная					16,	20
—	—,	теорема				существова
	ния	20
Степень			неразрешимости						§ 24
Теорема			о	полуленте				117

—о программировании па раллельной композиции 23

—— повторения 97

—последовательной компо зиции 91

—— разветвления 95

—Цейтина 158

—Черча 132

Тождественный						алгоритм 89
Ту9.		А.	135
Тьюринг			А.	8,	61,		68,	124
Тыорингово					моделирование
	автоматов				Неймана				188
Универсальная						машина			127
Условный				алгоритм				§ 24
Успенский			В.		Л. §		24
Формальные					операции				над
	программами					88
Функциональная						схема			ма
	шины		72
		машина			Тьюринга				72
Функция			общерекурсивная
	(рекурсивная)					109
—	примитивно					рекурсивная
	110
—	сигнализирующая								144
\|-самоприменимость									159
Цейтин			Р.	С.		35,	137,		158
Человек-вычислитель									46
Черч		А.	131
Численные				алгоритмы				13
Численный				анализ			13
Шеннон			Клод		25
Шифр		конфигурации						129
— функциональной							схемы		129
Эквивалентность						слов		34
Языки		программирования							98
ц — оператор					107

			С О Д Е Р Ж А Н ИЕ
Предисловие								3
Введение								5
ЧАСТЬ		I . Алгоритмы						11
§ 1 .		Численные алгоритмы						11
	1.1.		Арифметические			действия; алгоритм Евклида . .		11
	1.2.		Численные	алгоритмы				13
	1.3.		Диофантовы		уравнения			Ц
§ 2.		Алгоритмы игр						15
	2.1. Одиннадцать предметов							16
	2.2.		Побеждает	чет				17
	2.3.		Дерево игры					17
	2.4.		Существование			выигрышной	стратегии . . . .	20
§ 3 .		Алгоритмы поиска				пути в лабиринте		25
	3.1.		Лабиринты				:	25
	3.2.		Алгоритм	поиска .				26
	3.3.		Обоснование		алгоритма поиска			29
§ 4.		Проблема слов						33
	4.1. Ассоциативные исчисления							33
	4.2.		Проблема	эквивалентности слов				34
	4.3.		Проблема	слов		и лабиринты		36
. 4.4.			Построение алгоритмов					37
	4.5.		Самосовмещення			квадрата		42
*	4.6.		Уравнения	в	словах			46
§	5.	Вычислительная машина с автоматическим управле
	нием							46
	5.4.		Человек-вычислитель					46
	5.2.		Вычислительные			машины		48
	5.3.		Машинные	команды				50
§ 6.		Программа (машинный алгоритм)						52
. 6 . 1 . Программа для линейных уравнений								53
	6.2.		Повторение					54
	6.3.		Программирование алгоритма				Ев.клида	^57

6.4.Функционирование вычислительной машины . . '58

6.5.Другие применения вычислительных машин . . . 59

ЧАСТЬ П. Машины Тьюринга					60
§ 7. Необходимость		уточнения понятия алгоритма . .			60
7.1. Существование		алгоритмов			60
7.2.	Распознавание	выводимости			63
7.3.	Формулировка	определения		«алгоритма» . . .	65
§ 8. Машина Тьюринга					68
8.1. Определение машины Тьюринга					68
8.2.	Функционирование		машины	Тьюринга	73
§ 9. Реализация алгоритма			в машине Тьюринга (тыорин-
гово	вычисление)				76

198

9.1\

Переход от пк

+ '

1 в'десятичной

системе

счис-

ления

9.2.

Перевод унарной записи в десятичную

9.3.

Сложение

. 8 1

9.4-. Повторное суммирование и умножение

9.5.

Нахождение общего

наибольшего делителя

. ,

§ 10.

Программирующие алгоритмы

10.1. Стандартные

программы

и формальные

операции

над программами

10.2.

Последовательная композиция . . . .

. . .

. .

10.-3. • Параллельная

композиция

10.4.

Разветвление

алгоритмов

10.5.

Повторное применение алгоритма

10.6.

Языки программирования

§ 11.

Рекурсивные функции

и функции,

вычислимые по

Тьюрингу

11.1. Вычисление функций

и алгоритмические

пробле

мы . .

11.2.

Простейшие операторы

102

• 1-1.3. Примитивная рекурсия

103

11.4.

ц.-оператор

107

11.5.

Рекурсивные

описания

их

тыорингово

про

граммирование

108

* 11.6.

Рекурсивное

программирование

функций,

вы

числимых по

Тьюрингу

112

§ 12. -Варианты внешней памяти

: . .

115

12.1. Полуленты и

параллельная

композиция . .

. .

116

•

12.2.

Доказательство

теоремы

полуленте

117

•

12.3.

Многоэтажные

и многомерные

ленты

119

§ 13. Основная гипотеза теории алгоритмов

120

13.1. Гипотеза и ее значение

120

13.2.

Обоснование

гипотезы

123

ЧАСТЬ

I I I . Алгоритмические проблемы

125

§ 14.

Универсальная

машина

Тьюринга

125

14.1. Алгоритм подражания

125

14.2.

Универсальная

машина . . .

127

§ 15.

Алгоритмически

неразрешимые

проблемы .

. . .

131

15.1. Теорема

Черча

131

15.2.

Распознавание

самоприменимости

переводи

мости

132

15.3.

Краткий

исторический обзор

134

§ 16.

Невозможность

алгоритма

для

проблемы

эквива

лентности

слов

138

16.1. Невозможность алгоритма распознавания

перево

димости

слов

.138

16.2.

Неразрешимость проблемы

эквивалентности

. . .

143

§ J 7 .

Качество

алгоритмов

и вычислений

144

17.1. Сигнализирующие

функции

144

17.2.

Оценки

для

примеров § 9

145

17.3.

Поиск лучшего

алгоритма

146

17.4.

Распознавание

симметрии

148

§ 18.

Следы тыоринговых вычислений

150

199

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 / 2120 21 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ