Ты право, пьяное чудовище

[egovoru]

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

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

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

Сэр Роджер Пенроуз о платоническом мире математических объектов

Спасибо уважаемой yoginka, чей интерес к теме сподвигнул меня на чтение второй книжки Пенроуза.

Comments

[greygreengo.livejournal.com]

А где Вы с Пенроузом на брудершафт пили?

[egovoru.livejournal.com]

Я так и подумала, что читатели непременно отнесут обращение в заглавии поста на счет Пенроуза :) На самом деле, конечно, эти строчки - просто первое, что мне приходит в голову при слове "истина". Ну, может, после соответствующих пушкинских строк, но те я уже использовала в каком-то прежнем посте.

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

[noname-rambler.livejournal.com]

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

[egovoru.livejournal.com]

"алгоритмически выразить поиск такого числа"

Проблема в том, что я не до конца уверена, что действительно понимаю, что такое алгоритм. Тем более, что разные люди используют это слово в немного разных значениях: вот у Юрия Манина (https://egovoru.livejournal.com/118823.html), например, и фермент - алгоритм :) Надо отдать ему должное, Пенроуз в своей книжке четко оговаривает, что он под алгоритмом будет понимать машину Тьюринга. Но я не уверена, что я достаточно четко представляю себе эту машину, чтобы рассуждать о том, что она может сделать, а что - нет :( А Вы?

[greygreengo.livejournal.com]

Стоит ли упоминать о наличии принципа полной и неполной математической индукции в теории доказательств?
Алгоритмизация принципа - задача не до конца поставленная в рамках современных языков программирования, но вполне может иметь решение в рамках нейросетевого моделирования, или схемы обучения с учителем, которая до сих пор актуальна в теории ИИ. Учитель говорит, что А - невозможно, и, очерчивает границы до которых обучаемый (одно- или многослойный перцептрон) может зайти за эти границы. А при обратном прогоне показывает, где и как выход за границы возможного упрощает или усложняет обучение.

Всегда люблю здесь цитировать именно это: - "она начиталась всяких прелестных историй о том,
как дети сгорали живьем или попадали на съедение диким зверям,
-- и все эти неприятности происходили с ними потому, что они не
желали соблюдать простейших правил, которым обучали их друзья:
если слишком долго держать в руках раскаленную докрасна
кочергу, в конце концов обожжешься; если поглубже полоснуть по
пальцу ножом, из пальца обычно идет кровь; если разом осушить
пузырек с пометкой ``Яд!'', рано или поздно почти наверняка
почувствуешь недомогание."
Кэрролл это еще во времена до Джона Булля, основателя буллевой логики, предсказывал. Не в этом ли ценность вот таких, вечных предупреждений, оформленных в красивые рамки детских сказок?

[bluxer.livejournal.com]

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

Что касается аксиом, то надо полагать, они не устанавливаются, а объявляются.

[egovoru.livejournal.com]

"машине Тюринга не хватает знания каких-то общих концепций вроде того, что делится на два, а что нет"

А почему же нельзя сообщить машине эти знания в качестве начальных условий?

"они не устанавливаются, а объявляются"

А в чем же разница между этими двумя словами?

[alex-new-york.livejournal.com]

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

[egovoru.livejournal.com]

"массу логических конструкций, автоматическая применимость и оправданность которых совершенно не очевидна"

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

[xgrbml.livejournal.com]

Of course, mathematics is discovered, not invented.

Высказывание про машину Тьюринга и нечетное число, которое можно представить в виде суммы двух четных, лишено смысла: машин Тьюринга много. Как насчет такой, которая напечатает "таких нет" и остановится?

[egovoru.livejournal.com]

"mathematics is discovered, not invented"

В нашу компьютеризированную эпоху, действительно, легко стать платонистом :) Но меня, признаться, рассуждения о том, что в основе физического мира лежат не квантовые поля или суперструны, а "голая информация", приводят в недоумение: по мне, сколько ни говори "халва", во рту сладко не станет!

А Вы, вероятно, смогли бы объяснить мне, что же все-таки имел в виду Джон Уилер, когда отчеканил свое знаменитое "It from bit"? Я даже попыталась почитать его исходную статью об этом (http://cqi.inf.usi.ch/qic/wheeler.pdf), но она, увы, далеко превосходит мои возможности понимания :(

"Как насчет такой, которая напечатает "таких нет" и остановится?"

Пенроуз почему-то считает, что ни одна машина к этому не способна. Из чего он делает глобальный вывод о том, что человеческое мышление и сознание неалгоритмизируемо. Мне же кажется, что рассуждать об этом до того, как мы выяснили нейрофизиологические и биохимические механизмы мышления и сознания, совершенно бессмыссленно. А Вы что думаете?

[3seemingmonkeys.livejournal.com]

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

[steblya-kam.livejournal.com]

Именно. У меня примерно так и было. Я оказалась слишком большой материалисткой для математики :-)

[egovoru.livejournal.com]

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

[eldhenn]

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

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

[egovoru.livejournal.com]

"Существует ли нечётное число, которое можно представить в виде суммы двух чётных, и если существует, найдите такое число"

