![[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}
no subject
Date: 2002-11-13 11:01 am (UTC)Т.е. вот нам представлена машина Тьюринга для вычисления F (например, в качестве кандидатов можно перебирать все машины по номерам). Для того, чтобы ей пользоваться, мы хотим также иметь сертификат - конечного размера запись доказательства того, что данная машина вычисляет F (причём ни в коем случае не очередную машину, "генерирующую" доказательство, а законченный продукт). Понятно, мы сможем обладать способом построить это доказательство для одной из двух тривиальных машин после того, как гипотеза Гольдбаха будет решена. А разговаривать о "существовании" доказательства (конечно, оно существует - только мы его не знаем) также бесполезно, как о существовании данной машины Тьюринга. Единственный интересный вопрос, пришедший на эту тему мне в голову - а возможно ли построить пару машина/доказательство, не решив гипотезу? Ведь машина может работать неопределённо долго (например, перебирать последовательно все математические рассуждения на предмет, а не решают ли они гипотезу) при том, что неконструктивное доказательство правильности работы машины вполне можно сформулировать.
Этот подход сводит затруднение в определении вычислимости/невычислимости в область доказуемости/недоказуемости, которая вполне устоялась и более глубоко проработана логиками в 20-м веке. Подойдёт?
Re:
Date: 2002-11-13 03:11 pm (UTC)а возможно ли построить пару машина/доказательство, не решив гипотезу?
С интуитивной точки зрения - конечно, невозможно. В этом-то и суть - обычный математический подход говорит нам, что есть машина, и есть док-во, но интуитивно мы понимаем, что это обман, "наколка", и что на самом деле вычислить F мы сможем только тогда, когда решим проблему. Но у нас нет удовлетворительного теоретического подхода к вычислимости, который бы соответствовал этой нашей интуиции.
no subject
Date: 2002-11-13 04:53 pm (UTC)Нам не нравится ситуация, когда "абстрактно-математически" функция вычислима, но всё что мы имеем "на настоящий момент" - две машины, ровно одна из которых действительно вычисляет функцию, но нам неизвестно, какая (машина есть, но мы не можем ею воспользоваться).
Чтобы "мочь воспользоваться", введём более узкое понятие "полезной вычислимости" или "верифицируемой вычислимости". В этом случае мы рассматриваем более сложный объект: машина + формальная спецификация функции F + формальное доказательство того, что эта машина вычисляет эту функцию F. Для пущей пользы можно даже включить в доказательство верхнюю оценку времени работы машины в зависимости от аргументов функции.
Если бы одна из тривиальных машин была снабжена необходимыми атрибутами верифицируемой вычислимости, мы имели бы решение гипотезы Гольдбаха. Вопрос, интересный для меня: представим нетривиальную машину, вычисляющую F - она выдаёт результат не сразу, а после выполнения некоего сложного алгоритма, сложность которого мы оценить не можем. Можно себе представить и доказательство того, что она вычисляет F (второй атрибут - формальную спецификацию F - можно опустить ввиду тривиальности, он нужен только для определения того, что доказывает третий атрибут - и для отсеивания нонсенсов типа "математико-исторических" задач). Почему Вы считаете, что такая конструкция не может быть сооружена в интуиционистской логике?
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)no subject
Date: 2002-11-13 05:08 pm (UTC)Так вот, предложенная "верифицируемая вычислимость" - соответствует?
А про мой вопрос насчёт нетривиальной машины можно забыть - всё более-менее понятно, скорее всего, такую машину сконструировать можно, и доказательство - можно (конструктивистское даже), только вот оценить время работы мы не сможем - или это будет совершенно астрономическое число (иначе математики бы давно уже использовали такие конструкции для своих нужд - чего не происходит :^) ).