Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Проблема остановки в теории алгоритмов, и не только

Покупка
Новинка
Артикул: 890570.01.99
Доступ онлайн
1 099 ₽
В корзину
В книге рассказывается о «проблеме остановки», пожалуй, самой знаменитой неразрешимой проблеме: может ли алгоритм за конечное время решить, остановится ли когда-нибудь произвольная компьютерная программа? Проблема остановки «кроется» во многих предметах: от логики (свободна ли математика от противоречий?) и физики (является ли квантовая случайность совершенной?) до философии (обладает ли человек свободой воли или наш мозг генерирует мысли и решения автоматически?) и квантовых вычислений (почему не существует квантовой проблемы остановки?). Книга написана неформальным языком, приглашает к размышлениям и почти свободна от заумной математики (формальные доказательства имеются только в некоторых частях). Издание предназначено широкому кругу читателей, интересующихся информатикой и смежными областями знаний.
101
Калюд, К. Проблема остановки в теории алгоритмов, и не только : практическое руководство / К. Калюд ; пер. с англ. А. А. Слинкина. – Москва : ДМК Пресс, 2024. - 266 с. – ISBN 978-5-93700-315-7. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2274641 (дата обращения: 20.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Кристиан С. Калюд
Проблема остановки 
в теории алгоритмов, 
и не только


To Halt or Not to Halt? 
That Is the Question
Cristian S Calude


Проблема остановки 
в теории алгоритмов, 
и не только
Кристиан С. Калюд
Москва, 2024


УДК 510.5+519.712
ББК  22.12
К17
Кристиан С. Калюд
К17 
Проблема остановки в теории алгоритмов, и не только / пер. с англ. 
А. А. Слинкина. – М.: ДМК Пресс, 2024. – 264 с.: ил.
ISBN 978-5-93700-315-7
В книге рассказывается о «проблеме остановки», пожалуй, самой знаменитой 
неразрешимой проблеме: может ли алгоритм за конечное время решить, остановится ли когда-нибудь произвольная компьютерная программа? Проблема 
остановки «кроется» во многих предметах: от логики (свободна ли математика 
от противоречий?) и физики (является ли квантовая случайность совершенной?) 
до философии (обладает ли человек свободой воли или наш мозг генерирует 
мысли и решения автоматически?) и квантовых вычислений (почему не существует квантовой проблемы остановки?). Книга написана неформальным 
языком, приглашает к размышлениям и почти свободна от заумной математики 
(формальные доказательства имеются только в некоторых частях).
Издание предназначено широкому кругу читателей, интересующихся информатикой и смежными областями знаний.
УДК 510.5+519.712
ББК 22.12
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой 
бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав.
Copyright © 2024 by World Scientific Publishing Co. Pte. Ltd.
©  Оформление, издание, перевод, ДМК Пресс, 2024
ISBN  (анг.) 978-9-81123-227-5
ISBN  (рус.) 978-5-93700-315-7


Читателю, мозг которого – не машина Тьюринга1
1	 G. Longo [279, стр. 21].


Оглавление
Предисловие от издательства........................................................... 9
Вступительное слово........................................................................ 10
Предисловие...................................................................................... 11
Глава 1. От Entscheidungsproblem к проблеме остановки.......... 14
1.1. Почему проблема остановки получила такое название?.........................14
1.2. Доказательство в стихах.............................................................................15
1.3. Программы на псевдокоде.........................................................................18
1.4. Остановка программы...............................................................................19
1.5. Неостанавливающиеся программы..........................................................20
1.6. Циклы и неостанавливающиеся программы...........................................21
1.7. Проблема остановки...................................................................................22
1.8. Бесконечно много разрешимых случаев..................................................23
1.9. Бесконечный анализатор...........................................................................25
1.10. Теорема об остановке...............................................................................25
1.11. Может ли человек решить проблему остановки?...................................27
1.12. Тезис Чёрча–Тьюринга.............................................................................28
1.13. Существует ли квантовая проблема остановки?....................................33
1.14. Языки программирования с разрешимой проблемой остановки........40
1.15. Перечислители..........................................................................................40
1.16. Приближенные решения проблемы остановки......................................41
Глава 2. Неполнота и остановка...................................................... 46
2.1. Евклид, Гильберт и аксиоматический метод............................................46
2.2. От теоремы об остановке к теореме о семантической неполноте..........54
2.3. От теоремы о семантической неполноте к теореме об остановке..........57
2.4. Минимальные программы.........................................................................58
2.5. Алгоритмическая сложность и несжимаемость.......................................60
2.6. Разрешима ли несжимаемость?................................................................64
2.7. Вычислима ли алгоритмическая сложность?............................................65
2.8. Кодирование проблемы остановки...........................................................65
2.9. Алгоритмическая и временная сложность...............................................70
Глава 3. Знаменитые математические утверждения  
и проблема остановки...................................................................... 72
3.1. Бесконечность множества простых чисел................................................72
3.2. Принцип Дирихле.......................................................................................73


3.3. Гипотеза Гольдбаха и другие проблемы теории чисел.............................73
3.4. Десятая проблема Гильберта.....................................................................75
3.5. Теорема о четырех красках........................................................................77
3.6. Гипотеза Римана.........................................................................................78
3.7. Теорема Эйлера о разбиении целого числа..............................................79
3.8. Гипотеза Коллатца......................................................................................80
3.9. Проблема равенства P и NP........................................................................81
3.10. Конечно опровержимые утверждения....................................................84
3.11. Вычисление сложности класса математических утверждений.............86
3.12. Универсальная беспрефиксная двоичная машина Тьюринга...............87
3.13. Двоичное кодирование программ для регистровой машины...............88
3.14. Методы программирования....................................................................90
3.15. Мера сложности для Π1-утверждений.....................................................93
3.16. Конкретные сложности............................................................................93
Глава 4. Интересные применения теоремы об остановке.......101
4.1. Можно ли для тестирования и доказательства правильности 
программы ограничиться одним лишь компьютером?...............................101
4.2. Можно ли написать антивирусную программу,  
которая не будет нуждаться в обновлениях?................................................103
4.3. Можно ли написать идеально безопасную операционную систему?....... 105
4.4. Существуют ли неразрешимые проблемы в программной  
инженерии?.....................................................................................................106
4.5. Поведение программы.............................................................................108
4.6. Небезопасность сети................................................................................110
4.7. Бесконечная делимость............................................................................111
4.8. Есть ли у физики иммунитет к невычислимости?.................................112
4.9. Сила и слабость случайности...................................................................114
4.10. Реляционные базы, теория Рамсея и невозможность полного 
беспорядка.......................................................................................................117
4.11. Спонтанные корреляции в больших данных:  
«Избыток информации внешне походит на недостаток информации».....122
4.12. Квантовая случайность...........................................................................129
4.13. Проблема остановки в шахматах и в игре на четность........................141
4.14. Искусственный интеллект: могущество и пределы.............................144
4.15. Свобода воли и случайность..................................................................164
4.16. Существует ли универсальный генератор изображений?...................171
Глава 5. Проблема остановки, и не только..................................181
5.1. И снова о теории вычислимости.............................................................181
5.2. Машины Тьюринга...................................................................................182
5.3. Еще о циклах и неостанавливающихся программах.............................184
5.4. Теорема о разрешимости: формальное доказательство........................184
5.5. Конечная версия теоремы об остановке.................................................185
5.6. Теорема о принятии.................................................................................185
5.7. Теорема Райса – формальное доказательство........................................186
5.8. Теорема Спекера.......................................................................................187
Оглавление    7


5.9. Можно ли «экспериментально проверить» невычислимость?.............190
5.10. Насколько «неразрешима» проблема остановки?................................195
5.11. Большинство программ останавливаются быстро или 
не останавливаются никогда..........................................................................196
5.12. Насколько велико множество спонтанных корреляций?....................202
Глава 6. Формальный подход к неполноте и остановке..........204
6.1. Аксиоматические системы......................................................................204
6.2. Автоматизированное доказательство теоремы об остановке...............206
6.3. Унифицированное представление теорем о неполноте,  
основанное на теореме об остановке............................................................209
6.4. Необычно длинные доказательства........................................................214
6.5. Является ли гёделева неполнота исключением?....................................219
6.6. Любая функция вычислима.....................................................................221
Глава 7. Исторические и философские замечания.....................224
7.1. Предтечи теории вычислимости.............................................................224
7.2. Entscheidungsproblem и Тьюринг.............................................................227
7.3. Проблема остановки: неправильная версия...........................................228
7.4. ChatGPT-4 о проблеме остановки............................................................229
7.5. Еще об истоках проблемы остановки......................................................231
7.6. Программные средства доказательства..................................................233
7.7. Почему и что мы вычисляем?..................................................................234
7.8. Краткая история неразрешимости..........................................................236
Послесловие.....................................................................................241
Библиография..................................................................................243
Оглавление


Предисловие от издательства
Отзывы и пожелания
Мы всегда рады отзывам наших читателей. Расскажите нам, что вы думаете об 
этой книге – что понравилось или, может быть, не понравилось. Отзывы важны 
для нас, чтобы выпускать книги, которые будут для вас максимально полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на страницу книги и оставив комментарий в разделе «Отзывы и рецензии». Также 
можно послать письмо главному редактору по адресу dmkpress@gmail.com; 
при этом укажите название книги в теме письма.
Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http://dmkpress.com/
authors/publish_book/ или напишите в издательство по адресу dmkpress@gmail.com.
Список опечаток
Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое 
качество наших текстов, ошибки все равно случаются. Если вы найдете ошибку 
в одной из наших книг – возможно, ошибку в основном тексте или программном коде, – мы будем очень благодарны, если вы сообщите нам о ней. Сделав 
это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги.
Если вы найдете какие-либо ошибки в  коде, пожалуйста, сообщите о  них 
главному редактору по адресу dmkpress@gmail.com, и мы исправим это в следующих тиражах.
Нарушение авторских прав
Пиратство в  интернете по-прежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к  вопросам защиты авторских прав и лицензирования. Если вы столкнетесь в интернете с незаконной 
публикацией какой-либо из наших книг, пожалуйста, пришлите нам ссылку на 
интернет-ресурс, чтобы мы могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу 
dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.


Вступительное слово
Двадцатый век стал свидетелем нескольких важных концептуальных революций. Сначала, конечно, теория относительности  – специальная и  общая. 
Но  еще более революционными стали квантовая механика, со всех сторон 
обсуждавшаяся философами, с ее суммами Фейнмана по всем путям и запутыванием кубитов, а в математике – целый пласт работ, посвященных такой, 
на первый взгляд, безобидной «проблеме остановки», которая тоже скрывает 
глубокий философский подтекст, но известна далеко не так широко. И вот теперь Кристиан Калюд в этой весьма интересной и разнообразной по тематике 
книге рассказал, почему проблема остановки является такой революционной 
и важной. Рискну даже сказать, излюбленной.
Он разворачивает перед нами различные варианты проблемы остановки, 
многочисленные области ее применения, демонстрируя плодородие и  богатство почвы, на которой на протяжении большей части столетия взращивало новый концептуальный аппарат небольшое сообщество, и ставя себе целью досконально разобраться в приложениях такой, казалось бы, непритязательной идеи.
В результате получился на удивление захватывающий путеводитель по 
проблеме остановки, красочная мозаика новых идей и концепций, описывающая новую веху в развитии оснований математики.
Отправьтесь в путешествие с Калюдом в эту страну блистательных озарений. В век, когда над нами нависла угроза искусственного суперинтеллекта, 
находишь особое удовольствие и гордость от созерцания того, на что способен 
раскрепощенный человеческий дух.
Грегори Хайтин,
автор книги «Algorithmic Information Theory» (CUB Press, 1987)


Доступ онлайн
1 099 ₽
В корзину