Про Гёделя, Пенроуза и вычислимость (3)

[gul_kiev]

Продолжаю ту же тему, предыдущие посты: 1, 2.

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

Comments

[livelight]

> Как так получается, что для любого алгоритма невычислимых чисел не существует, а мы ими оперируем и приводим примеры таких чисел?

Здесь приведены примеры описания таких чисел, но не сами эти числа. А текст такого определения может быть обработан алгоритмом, которые выдаст ответ: "число, которое вы описали, невычислимо". Хотя, конечно, существуют и такие определения чисел, для которых ни человек, ни алгоритм не сможет сказать, вычислимо ли оно.

Ну и вообще, если мы отказываемся от Аксиомы Выбора или от неконструктивных чисел, то любое доказательства существования, и любые доказательства с действиями вида "возьмём число Х, обладающее свойством Y" (если мы уже доказали, что множество таковых непусто) превращаются в тыкву, и математика становится гораздо более пустой и безвидной :)

[gul_kiev]

> Здесь приведены примеры описания таких чисел, но не сами эти числа

В чём отличие примера числа от примера описания числа?
Когда мы приводим пример иррационального числа, скажем, корня из двух - это пример числа или описания числа? Или, скажем, пи - это число или описание?

> А текст такого определения может быть обработан алгоритмом, которые выдаст ответ: "число, которое вы описали, невычислимо"

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

[livelight]

> В чём отличие примера числа от примера описания числа

[gul_kiev]

> Добавляем вышеуказанную аксиому "если невозможно найти решение в классе задач X, то решения не существует"

Алгоритму нужно знать, невозможно найти решение в какой именно системе аксиом. И как только мы эту систему аксиом определяем, добавление аксиомы "если невозможно найти решение в классе задач X исходя из аксиом A, то решения не существует", это получается система аксиом B, в которой всё равно будут неразрашимые задачи, хоть и другие - те, неразрешимость которых в системе A недоказуема. А оперировать бесконечным количеством аксиом или рекурсивными аксиомами алгоритм не умеет.

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

[proshka_tjubik]

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