Я дословно воспроизвела формулировку Пенроуза: "Find an odd number that is the sum of two even numbers".

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

[woodenfriend.livejournal.com]

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

[egovoru.livejournal.com]

Вот и меня тоже как-то смущает утверждение, что компьютер не может справиться с задачкой, упомянутой в посте. Я надеялась, что среди читателей найдется кто-то, согласный в этом с Пенроузом, и тогда он сможет объяснить мне, что тот имеет в виду, но пока такого не нашлось :(

[yoginka.livejournal.com]

Я вам еще не надоела?

//аксиомы, то есть, утверждения, принятые за истину чисто условно, по договоренности.//
- Это редко бывает. Обычно имеется в виду некая модель/интерпретация, которой теория должна соответствовать. И из этих соображений выбираются аксиомы для теории. В частности, так было и с арифметикой Пеано. Сначала знали, что 2х2=4 из опыта (модели), а аксиомы подбирались так, чтобы этому не противоречили. Иными словами, чаще всего модель первична, аксиоматика вторична.

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

//Но я что-то не могу поверить, что компьютер нельзя запрограммировать так, чтобы он сразу же сообщал, что такого числа не может быть, потому что не может быть никогда? //
- Можно запрограммировать. Как можно и любой конкретный частный случай, 10 случаев, 1000000 случаев. Для всех примеров, которые приводит Пенроуз, можно запрограммировать остановку. И для любого другого, который кто-то предложит, человек может запрограммировать остановку. Можно сделать алгоритм, в который вручную заложено огромное количество подобных случаев, и он будет успешно с ними справляться. Но споткнется на том, который в него не заложили. А для всех подобных частных случаев вручную запрограммировать остановку нельзя, просто потому что их бесконечное количество (об этом я уже писала вам).

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

[egovoru.livejournal.com]

"Это редко бывает"

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

"Обычно имеется в виду некая модель/интерпретация"

Должна признаться, что из статьи в Вики я так и не поняла, что же такое "модель" в математике. Обычно это слово употребляют, когда говорят о математических моделях физических явлений, и это я хорошо понимаю. Но что такое, например, "модель арифметики Пеано", от меня начисто ускользает :(

"А человек как-то ухитряется распознавать подобные ситуации для задач, которые он первый раз видит"

Разве? Вот, например, бинарная проблема Гольдбаха (проблема Эйлера): никто не может ни доказать ее, ни опровергнуть уже более 250 лет.

"О том, как выбирают аксиому, говорится в доказательстве теоремы Геделя. В нем это важный момент"

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

[eldhenn]

> А человек как-то ухитряется распознавать подобные ситуации для задач, которые он первый раз видит.

"Я путаю кванторы" (c)

[a-gorb.livejournal.com]

Эпиграф
Давида Гильберта спросили об одном из его бывших учеников. «А, такой-то? — вспомнил Гильберт. — Он стал поэтом. Для математики у него было слишком мало воображения.»
[известный анекдот]

Деятельность математика не сводится «к преобразованием аксиом по заранее выбранным правилам», огромную роль играет воображение. (Оно является наиболее загадочной способностью человека и, на мой взгляд, тем, что делает человека человеком.) В самом деле, ведь даже на уровне «школьной» математике, когда многое из нее можно сделать наглядным, порядок доказывания той или иной теоремы надо в каком-то смысле угадать, вообразить, прежде чем облечь его в логически последовательную форму. Да и сами теоремы сначала надо придумать, найти. Ведь нигде нет готового списка теорем, которые надо всего лишь доказать. Поэтому деятельность математика не
алгоритмизируема, как алгоритмизируемо (пока?) воображение.

”Но я что-то не могу поверить, что компьютер нельзя запрограммировать так, чтобы он сразу же сообщал, что такого числа не может быть, потому что не может быть никогда?”
Компьютер программируется человеком с учетом возможностей этого компьютера. Что запрограммируешь, то и будет. Нет проблем, написать программу, которая на задачу «найти нечетное число, которое можно представить в виде суммы двух четных» сразу отвечает, что решения не существует. Это мы свое уже готовое решение задачи заложили в компьютер. Так часто делают, компьютер при этом лишь облегчает проведение вычислений, представление ответа и т.п.
Другой вариант – мы не знаем решения задачи и хотим его найти. Для этого, разумеется, все равно нам нужно иметь алгоритм ее решения. Тут сразу надо иметь в виду ограничения, которые накладывает устройство компьютера. Например, нам надо решить дифференциальное уравнение движения спутника в поле тяготения Земли и Луны и найти его траекторию, которая нам заранее не известна. Но компьютер не «умеет» работать с бесконечно малыми дифференциалами. В результате дифференциальное уравнение мы представляем в виде конечных разностей и разрабатываем алгоритм его решения, который уже представляем в виде программы.
Применительно к задаче о четных и нечетных числах то же можно написать программу, которая будет решать эту задачу, не опираясь на заранее известный ответ. Например, это может быть простой перебор нечетных чисел с проверкой каждого на такую возможность. В результате мы получим, что ответ не найден. Тут такая же сложность, как и с бесконечно малыми. Компьютер не умеет работать с бесконечно большими числами, поэтом нам самим придется ограничить то максимальное число, до которого он будет вести перебор.
Такого рода компьютерные методы то же находят свое применение. Скажем, возникает гипотеза, что некая теорема верна. Человек способен самостоятельно перебрать небольшое число вариантов, а вот компьютеру можно поручить перебрать большее количество вариантов. Такого рода перебор бывает полезен во всякого рода задачах комбинаторики, теории вероятности, игр и т.п. Он не дает строгого ответа, но дает некие основания, что теорема верна и имеет смысл искать ее доказательство. А уж если компьютер обнаружит контр-пример, то ситуация немедленно проясняется – теорема не верна.
Еще отмечу, что на основе всякого рода алгоритмов, возможно построение доказательств в математике, в частности теорема Геделя о неполноте может быть доказана на основе теории алгоритмов.

[egovoru.livejournal.com]

"порядок доказывания той или иной теоремы надо в каком-то смысле угадать"

Разумеется, причем угадать надо не только доказательство теоремы, но, в первую очередь, саму ее формулировку! В английском языке есть специальное слово "conjecture", которого, мне кажется, сильно не хватает в русском (тем более, что корень-то все равно латинский). По-русски обычно говорят "гипотеза" (Римана и т.д.), но мне кажется, это не совсем удачно, потому что гипотеза - это то, что проверяют экспериментом, а conjecture - это то, что требуется вывода из аксиом по правилам логики.

В смысле необходимости угадывания математика ничем не отличается от естествознания; принципиальное различие, однако, состоит в том, что происходит после этого. От математика требуется вывести угаданную им конъекцию (так, наверное, это слово должно звучать по-русски?) из аксиом по правилам логики, от естествоиспытателя - проверить гипотезу экспериментом.

"Но компьютер не «умеет» работать с бесконечно малыми дифференциалами"

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

"Такого рода компьютерные методы то же находят свое применение"

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

[niktoinikak.livejournal.com]

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

[(Anonymous)]

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

Первокласник не разбирается - он "знает".

Можно ли заложить в машину? Да запросто. Если перед делением числа X на число Y я поставлю проверку Y на ноль и обход деления в случае true, то никакого краш не будет, но даже если не поставлю и случись X/Y при Y=0, на экран вылетит divide overflow. Ну да и? При чем тут машина Тюринга или компьютер? Если бы мы знали что делать при делении на нуль - ОК, а так? Чего мы хотим от компьютера? Чтоб он выдал новое "знание"?

Не совсем понял какое отношение запрограммировать "чтоб сразу"? Имеет отношение к первокласнику, который "разбирается"?

Запрограммировать компьютер искать два четных чтоб в сумме давали нечетное? Да дело трех минут и да не зависнет, но свалится в вечный цикл пока хватит разрядной сетки. Все зависит от - как заложить. При современной многозадачности и корректном программировании вполне себе будет молотить в фоне без всякого зависания. И что? Тюринг то тут причем? Ты "сказал" - машина отработала, свободой воли в отличии от первокласника машина не обладает, будет делать пока не остановишь. Заложить это на уровень процессора? Чтоб машина также "знала" как и первокласник? Да тоже можно, только зачем? Кто из программеров будет заниматься поиском нечетного по сумме двух четных? Хотел бы посмотреть на такого, особенно учитывая что функции которые придется применять в принципе исключают подобную глупость, в виду очевидности )).

