Теорема Гёделя о неполноте за 20 минут

Поделиться



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

С одной стороны, почти все о них что-то слышали. С другой — в народной интерпретации теория Эйнштейна, как известно, «говорит, что всё в мире относительно». А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума».

И вот одни пытаются приспособить её в качестве аргумента против материализма, а другие, напротив, доказывают с её помощью, что бога нет. Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.



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

Математическая логика — наука действительно довольно сложная, а главное — не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 15-20 минут времени.

Несколько упрощая, ТГН утверждает, что в достаточно сложных языках существуют недоказуемые высказывания. Но в этой фразе почти каждое слово нуждается в пояснении.

Начнём с того, что попытаемся разобраться, что такое доказательство. Возьмём какую-нибудь школьную задачку по арифметике. Например, пусть требуется доказать верность следующей незамысловатой формулы: «∀x(x−1)(x−2)−2=x(x−3)» (напомню, что символ ∀ читается «для любого» и называется «квантор всеобщности»). Доказать её можно, тождественно преобразуя, скажем, так:

∀x(x−1)(x−2)−2=x(x−3)

∀xx2−3x+2−2=x2−3x

∀xx2−3x–x2+3x=0

∀x0=0

ИСТИНА

 

Переход от одной формулы к другой происходит по некоторым известным правилам. Переход от 4-й формулы к 5-й произошёл, скажем, потому, что всякое число равно самому себе — такова аксиома арифметики. А вся процедура доказывания, таким образом, переводит формулу в булево значение ИСТИНА. Результатом могла быть и ЛОЖЬ — если бы мы опровергали какую-то формулу. В таком случае мы бы доказали её отрицание. Можно себе представить программу (и такие программы действительно написаны), которые бы доказывали подобные (и более сложные) высказывания без участия человека.

Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество S так называемых высказываний — то есть грамматически осмысленных фраз, каждая из которых истинна или ложна. Можно сказать, что существует функция P, сопоставляющая высказываниям из S одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество B из двух элементов).

Назовём такую пару — множество высказываний S и функция P из >S в B — «языком высказываний». Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда!» не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.

Для дальнейшего нам понадобится понятие алгоритма. Приводить здесь формальное его определение я не буду — это завело бы нас довольно далеко в сторону. Ограничусь неформальным: «алгоритм» — эта последовательность однозначных инструкций («программа»), которая за конечное число шагов переводит исходные данные в результат.

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

Спросим себя: для всякой ли функции P существует «доказывающий алгоритм» (или, короче, «дедуктика»), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима?

Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая — существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

Очень может быть, что это утверждение вызовет у вас внутренний протест. Связано это с несколькими обстоятельствами. Во-первых, когда нас учат школьной математике, то иногда возникает ложное впечатление почти полной тождественности фраз «теорема X верна» и «можно доказать или проверить теорему X».

Но, если вдуматься, это совершенно не очевидно. Некоторые теоремы доказываются довольно просто (например, перебором небольшого числа вариантов), а некоторые — очень сложно. Вспомним, например, знаменитую Великуютеорему Ферма:
 

Не существует таких натуральных x,y,z и n>2, что xn+yn=zn,

 

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

Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно.

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

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

В таких случаях говорят, что дедуктика противоречива. Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика» — отсюда и название теоремы.

Иногда называют «теоремой Гёделя» утверждение о том, что любая теория содержит проблемы, которые не могут быть решены в рамках самой теории и требуют её обобщения. В каком-то смысле это верно, хотя такая формулировка скорее затуманивает вопрос, чем проясняет его.

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





Курт Гедель

Любому школьнику известно, что, скажем, в случае функции sin⁡x вам должно сильно повезти с аргументом, чтобы процесс вычисления точного десятичного представления значения этой функции окончился за конечное число шагов.

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

Для дальнейшего опишем «язык формальной арифметики». Рассмотрим класс строк текста конечной длины, состоящих из арабских цифр, переменных (букв латинского алфавита), принимающих натуральные значения, пробелов, знаков арифметических действий, равенства и неравенства, кванторов ∃ («существует») и ∀ («для любого») и, быть может, каких-то ещё символов (точное их количество и состав для нас неважны).

Понятно, что не все такие строки осмысленны (например, «12=+∀x>» — это бессмыслица). Подмножество осмысленных выражений из этого класса (то есть строк, которые истинны или ложны с точки зрения обычной арифметики) и будет нашим множеством высказываний.
 

Примеры высказываний формальной арифметики:

  • 1=1

  • 2×2=5

  • ∃xx>3

  • ∀y∀zy×z>y+z

 

и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром x):
 

  • x=0

  • 2×2=x

  • ∃yx+y>x

 

и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.

Обозначим множество всех ФСП буквой F. Понятно, что его можно упорядочить (например, сначала выпишем упорядоченные по алфавиту однобуквенные формулы, за ними — двухбуквенные и т.д.; по какому именно алфавиту будет происходить упорядочивание, нам непринципиально). Таким образом, любой ФСП соответствует её номер k в упорядоченном списке, и мы будем обозначать её Fk.
 

Перейдём теперь к наброску доказательства ТГН в такой формулировке:

Для языка высказываний формальной арифметики не существует полной непротиворечивой дедуктики.

Доказывать будем от противного.

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

