Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 106
Скачиваний: 0
* |
18.1. |
Следы |
|
|
|
|
|
|
150 |
|
* |
18.2. |
Эксперимент |
с разрезанной |
лентой |
|
152 |
||||
* |
18.3. |
Замещения |
|
|
|
|
|
152 |
||
§ 19. |
Нижние оценки |
сложности |
|
|
153 |
|||||
* |
19.1. Сложность |
распознавания |
симметрии . . . . |
153 |
||||||
* |
19.2. |
Сложность |
перевода |
в десятичную |
запись . . |
155 |
||||
§ 2 0 . Существование |
сколь угодно |
сложных |
проблем . . |
156 |
||||||
|
20.1. |
Уточнение |
постановки вопроса |
|
157 |
|||||
|
20.2. Распознавание /-самоприменимости |
|
158 |
|||||||
V § 2 1 . |
Автоматы |
Неймана |
|
|
|
161 |
||||
|
21.1. Системы тыоринговых |
машин |
|
161 |
||||||
|
21.2. |
Автоматы |
Неймана |
|
|
|
163 |
|||
|
21.3. |
Пример: |
неймановы |
часы |
|
|
166 |
|||
|
21.4. |
Нейманово |
моделирование |
машин |
Тьюринга . |
167 |
||||
§ 22. |
Задача о стрелках |
|
|
|
172 |
|||||
|
22.1. Стрелки |
|
|
|
|
|
|
172 |
||
|
22.2. |
Стрелки |
и |
автоматы |
|
|
|
173 |
||
|
22.3. |
Решение |
задачи |
|
|
|
176 |
|||
§ 23. |
Сравнение |
неймановых |
и тыоринговых |
вычислений |
179 |
|||||
|
23.1. |
Кодирование |
|
|
|
|
179 |
|||
23.2.Вычислимость по Нейману и по Тьюрингу . . . ,182
23.3.Распознавание симметрии на автомате Неймана 185
23.4. Тыорингово моделирование автомата |
Неймана 188 |
§ 24 заключительный |
190 |
Указатель |
195 |
Содержание |
198 |
БОРИС АВРААМОВИЧ ТРАХТЕНБРОТ
Алгоритмы и вычислительные автоматы
Редактор Н. Я. Гутчина |
|
|
||
Художественный редактор В. Т. Сидоренко |
|
|||
Обложка художника Б. Л. Николаева |
|
|||
Технический редактор Г. 3. |
Кузнецова |
|
||
Корректор Н. М. |
Давыдова |
|
||
Сдаяо в набор 6.Ш—1973 г, Подписано в печать |
13.ХП-1973 г. Т18070 |
|||
Формат 84Х108'/зз |
Бумага |
типографская |
N> 2 |
|
Объем |
12,5 усл. п. л., |
11,652 уч.-изд. л. |
|
|
Тираж |
27 500 экз. |
Зак. 263. |
Цена 7 1 к о п . |
|
Издательство «Советское радио», Москва, Главпочтамт а/я 693
Московская типография М> 4 Союзполиграфпрома при Государственном Комитете Совета Министров СССР
по делам издательств, полиграфии и книжной торговли Москва, И-41, Б. Переяславская, 46
|
|
|
1J |
|
|
|
|
|
З А М Е Ч Е Н Н Ы Е О П Е Ч А Т К И |
||||
Стр. |
Строка |
о |
~ |
„ |
|
|
Напечатацр |
|
Д о л ж н о быть |
||||
|
|
|
|
|||
12 |
3 |
снизу |
для большей |
в |
силу |
большой |
75 |
3 |
снизу |
|
|
Sj |
Pq, |
93 |
2 |
снизу |
Q |
|
|
Ъ |
94 |
3 |
сверху |
задавать |
|
задевать |
|
96 |
11 |
снизу |
рис. 27 |
|
рис. |
26,6 |
105 19 снизу
114 5 сверху
12, 31
158 сверху 14, 32, 34
сверху 159 1 снизу
165 рис. 44,6
177 1 снизу
184 1 снизу
190 18 снизу Зак 263
. . . |
я* - ,)'* » |
-••> |
"k-i) |
() |
|
, |
0)-(/ |
|
, |
0 ) . п |
|
|
31 |
|
|
|
|
/ я .. |
|
|
|
|
|
|
8 |
|
|
|
|
сс (* + |
1) = г |
т |
a(t + |
l)=rn |
|
|
ггг |
|
|
|
|
ГС/ |
|
|
m |
|
|
|
3! |
|
|
si |
|
1 2 / Э Т ( Я ) + 0 / ^ ( Р ) |
1 2 ^ ( P ) + 6 / J J J ( P ) |
||||
