Вопрос по теореме Геделя

[tac14]

Xaositect в сообщении #1037285 писал(а):

Ну то есть, как вариант, можно стать ультрафинитистом и сказать: меня интересуют только утерждения, в которых все числа не превышают $10^{100}$.

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

-- Ср июл 15, 2015 16:15:20 --

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

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

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

[Xaositect]

tac14 в сообщении #1037458 писал(а):

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

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

[tac14]

Но еще раз, чтобы зафиксировать, проблематика Геделя упирается в то, что мы хотим в формальных системах пользоваться бесконечными числами и/или хотим чтобы в системе была разрешена рекурсия ?

-- Ср июл 15, 2015 16:29:33 --

Xaositect в сообщении #1037459 писал(а):

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

Вот это очень хорошо. Т.е. все таки можно это сравнивать? Один из начальных мои вопросов это как раз и спрашивал:

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

[epros]

tac14 в сообщении #1037458 писал(а):

Не можно, а нужно, если мы хотим рассуждать о реальном мире (степень только надо выбрать соответствующую).

Число Грэма.

tac14 в сообщении #1037458 писал(а):

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

Это примерно то же самое, что формализованное доказательство. Программирование -- в некотором смысле разновидность математики.

[Deggial]

tac14 в сообщении #1037458 писал(а):

Не можно, а нужно, если мы хотим рассуждать о реальном мире (степень только надо выбрать соответствующую).

tac14, докажите это утверждение, согласно правилам дискуссионного раздела.

[Xaositect]

tac14 в сообщении #1037460 писал(а):

Но еще раз, чтобы зафиксировать, проблематика Геделя упирается в то, что мы хотим в формальных системах пользоваться бесконечными числами и/или хотим чтобы в системе была разрешена рекурсия ?

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

В принципе, это, наверное, можно назвать "чтобы в системе была разрешена рекурсия".

-- Ср июл 15, 2015 15:41:51 --

tac14 в сообщении #1037460 писал(а):

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

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

[epros]

tac14 в сообщении #1037460 писал(а):

мы хотим в формальных системах пользоваться бесконечными числами и/или хотим чтобы в системе была разрешена рекурсия ?

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

tac14 в сообщении #1037460 писал(а):

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

В каком-то смысле связаны. Если бы Вы могли точнее сформулировать вопрос, то получили бы более конкретный ответ. В частности, пример теоремы Гудстейна -- это можно считать про "рекурсию на языке программирования". Есть ещё масса примеров недоказуемости чего-то в чём-то. И, скажем, можно привести пример конкретной невычислимой функции $\Sigma : \mathbb{N} \mapsto \mathbb{N}$. Но что Вы хотите услышать -- непонятно.

[alhimikoff]

Почитал википедию на эту тему
https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 1%82%D0%B5

Как вам такая формула, особенно $b^{5^{60}}$?


Из списка литературы - http://www.ams.org/journals/bull/1980-0 ... 4832-6.pdf
В конце такая теорема:
Для любой теории Т и любого утверждения Р, если Р может быть доказано в Т, то оно имеет другое доказательство из 100 сложений и умножений целых чисел.

Раз теорему Ферма доказали, значит надо приступать к поиску её доказательства за 100 сложений и умножений?

[***]

alhimikoff в сообщении #1078832 писал(а):

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

Контрпример, сумма 102-ух случайных чисел.

[Brukvalub]

*** в сообщении #1078836 писал(а):

alhimikoff в сообщении #1078832 писал(а):

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

Контрпример, сумма 101 случайного числа.

Это не контрпример, а просто отменная глупость.

[***]

Brukvalub в сообщении #1078838 писал(а):

Это не контрпример, а просто отменная глупость.

Поясните, почему глупость, не понимаю?

[Brukvalub]

*** в сообщении #1078839 писал(а):

Brukvalub в сообщении #1078838 писал(а):

Это не контрпример, а просто отменная глупость.

Поясните, почему глупость, не понимаю?

Сначала вы поясните, к какой теореме (к какому утверждению) вы привели свой "контрпример".

[***]

Brukvalub К процитированному в сообщении 02.12.2015, 14:53. Разве это имеет несколько толкований?

[Brukvalub]

*** в сообщении #1078841 писал(а):

Brukvalub К процитированному в сообщении 02.12.2015, 14:53. Разве это имеет несколько толкований?

Нет, это имеет одно толкование. Но вы его совсем не понимаете. С равным успехом вы могли бы привести в качестве контрпримера "табуретка".

[***]

Хорошо. Буквальное прочтение формулировки теоремы без учета контекста статьи показалось мне смешным. Зря влез.