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

[Eimrine]

A_Nikolaev в сообщении #1132957 писал(а):

The Pernicious Influence of Mathematics on Science

Мне кажется это очень даже не офтопик. Критерия истинности в математике нет, есть только моделирование и аппроксимация. Опасностей в статье как-то не обнаружено.

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

[Rasool]

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

[arseniiv]

(Оффтоп)

Вот эта тема уже интереснее.

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

[Rasool]

Согласно теореме Геделя о неполноте формальной арифметики, множество всех истинных высказываний арифметики неперечислимо. Да и для достаточно богатых математических теорий нет полных и непротиворечивых теорий. Современные компьютеры, основанные на машине Тьюринга, ограничены в доказательстве теорем таких теорий. Если бы удалось построить машину, которая могла бы строить теории и метатеории самых разных математических областей, обеспечивая доказательство самых разных математических теорем, то задачу построения ИИ можно было бы считать выполненной.

[arseniiv]

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

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

Тогда давайте откажем человеку в естественном интеллекте. В человеческой голове ничего экстраординарного нет.

[epros]

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

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

Оригинальная трактовка. Какая именно из арифметик неперечислима? Вообще-то Гёдель доказал, что теория, содержащая арифметику (с возможностью разложения натуральных чисел на простые сомножители), содержит невыводимое истинное утверждение. Откуда неперечислимость?

[vicvolf]

Sonic86 в сообщении #1132102 писал(а):

Зачем этот вопрос находится в этом разделе без попыток решения - вообще непонятно.

Целиком согласен. Это скорее беседа на околонаучную тему.

[venco]

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

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

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

Оригинальная трактовка. Какая именно из арифметик неперечислима? Вообще-то Гёдель доказал, что теория, содержащая арифметику (с возможностью разложения натуральных чисел на простые сомножители), содержит невыводимое истинное утверждение. Откуда неперечислимость?

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

[Anton_Peplov]

venco в сообщении #1134411 писал(а):

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

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

venco в сообщении #1134411 писал(а):

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

Подмножество перечислимого множества не обязательно перечислимо.

[Rasool]

Я сам подобной темой интересовался лет 20 назад, сейчас все забыл, чтобы восстановить в памяти, залез в учебник по дискретной математики Кузнецова, главу про формальные системы. Может быть, я не точно передал смысл.

-- Вт июн 28, 2016 23:02:47 --

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

[epros]

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

в "естественной" модели соответствуют истинные высказывания

Интересно, как это определяется? Если я правильно понимаю Гёделя, модель, в которой истинны те и только те высказывания, которые выводимы, тоже достаточно "естественна". Хотя при этом окажется истинным высказывание, утверждающее противоречивость арифметики, ну да и пусть...

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

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

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

[Xaositect]

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

Интересно, как это определяется? Если я правильно понимаю Гёделя, модель, в которой истинны те и только те высказывания, которые выводимы, тоже достаточно "естественна". Хотя при этом окажется истинным высказывание, утверждающее противоречивость арифметики, ну да и пусть...

Такой модели же не существует. Либо истинно невыводимое утверждение о противоречивости арифметики, либо истинно невыводимое утверждение о непротиворечивости арифметики.
Для любой модели арифметики множество истинных утверждений неперечислимо.

[mihaild]

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

Современные компьютеры на базе машины Тьюринга это не умеют

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

Или вы хотите чтобы ИИ умел работать оракулом останова?

[Rasool]

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

Или вы хотите чтобы ИИ умел работать оракулом останова?

Есть же теорема о самоприменимости. Если бы удалось обойти ее ограничения...

[venco]

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

venco в сообщении #1134411 писал(а):

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

Не-не. Именно так: множество всех тех и только тех формул арифметики Пеано, которым в "естественной" модели соответствуют истинные высказывания, неперечислимо.

Да, это я в терминологии не разбираюсь, спутал "перечислимое" и "счётное".