Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

конструктивизм и машины Тюринга: мысли вслух

Возьмём какую-нибудь знаменитую нерешённую математическую задачу. Например, проблему Гольдбаха: любое чётное число больше 2 может быть представлено в виде суммы двух простых чисел. Обозначим это утверждение буквой G. Либо G, либо не-G верно; но математики пока не знают, какая из двух альтернатив верна.

Теперь определим функцию F на множестве всех натуральных чисел N таким образом: для любого натурального числа n F(n)=1 если утверждение G верно, и F(n)=0 если утверждение G неверно.

Таким образом, если гипотеза Гольдбаха верна, то функция F даёт значение 1 для любого аргумента, а если неверна - значение 0. Такое определение функции F вполне законно в обычной математике.

Теперь спросим: вычислима ли функция F? С точки зрения обычной математики F несомненно вычислима. Ведь функция вычислима, если существует машина Тюринга (грубо говоря, абстрактная программа, бегущая на идеальном компьютере с неограниченной памятью), которая для каждого аргумента правильно вычисляет эту функцию. А в данном случае для функции F несомненно существует такая машина Тюринга! Если гипотеза Гольдбаха верна, то это машина, всегда выдающая в качестве ответа 1; если неверна - машина, всегда выдающая 0. В любом случае, такая машина существует.

Но если функция F вычислима, то я хочу вычислить её значение. Чему равно F(5)? Нет ответа, и не будет, пока математики не решат проблему Гольдбаха. Если никогда не решат - никогда не будет ответа.

Что-то, наверное, не так в математическом определении вычислимости, если функция может быть вычислимой, и при этом вычислить её мы не можем, даже теоретически. Что именно не так?

Посмотрим на проблему с другой стороны. Все машины Тюринга можно перенумеровать в одной длинной бесконечной последовательности, присвоить каждой натуральный порядковый номер. При этом функция является вычислимой, если существует число, обозначающее машину Тюринга, к-я вычисляет эту функцию (т.е. на каждое значение аргумента рано или поздно останавливается и выдаёт правильно значение функции). Пусть номер машины, которая всегда выдаёт единицу, будет 10 (например), а номер машины, которая всегда выдаёт ноль - 15. Тогда наша функция F вычислима: существует число, обозначающее машину Тюринга, к-я вычисляет F. Это число 10 если гипотеза Гольдбаха верна, и 15 если неверна. В любом случае существует такое число; но какое именно число, мы не знаем.

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

Для интуиционистов эта невозможность - знак неадекватности обычной математики. В частности, Хейтинг (к-го обычно по-русски пишут Гейтинг) использует подобный аргумент для демонстрации необходимости интуиционистской логики. В интуиционистском подходе никаких проблем не возникает, потому что функция F плохо определена - для её определения используется запрещённый вид закона исключённого третьего (в данном случае это утверждение "либо G, либо не-G).

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

Что же тогда делать с описанной выше проблемой вычислимости функции F? Можно просто закрывать на неё глаза, что обычно и делают. В конце концов, математической проблемы здесь нет; ну да, функция F вычислима, ну и что? Есть проблема философская, проблема совместимости нашего интуитивного понятия о вычислимости и строгого математического определения, долженствующего это понятие описать в математических терминах. Тогда можно случаи, подобные данному, считать маргинальными уродцами, в обычной практике не встречающимися (что верно или почти верно) и поэтому никаких изменений не требующими.

Но, может быть, есть какой-то способ изменить понятие вычислимости, приблизить его к интуитивной возможности вычислить, к "держанию в руках", не выплёскивая при этом ребёнка вместе с водой, не втискивая математику в прокрустово ложе интуиционизма?
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 45 comments