Противостояние недоказуемому — Гёдель и все такое

При бесконечной вычислительной мощности не может быть проблем или головоломок, которые нельзя решить? Знаменитая или печально известная теория неполноты Курта Гёделя говорит о другом, но что это на самом деле означает?

Путеводитель по теории для программистов

Есть более поздняя версия этого:

Теперь доступен в мягкой обложке и в электронной книге на Amazon.

Руководство программиста по теории — NP & Co-NP

СОДЕРЖАНИЕ

• Что вычислимо?
• Конечные автоматы
• Что такое машина Тьюринга?
• Вычислительная сложность
• Невычислимые числа
• Трансфинитный
• Аксиома выбора
• Лямбда-исчисление
• Грамматика и пытки
• Обратная польская нотация — RPN
• Введение в булеву логику
• Противостояние недоказуемому — Гёдель и все такое
• Руководство программиста по фракталам
• Руководство программиста по хаосу *
• Простые числа и проверка на простоту
• Клеточные автоматы — как и почему
• Теория информации
• Теория кодирования
• Колмогоровская сложность
• * Будет пересмотрено

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

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

Например, проблема теоремы Ферма и ее доказательства тянулась веками, а затем внезапно все это было решено с помощью новой математики, а некоторые старые математики были умело применены.

Последняя теорема Ферма — отрицательная теорема. В нем говорится, что не существует целых чисел a, b и c, удовлетворяющих:

ан + bn = сп

для n> 2 (есть множество примеров, когда a, b и c равно n = 2 или 1). Он почти взывает к вам, чтобы доказать это, найдя встречный пример, то есть a, b, c, которые действительно удовлетворяют соотношению для некоторого n> 2.

Но доказательства намного сложнее, чем вы можете себе представить.

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

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

Кажется, что люди плюс компьютеры способны решать проблемы точно и эффективно, и, конечно же, не может быть ничего недосягаемого?

Дело в том, что можно доказать, что есть истины, которые действительно находятся за пределами досягаемости логики.

По сути, это то, что Курт Гёдель доказал в 1931 году. Идея не сложная, но ее часто используют для обоснования некоторых очень странных выводов, большинство из которых вообще не оправданы!

Важно и интересно узнать немного больше о том, что это на самом деле означает.

Механическая математическая машина

Во-первых, нам нужно внимательнее присмотреться к тому, как мы на самом деле ожидаем, что мир будет работать.

Еще на рубеже 20-го века математика перестала быть «творческой» дисциплиной и стала стремиться быть точной и логичной.

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

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

Например, Альфред Норт Уайтхед и Бертран Рассел выпустили огромную книгу (Principia Mathematica, опубликованную в трех томах в 1910, 1912 и 1913 годах), в которой потребовалось несколько сотен страниц, чтобы получить доказательство того, что 1 + 1 = 2!

Дело в том, что это была очень подробная работа, построенная на очень простых исходных аксиомах, которые были настолько базовыми, что никто не мог с ними оспорить. Тот факт, что 1 + 1 было 2, был не просто физическим наблюдением, а логической необходимостью с учетом исходных аксиом.

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

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