![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВозьмём какую-нибудь знаменитую нерешённую математическую задачу. Например, проблему Гольдбаха: любое чётное число больше 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 вычислима, ну и что? Есть проблема философская, проблема совместимости нашего интуитивного понятия о вычислимости и строгого математического определения, долженствующего это понятие описать в математических терминах. Тогда можно случаи, подобные данному, считать маргинальными уродцами, в обычной практике не встречающимися (что верно или почти верно) и поэтому никаких изменений не требующими.
Но, может быть, есть какой-то способ изменить понятие вычислимости, приблизить его к интуитивной возможности вычислить, к "держанию в руках", не выплёскивая при этом ребёнка вместе с водой, не втискивая математику в прокрустово ложе интуиционизма?
Теперь определим функцию 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 вычислима, ну и что? Есть проблема философская, проблема совместимости нашего интуитивного понятия о вычислимости и строгого математического определения, долженствующего это понятие описать в математических терминах. Тогда можно случаи, подобные данному, считать маргинальными уродцами, в обычной практике не встречающимися (что верно или почти верно) и поэтому никаких изменений не требующими.
Но, может быть, есть какой-то способ изменить понятие вычислимости, приблизить его к интуитивной возможности вычислить, к "держанию в руках", не выплёскивая при этом ребёнка вместе с водой, не втискивая математику в прокрустово ложе интуиционизма?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Re:
Date: 2002-11-13 05:05 pm (UTC)Вы хотите формализовать понятие "держания в руках". В обычной неинтуиционистской математике единственный способ его формализовать - с помощью квантора существования, и как мы видим в данном примере с функцией F, этот способ как минимум иногда неадекватен нашей интуиции. Это и есть наша проблема.
Вы говорите: вместо того, чтобы просто требовать машину, потребуем "машина+формальная спецификация функции F + формальное доказательство того, что эта машина вычисляет эту функцию F". Первый вопрос: формальная спецификация в каком именно формальном формате? Второй вопрос, более важный: ну и что? Предположим, мы этого требуем, и для нас "вычислимость" становится идентичной существованию этой тройки: машина+спецификация функции+доказательство адекватности.
Но тогда в случае функции F есть две разные тройки, которые отвечают нужным условиям в зависимости от верности G. Если G верна, то есть машина, формальная спецификация функции F (формализующая определение: для каждого x F(x)=1), и формально док-во того, что данная машина вычисляет эту функцию. Если G неверна, то есть другая машина, другая спецификация и другое док-во. Так или иначе, утверждение "существует такая тройка, что..." будет формально доказуемо, следовательно, функция F будет вычислима в соответствии с этим Вашим новым определением, но останется столь же невычислимой с интуитивной точки зрения.
Понятие "держать в руке машину" Вы заменили на понятие "держать в руке машину+формальную спецификацию+док-во адекватности машины спецификации". Но само понятие держания в руках от этого не стало более досягаемым; оно по-прежнему определяется квантором существования в обычной математике, и приводит к противоречию с интуицией в нашем случае.
Вот в чём моя проблема с Вашим подходом.
Re:
Date: 2002-11-13 05:42 pm (UTC)Я не понимаю, почему это верно.
А так-то конечно, F либо верифицируемо вычислима, либо нет - одно из двух, но что — мы не знаем... От этого тоже ни горячо, ни холодно, но мне кажется, что верифицируемая вычислимость ближе к нашей интуиции, чем "классическая" вычислимость (про которую мы знаем, что F вычислима - что противоречит нашей интуиции).
И это тоже не понимаю, почему верно. С моей точки зрения, как я описал в предыдущем комменте, F всегда "верифицируемо вычислима" точно так же, как она и просто вычислима. В обоих случаях имеется противоречие нашей интуиции.
no subject
Date: 2002-11-13 06:44 pm (UTC)Re:
Date: 2002-11-13 06:47 pm (UTC)no subject
no subject
Date: 2002-11-13 10:33 pm (UTC)Однако придираться - неконструктивно, и я решил вместо этого поточнее сформулировать моё решение (для себя самого) затруднения из Вашего корневого поста. Интересно, заинтересует ли оно кого-либо?
Re:
Date: 2002-11-14 05:59 am (UTC)