![[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-12 08:02 am (UTC)Всё начинает звучать вполне осмысленно, если спросить: "существует ли такая машина Тьюринга, которая для данного X выдаёт одно из слагаемых его разложения на сумму простых?"
no subject
Date: 2002-11-12 08:08 am (UTC)Вообще, мне кажется, что на вопрос Анатолия есть осмысленный ответ, но как-то недосуг подумать.
no subject
no subject
Date: 2002-11-12 08:12 am (UTC)Re:
Date: 2002-11-12 08:14 am (UTC)Удачи на семинаре. Тебя ругать в воскресенье?
no subject
Date: 2002-11-12 08:15 am (UTC)no subject
Date: 2002-11-12 09:00 am (UTC)no subject
no subject
Date: 2003-01-20 04:17 pm (UTC)no subject
Date: 2002-11-12 08:11 am (UTC)no subject
Date: 2002-11-12 08:32 am (UTC)А интересен именно вопрос, существует ли МТ, которая *всегда* выдаёт такое разложение на два простых или же не существует.
Тот же вопрос "верна ли гипотеза Гольдфарба?", только по-иному завуалированный.
no subject
Date: 2002-11-12 08:59 am (UTC)no subject
Date: 2002-11-12 08:15 am (UTC)Krome togo, sama problema dostatochno izvestna v klassicheskoj matematike: dokazatel'stva suschestvovanija byvajut libo konstruktivnye (ja znaju mashinu Tjuringa, kotoraja ... - v Vashem primere) i nekonstruktivnye (k nim, naprimer, otnosjtsja vse dokazatel'stva "ot protivnogo"). Vtorye, obychno, prosche pervyh.
Clement
no subject
Date: 2002-11-12 09:47 am (UTC), а в "возможных мирах" - "возможно Х", "есть такой мир , где Х"
От этого до интуитивности все же очень далеко.
Пара вопросов
Date: 2002-11-12 09:32 am (UTC)2. Счётно ли множество машин Тюринга? Мне кажется, что нет.
Re: Пара вопросов
Date: 2002-11-12 10:04 am (UTC)2. Множество машин Тюринга, конечно, счётно. Каждую машину Тюринга можно закодировать своим натуральным числом, вложив в него то конечное количество информации, к-е определяет машину Тюринга (а именно, кол-во состояний и таблицу перехода машины).
Один момент
Хотелось бы отметить, что согласно теореме Гёделя о неполноте, вовсе необязательно, что утверждение G доказуемо в рамках имеющейся теории. Исходя из этого, вопрос о "вычислимости" функции F становится еще менее очевидным :))
Re: Один момент
Date: 2002-11-12 09:39 am (UTC)Re: Один момент
Date: 2002-11-12 02:28 pm (UTC)no subject
Date: 2002-11-12 12:35 pm (UTC)no subject
Date: 2002-11-12 02:22 pm (UTC)Почему? В рамках какой угодно математики разница, IMHO, очевидна: первое утверждение - это формулировка проблемы, т.е., собственно, проверяемое утверждение, а второе - это одно из возможных доказательств его истинности. В чем проблема?
Re:
Date: 2002-11-12 02:26 pm (UTC)В невозможности формализации второго утверждения. В неформальном рассуждении его можно использовать, но в конце концов в формальном доказательстве оно всё равно обозначает существование объекта.
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)Так вот, предложенная "верифицируемая вычислимость" - соответствует?
А про мой вопрос насчёт нетривиальной машины можно забыть - всё более-менее понятно, скорее всего, такую машину сконструировать можно, и доказательство - можно (конструктивистское даже), только вот оценить время работы мы не сможем - или это будет совершенно астрономическое число (иначе математики бы давно уже использовали такие конструкции для своих нужд - чего не происходит :^) ).
no subject
Date: 2002-11-13 03:17 pm (UTC)Вопрос об истинности гипотезы G можно сформулировать как вопрос о всеобщности U[С], а можно - как вопрос существования доказательства D(G{U,C}}. Очевидно, что эти две формулировки тождественны в рамках математической и формально-логической аксиоматики.
Можно пойти дальше и поставить вопрос о существовании доказательства всеобщности алгоритма A, реализующего проверку утверждения U[C] (машины Тьюринга мне не нравится здесь как путь к теории алгоритмов - ниже скажу, почему). Это приведет нас к вопросам доказательства самого алгоритма А и того, что он заведомо выдаст результат "истина" для любых конкретных N, удовлетворяющих C. Эти вопросы, в свою очередь, можно "разбить" на вопросы о существовании таких доказательств и их нахождении...
________
Все это не продвинет нас ни на йоту в вопросе о самой гипотезе.
Вот почему:
Машина Тюринга без "ленты", на которой она работает - не представляет никакого интереса (поэтому мне и не нравится тут машина Тьюринга - это "отсутствие данных" при выражении обычным алгоритмическим или формально-логическим языком сразу очевидно) и ничего не вычислит. По Вашему построению первая машина Тьюринга выполняет следующий алгоритм:
// Алгоритм А1
// if (G=true) then {F=true} else {F=false};
"Вычислить" что-либо сие тривиальное приспособление сможет только тогда, когда на "ленточке" будет записано значение G - или нолик, или единичка, которые в Вашем случае будут обозначать существование доказательства гипотезы. По теореме Геделя (под которую рассматриваемая Вами гипотеза попадает "тик в тик") мы не сможем дать этого ответа до тех пор, пока не докажем или не опровергнем гипотезу, и, кроме того, есть шанс (вероятность его ~0,5 ;-) ), что мы никогда не сможем дать ответа на этот вопрос.
Комплекс машин Тьюринга, который Вы предложили идентичен по сути следующему алгоритму:
// Алгоритм А2
// Step 1. Получить (или вычислить) очередные аргументы: N=Nk+1
// Step 2. if (N удовлетворяет условиям гипотезы) then {Step 3} else {Step 1}
// Step 3. вычислить значение G(N) (для Вашего случая - перебирать итеративно или рекурсивно все возможные разложения на множители, проверяя сомножители на простоту, и выходить из цикла (рекурсии) к Step 4, если сомножители - простые, и к Step 5 - если все итерации (рекурсивные вызовы) пройдены)
// Step 4. Записать результат Rn для текущего N как 1, перейти к Step 1.
// Step 5 Записать результат Rn как "0", перейти к Step 1.
(программисты, ужаснитесь :-) - сей алгоритм будет работать, пока не сожрет всю память...)
Как легко видеть, ни сам по себе алгоритм А2, ни его сколь угодно долгий "прогон" для математика (логика) доказательством гипотезы являться не будет (хотя если бы речь шла об экономической или психологической гипотезе, 10 000 000 проверок убедили бы любого скептика...- но на то она и математика). Т.е. этот алгоритм так же не вычислит F(G), как и А1.
Чтобы что-либо сказать о гипотезе G, придется (если мы решим попытаться это сделать довольно-таки китайским, но, может быть, и верным путем теории алгоритмов) доказать истинность либо ложность утверждения "R="1" для всех N, удовлетворяющего условиям гипотезы G", т.е. доказать не только, что сам алгоритм работает верно, но и то, какой именно бесконечный массив результатов (какие значения) он выдаст на бесконечном массиве данных (аргументов).
Можно переформулировать и иначе: "существует доказательство того, что алгоритм А2 всегда выдает 1" - и вот это утверждение (вполне тождественное как утверждению о всеобщности доказательства D(G{U,C}), так и утверждению о существовании доказательства гипотезы G{U,C}, так и - в конечном итоге - всеобщности U[C]) уже полностью формализовано в том же виде, что и изначально обсуждаемое первое утверждение.
В чем проблема?
no subject
Date: 2002-11-13 12:09 am (UTC)А может, какой-нибудь тральфамадорский математик ее уже миллиард лет назад доказал (или опроверг)?
Re:
Date: 2002-11-13 03:12 pm (UTC)Никаким, конечно. Верность или неверность гипотезы Гольдбаха существует независимо от того, доказали/опровергнули ли её в прошлом, настоящем, или будущем.
Re:
Date: 2002-11-13 03:37 pm (UTC)Re:
Date: 2002-11-13 03:50 pm (UTC)В случае гипотезы Гольдбаха я не знаю, верна ли она (не могу доказать, что верна или неверна), следовательно, не могу вычислить функцию F.
Re:
Date: 2002-11-13 04:34 pm (UTC)no subject
no subject
Date: 2003-01-19 08:50 pm (UTC)Re:
Date: 2003-01-19 10:40 pm (UTC)no subject
Date: 2003-01-19 10:41 pm (UTC)no subject
Date: 2002-11-13 03:41 pm (UTC)сравним вероятности существования доказательства гипотезы до того, как оное доказательство найдено и никто не проверял эту гипотезу на истинность прямыми вычислениями (очевидно, эта вероятность - 0,25, если принять во внимание теорему Геделя) и после того, как ее проверили 10 000 раз и все 10 000 раз получили, что она верна (но доказательство нам по прежнему неизвестно). В последнем случае для эмпирических наук вероятность существования доказательства для всех N, будет больше 0,25 (можно даже прикинуть по формуле Байеса для, напр., 10 и 10 000 проверок...), а для математика останется равной 0,25.
?
no subject
Date: 2003-01-20 04:05 pm (UTC)