1. Находим k-ю формулу в списке F.

2. Подставляем в неё число k в качестве аргумента.

3. Применяем к полученному высказыванию наш доказывающий алгоритм (по нашему предположению, он существует), который переводит его в ИСТИНУ или ЛОЖЬ.

4. Применяем логическое отрицание к полученному результату.

Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.

Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.

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

Менее очевидно обратное утверждение:
 

Лемма: Любому алгоритму, переводящему натуральное число в булево значение, соответствует какая-то ФСП из множества F.

 

Доказательство этой леммы потребовало бы, как минимум, формального, а не интуитивного, определения понятия алгоритма. Однако, если немного подумать, то она довольно правдоподобна.

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

Пройдя это скользкое место, мы быстро добираемся до конца. 

Итак, выше мы описали алгоритм A. Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке F — скажем, n. Спросим себя, чему равно Fn(n)? Пусть это ИСТИНА. Тогда, по построению алгоритма A (а значит, и эквивалентной ему функции Fn), это означает, что результат подстановки числа n в функцию Fn — ЛОЖЬ.

Аналогично проверяется и обратное: из Fn(n)=ЛОЖЬ следует Fn(n)=ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.

Здесь уместно вспомнить Эпименида, который, как известно, заявил, что все критяне — лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.

В заключение я хочу заметить, что ничего особенного удивительного ТГН не утверждает. В конце концов, все давно привыкли, что не все числа представимы в виде отношения двух целых (помните, у этого утверждения есть очень изящное доказательство, которому больше двух тысяч лет?). И корнями полиномов с рациональными коэффициентами являются тоже не все числа. А теперь вот выяснилось, что не все функции натурального аргумента вычислимы.

Приведённый набросок доказательства относился к формальной арифметике, но нетрудно понять, что ТГН применима и к многим другим языкам высказываний. Разумеется, не всякие языки таковы. Например, определим язык следующим образом:
 

«Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».

 

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

«Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».

 

Здесь нас спасает то, что любой цитатник, очевидно, конечен, поэтому процесс «доказывания» неминуемо закончится. Таким образом, к языку догматических высказываний ТГН неприменима. Но мы ведь говорили о сложных языках, правда? опубликовано 

 



Источник: geektimes.ru/post/284486/

Так считали древние. Вавилон

Поделиться



Это продолжение задуманной мной серии про историю вычислений и счета. Первая статья про Египет здесь.

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


Вавилоняне в математике продвинулись намного дальше египтян, насколько нам известно, хотя и не сравнялись с греками, видимо. Они уже умели решать квадратные уравнения, кроме того имели некоторые зачатки числовой алгебры. Одно из их достижений было введение позиционной шестидесятеричной системы счисления без нуля. Это означает, что обращение с числами стало значительно более гибким и простым, чем в Египте. Точно не известно, откуда взялась такая система. Одна из версии говорит, что к ней привело смешение 6-ичной и 10-ичной систем народов Шумера и Аккада. Но существуют и другие мысли на этот счет.
Эта система, к сожалению (может и к счастью, не хотелось бы учить их таблицу умножения) не была освоена другими народами Древнего Мира, и пришлось ждать прихода индийской позиционной системы. Однако, кое-какое отражение вавилонской математики в нашей культуре осталось: деление минуты на шестьдесят секунд и часа на 60 минут — это отзвук древней вавилонской системы счисления.

Цифры и система счисления




Читать дальше →

Робот адаптируется к потере конечностей

Поделиться





В журнале Nature была опубликована статья «Роботы, которые могут адаптироваться как животные» (Robots That Can Adapt Like Animals). В ней демонстрируется, как роботы могут восстанавливаться при травме менее, чем за 2 минуты. В видеоролике выше показано, как шестиногий робот адаптируется и продолжает шагать даже с двумя сломанными ногами. Разработанный алгоритм также применим к робо-руке.

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

До начала функционирования робот использует компьютерную симуляцию процесса хода. Так составляется детальная карта поведения на основе нового эволюционного алгоритма MAP-Elites. В карте содержатся представления робота о различных методах работы и оценка их успешности. Гексапод получает повреждения и пытается использовать эти представления для управления алгоритмом обучения. Старые методы ходьбы уже не работают — карта составлялась для шести исправных конечностей. Проводятся эксперименты по быстрому обнаружению компенсирующего поведения и байесовская оптимизация. Новый алгоритм называется «Умный метод проб и ошибок» (Intelligent Trial and Error).




Читать дальше →

В МТИ разработали алгоритм, который удаляет с фотографий отражения в окнах

Поделиться



Алгоритм PageRank применили для определения наиболее успешных футбольных команд

Поделиться



Алгоритмизация личных финансов или подход технаря к вычислению трат

Поделиться



Пару лет назад я оформлял потребительский кредит (далеко не первый, надо сказать). Взял на работе справку 2-НДФЛ и понес ее в банк. В кредите мне отказали – менеджер не мог поверить, что я беру в долг под большие проценту и на целый год сумму, заметно меньшую, чем моя месячная зарплата. В общем, он заподозрил подвох. Я тоже не мог поверить, что прополимерил деньги, стоящие в графе «итого за год». По моим ощущениям, будь у меня на руках такая сумма, я бы огого…




Читать дальше →