Что то я совсем не понял о чем Пенроуз, надо будет почитать, мне кажется что то не так в Вашем изложении.

ps Деление на ноль аж бегом, сплошь и рядом. Нечетное по двум четным? Зачем? Где? Как отвлеченка - ОК. Где на практике может такое встретиться? Предложите вариант? Вот реальный вариант, чтоб можно было сказать - в результате этой практичной расчетной вещи мы зависли. Ммм??

[egovoru.livejournal.com]

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

[(Anonymous)]

Ой нет. Тут я как раз соглашусь с Вами 100%. Я считаю что тут одно из двух, толи у грудничков есть какой то очень простой алгоритм первоначальной нарезки реальности (безумно простой, как все гениальное) который затем отмирает за ненадобностью - переходим на более сложные алгоритмы. Толи надо признавать искру божью. В любом случае нужно рыть там, до года (от силы двух). Наше взрослое понимание ведет не туда и не к тому. Это как видеть результат работы операционной системы ничего не зная о BIOS и о том как ОС загрузилась. Аналогия практически прямая, только мы не перегружаемся, впал в детство - конец, вторично этот механизм не запускается, по крайней мере я не слышал. Не там они роют как по мне.

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

Все эти недостатки вычислительных мощностей или тесты Тьюринга - ВS. Не там собака порылась. Да кстати и уверен что касается ИИ, совсем не об этом Тьюринг говорил. То что мы хотим от ИИ сейчас и то что подразумевал Тьюринг - разные вещи. Трехлетний ребенок тест Тьюринга не пройдет, но интеллектом безусловно обладает, глупо предпологать что Тюринг этого не видел

[egovoru.livejournal.com]

"В любом случае нужно рыть там, до года (от силы двух)"

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