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

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

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

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

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




Edited at 2018-07-26 04:11 pm (UTC)

Of course, mathematics is discovered, not invented.

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

Edited at 2018-07-26 06:17 pm (UTC)

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

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

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

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

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

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

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

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

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

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

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

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

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