Критерий истинности в математике

[Anton_Peplov]

epros в сообщении #1135973 писал(а):

А разве нет? Вроде, он доказал её отнюдь не в аксиоматике Пеано первого порядка. То бишь, аксиоматика явно была сильнее, чем минимально необходимая.

А кто говорил, что компьютерное доказательство обязательно проводится в минимально необходимой аксиоматике? Имеет смысл полагать, что все построения Уайлса, включая исходные посылки, выразимы в ZFC:) Ну и чего, кто-нибудь предъявил найденное компьютером доказательство результата Уайлса в формальной ZFC? Верите ли Вы в то, что в обозримом будущем кто-то его предъявит?

[mihaild]

epros в сообщении #1135973 писал(а):

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

Равно как и нет оснований для уверенности в обратном. Но кажется мы тут можем до бесконечности повторять истинные но неинтересные утверждения:)

[epros]

Anton_Peplov в сообщении #1135975 писал(а):

Ну и чего, кто-нибудь предъявил найденное компьютером доказательство результата Уайлса в формальной ZFC?

Ха, а кто-нибудь давал компьютеру задание поиска доказательства именно в ZFC? Это ж надо было фантазию проявить в выборе аксиоматики, а на это компьютеры обычно не программируют за ненадобностью.

[Anton_Peplov]

epros в сообщении #1135982 писал(а):

Ха, а кто-нибудь давал компьютеру задание поиска доказательства именно в ZFC?

А что, никто не дает компьютерам заданий доказывать теоремы в ZFC?

[epros]

mihaild в сообщении #1135978 писал(а):

мы тут можем до бесконечности повторять истинные но неинтересные утверждения

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

[Anton_Peplov]

epros в сообщении #1135986 писал(а):

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

А такого предположения никто здесь, кажется, не делал. Я, например, обращал внимание лишь на то, что "правильных базовых алгоритмов" мы не знаем и неизвестно, когда узнаем. Вытащить их из мозга великих математиков на сегодняшний день нет никакой практической возможности.

[epros]

Anton_Peplov в сообщении #1135983 писал(а):

А что, никто не дает компьютерам заданий доказывать теоремы в ZFC?

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

-- Вт июл 05, 2016 23:52:28 --

Anton_Peplov в сообщении #1135987 писал(а):

А такого предположения никто здесь, кажется, не делал

Я исхожу из того, что фразу "нет оснований для уверенности в обратном" можно трактовать как предложение рассмотреть это в качестве предположения.

-- Вт июл 05, 2016 23:55:57 --

Anton_Peplov в сообщении #1135987 писал(а):

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

Ну да, разумеется, между "практической невозможностью сегодня" и "принципиальной невозможностью" лежит пропасть, которая позволяет надеяться, что первая когда-нибудь потеряет актуальность.

[mihaild]

epros, я под "компьютером" всё время подразумевал "компьютер, аналогичный современным" (т.е. полиномиально эквивалентный машине Тьюринга).
(а незнание биологии и квантовой механики мешает мне увидеть мистику в способности мозга решать что-то из $BQP \setminus PSPACE$ за полиномиальное время - она там правда есть?)

[epros]

mihaild в сообщении #1135991 писал(а):

я под "компьютером" всё время подразумевал "компьютер, аналогичный современным" (т.е. полиномиально эквивалентный машине Тьюринга)

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

[mihaild]

epros в сообщении #1135995 писал(а):

Современные компьютеры архитектурно неэквивалентны машине Тьюринга, ибо многопроцессорны.

Если считать, что число процессоров ограничено полиномом, то мы всё равно остаемся в $P$.

[whitefox]

epros в сообщении #1135995 писал(а):

Современные компьютеры архитектурно неэквивалентны машине Тьюринга, ибо многопроцессорны.

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

[epros]

whitefox в сообщении #1135999 писал(а):

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

Это верно, но при решении задач ограниченной сложности, если не возникает переполнения по загрузке процессоров, то это не имеет значения. Кстати, квантовый компьютер тоже по-сути параллельный вычислитель. Например, алгоритм факторизации Шора имеет на нём эффективность $N^3$, но это только в том случае, если $N$ не настолько велико, чтобы потребовалось больше кубитов, чем имеется.

[arseniiv]

Rasool в сообщении #1135963 писал(а):

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

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

[whitefox]

epros в сообщении #1136002 писал(а):

Кстати, квантовый компьютер тоже по-сути параллельный вычислитель.

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

[Rasool]

Anton_Peplov в сообщении #1135987 писал(а):

epros в сообщении #1135986 писал(а):

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

А такого предположения никто здесь, кажется, не делал. Я, например, обращал внимание лишь на то, что "правильных базовых алгоритмов" мы не знаем и неизвестно, когда узнаем. Вытащить их из мозга великих математиков на сегодняшний день нет никакой практической возможности.

*Предположительно* Может быть, изготовить некую сложную нейросеть и обучить ее на примерах доказательств?