gul_kiev: (buddha eyes)
Тест Тьюринга глубже и конструктивнее, чем люди обычно себе представляют.
Есть две стратегии поведения: руководствуясь пониманием, идеей, либо же руководствуясь расчётом, прогнозируемой выгодой.
Понимание, осознавание, идея всегда выигрывают у расчёта. Поэтому расчёт зачастую мимикрирует под идею.
Тест Тьюринга - это не только отличить человека от компьютера, это отличить понимание от расчёта. Любовь от имитации любви. Честного политика от лживого. Боль от симуляции боли.
Теоретическая разрешимость или неразрешимость этой задачи имеет много интересных следствий.
gul_kiev: (buddha eyes)
Я со школьных лет сталкивался с неразрешимостью некоторых задач, и уровень этой неразрешимости постепенно увеличивался, сейчас приблизившись к границам моего осознания.

Сначала я узнал, что не существует формулы для нахождения корней многочлена степени больше 4. Все мы знаем, как решить квадратное уравнение. Для уравнения третьей степени существует формула Кардано, которую мало кто помнит. Для уравнений четвёртой степени тоже существует формула, которая настолько громоздка, что её никто не только не помнит, но и не применяет. А вот для пятой степени и выше формулы нет. Не просто ещё не придумали, а доказали, что нет. Решения уравнения есть, а формулы для этих решений нет.
Дальше - больше )
gul_kiev: (buddha eyes)
Оказывается, не только Пенроуз математически доказал невычислимость человеческого сознания, но и Курт Гёдель в 1970 опубликовал математическое доказательство существования бога (об этом комментарии в том же блоге 1, 2, 3).
И это не стёб типа доказательства, что все лошади одного цвета, это вполне строгий и формальный вывод.
Что я об этом думаю )
gul_kiev: (buddha eyes)
Роджер Пенроуз написал книгу "Тени разума: в поисках науки о сознании", в которой, ни много ни мало, формально математически доказал невычислимость человеческого мышления (т.е. теоретическую невозможность его моделирования на компьютере).
Я попробую вкратце пересказать её основные положения для тех, кто читать саму книгу не собирается (может, заодно и сам лучше пойму). Там, на самом деле, интересно.

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

Теперь, собственно, доказательство невычислимости человеческого разума.
Можно перенумеровать все возможные алгоритмы, и входные данные представить в виде натурального числа. Это сделать не очень трудно, если вспомнить, что в математике натуральное число - это не uint64, а произвольное сколь угодно большое число (программисты вместо "число" могут это воспринимать как "строка" или "произвольный бинарный массив"). В частности, бинарный код программы (или её исходный код - неважно) - это число, и произвольные входные данные произвольного объёма - это тоже число. Таким образом, любому алгоритму (программе) можно поставить в соответствие некое натуральное число N. (Тут есть нюанс в том, что не для любого алгоритма существует реальная компьютерная программа в силу технических ограничений, но с этой проблемой успешно и почти независимо справились Тьюринг, Пост и Черч, вполне формализовав понятие алгоритма с математической точки зрения). Таким образом, произвольный алгоритм мы можем обозначить через Ck, а алгоритм, которому на вход даны некоторые данные - Ck(n).

Теперь представим, что нам нужно решить задачу: глядя на алгоритм, понять, завершится ли он, если его запустить с этими входными данными, или будет работать вечно? Например, мы видим алгоритм поиска минимального простого числа, больше заданного N - мы знаем, что он завершится. Переборный алгоритм поиска минимального нечётного числа, являющегося суммой двух чётных чисел, очевидно, не завершится (сумма двух чётных чисел всегда чётна). Завершится ли алгоритм поиска минимального чётного числа, больше двух, не являющегося суммой двух простых чисел, на сегодняшний день неизвестно (это гипотеза Гольбаха). То есть, задача наша, вообще говоря, не простая, и в полной мере мы её решить не можем. Однако, в некоторых случаях мы можем гарантировать, что данный алгоритм никогда не завершится. Как мы это определяем?

Предположим, что мы для этого используем некий алгоритм A, который, получая на вход два числа k и n, в каких-то случаях может определить, что алгоритм Ck(n) не завершается. В этом случае наш алгоритм A(k,n) завершается. Не обязательно он может определить завершаемость во всех случаях - мы ведь не все задачи можем решить. Достаточно того, что в некоторых случаях он работает.
Теперь рассмотрим алгоритм D(n), который всегда ведёт себя так же, как A(n,n), т.е. который, по сути, проверяет завершаемость алгоритма с номером n, если ему на вход дать данные n. Такой алгоритм, очевидно, существует, и пусть у него будет номер k, т.е. Ck(n) эквивалентно A(n,n), для любого n. Применим его для n = k. В этом случае алгоритм проверки окажется применён к самому себе, т.к. A(k,k) эквивалентно Ck(k), т.е. наш алгоритм A будет проверять завершаемость самого себя на входных данных (k,k). Если он завершится, то он окажется ошибочным, т.к. он тем самым будет утверждать, что он не завершается. Значит, он определённо не завершается, и таким образом не может определить завершаемость самого себя на входных данных (k,k). Однако мы при этом совершенно точно определили, что этот алгоритм на этих входных данных не завершается.
Вспоминая наше предположение о том, что алгоритм A - это и есть тот алгоритм, который мы используем для определения завершимости, мы получили противоречие.
Вывод: способ, которым мы определяем завершаемость алгоритма (а значит, разрешимость математической задачи), не является обоснованным алгоритмом.

Слово "обоснованным" тут взялось из варианта, когда A(k,k) завершается, тем самым ошибочно определяя незавершаемость Ck(k). В таком случае A(k,n) мы назовём необоснованным, т.е. дающим какие-то результаты, но не всегда верные. Судя по всему, Алан Тьюринг видел выход из этого парадокса именно в этом, он считал наличие ошибок необходимым атрибутом человеческого мышления. Если же предположить, что способность ошибаться не является фундаментальной способностью человеческого разума, то придётся признать, что человеческий разум действует не алгоритмически (т.е. некоторые его проявления невозможно промоделировать алгоритмом).

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

Что я об этом думаю )
gul_kiev: (buddha eyes)
В математике есть разные парадоксы, особенно в теории множеств. Многие утверждения интуитивно кажутся парадоксальными, хотя на самом деле (формально) никакого парадокса нет, математически всё корректно. Например, между любыми двумя рациональными числами находится бесконечное количество иррациональных, между любыми двумя иррациональными - бесконечное количество рациональных, а при этом иррациональных чисел много больше, чем рациональных (иными словами, если на числовой прямой взять случайную точку, то она наверняка окажется иррациональной). Есть и более заковыристые "парадоксы". Например, шар можно разделить на конечное количество связных частей, из которых можно сложить два шара такого же размера без пустот (парадокс Банаха-Тарского).

Большое количество этих парадоксов, обнаруженных в конце XIX - начале XX веков, назвали даже кризисом оснований математики.

Математика изначально требует "понимания" человеком, т.е. интерпретации. Есть отдельные попытки построить совсем абстрактные математические теории без интерпретаций (примерно как "просклонять словосочетание «глокая куздра»"), но это скорее исключение, чем правило. Одной из первых таких теорий была геометрия Лобачевского, для которой довольно скоро после её создания было придумано сразу несколько интерпретаций (наиболее известная - интерпретация Пуанкаре). Любопытный пример теории, насчёт которой наличие интерпретации неочевидно: N-мерная геометрия при N>3. Я бы всё-таки сказал, что интерпретация есть - как минимум, представление точек в виде массива из N вещественных чисел (соответственно, прямых, плоскостей, гиперплоскостей и т.д. - тоже через координаты). В этом смысле можно сказать, что "обычная" геометрия (планиметрия, стереометрия) имеет сразу как минимум две интерпретации - основную (которую приближённо рисуем) и координатную, и доказательство их эквивалентности - отдельная не очень простая задача.

Теперь вернёмся к теории множеств и к парадоксам. В начале XX века Курт Гёдель доказал интересную теорему. В несколько упрощённом виде и в одной из трактовок она звучит так: в любой достаточно сложной формальной системе (например, в арифметике, или, точнее, в аксиоматике Пеано) обязательно существуют утверждения, которые в рамках этой системы невозможно ни доказать, ни опровергнуть. В теории множеств такие утверждения скоро нашлись: в частности, континуум-гипотеза (существует ли множество мощности больше счётного, но меньше континуума, т.е., грубо говоря, в котором больше элементов, чем рациональных чисел, но меньше, чем действительных). Математики доказали, что ни наличие, ни отсутствие такого множества не будет противоречить имеющейся системе аксиом (Цермело-Френкеля, ZFC). Это один из математических фактов, противоречащих интуиции, а значит, и не вписывающийся в интерпретацию. Ведь говоря другими словами, мы определённо никогда не сможем привести пример такого множества. Разве это не доказывает его отсутствие? Но нет - если мы предположим, что оно всё-таки существует, это ничему не будет формально противоречить. Ещё интереснее ситуация с аксиомой выбора. Одна из формулировок: существует правило, по которому при любом разбиении множества натуральных чисел на два подмножества одно из них всегда будет иметь меру 1, а второе - меру 0 (и при этом любое конечное множество всегда имеет меру 0). Числа можно разделить на чётные и нечётные, на простые и составные, на степени двойки и прочие и т.д. - и в каждом случае одно из подмножеств должно иметь меру 1, а второе меру 0. Это утверждение (о существовании такого разбиения) тоже недоказуемо и неопровержимо. Значит, привести пример такого правила невозможно. Но если мы предположим, что оно всё-таки существует, это даёт нам множество возможностей (например, построение нестандартного анализа). В некоторых случаях, принимая аксиому выбора, мы можем, с одной стороны, доказать существование выигрышной стратегии, а с другой - доказать невозможность её применить. Хотя, казалось бы, разве невозможность применить выигрышную стратегию не означает её отсутствие? Пример: Трем мудрецам написали на лбу по вещественному числу. Они видят числа коллег, но общаться не могут. Каждый мудрец подает королю конечный список чисел. Если хоть один включил свое число в список, то мудрецы победили. Если верна аксиома выбора и континуум-гипотеза, то у мудрецов есть выигрышная стратегия (но привести её и, соответственно, применить, они не могут, и это тоже доказуемо).

Итак, теорема Гёделя. Роджер Пенроуз в своей книге "Тени разума" с её помощью формально доказал, что человеческий разум обладает свойством невычислимости, т.е. его теоретически невозможно промоделировать на обычном компьютере. Как бы заманчиво ни звучал этот вывод ("учёные признали существование души?"), я, как и многие другие, склонен искать ошибку в рассуждениях. И ошибку эту я вижу достаточно глубоко в основаниях математики, в оперировании бесконечностями и определении вещественного числа как бесконечной десятичной дроби. Одно из первых строгих определений вещественного числа дал Дедекинд, определивший его как сечение множества рациональных чисел, разбиение их на два подмножества A и B, в котором любое число из A меньше любого числа из B. Например, в A собраны отрицательные числа, и такие, для которых квадрат меньше двух, а в B - положительные, квадрат которых больше двух - такое сечение задаёт иррациональное число корень из двух. Можно доказать, что множество таких чисел непрерывно, т.е. что не существует такого разбиения действительных чисел на подмножества A и B, что у A нет максимального элемента, а у B нет минимального (как это бывает для рациональных чисел). Так вот, если такое сечение задавать математической фразой (формулой) конечного размера, то множество таких чисел будет счётным (таким же по мощности, как множество целых или рациональных чисел). Мы можем оперировать такими числами-формулами (назовём их "конечными"), их складывать-умножать-делить точно так же, как мы это делаем с вещественными числами, и всегда будем в результате получать те же самые "конечные" числа, это (счётное!) множество полно. Определяя числа таким образом, мы уходим от оперирования бесконечностями (ведь вещественное число - это бесконечная десятичная дробь). А значит (и это важно!) не теряем соответствия интерпретации. А пока есть интерпретация, не должно быть и парадоксов. Тут можно вспомнить отношение к математике Платона - он считал, что существует идеальный математический мир, грубым и искажённым отражением которого является наш реальный мир, но наше сознание обладает способностью познавать изначальный мир математики. Заложив понятие "бесконечность" в определение вещественного числа, мы сделали шаг от познаваемого мира математики Платона в сторону лишённой интерпретации абстракции. И сразу (точнее, не совсем сразу, но не в этом суть) получили парадоксы и противоречия.

Если мы можем доказать, что невозможно найти выигрышную стратегию - давайте в этом случае скажем, что её нет. Если мы можем доказать, что невозможно привести пример множества мощностью больше счётного, но меньше континуума - давайте считать это доказательством того, что такого множества нет. Нельзя из математической науки выбрасывать субъект математика, это показал Гёдель. Невозможно построить универсальный решатель задач или доказыватель теорем, т.к. он не будет обладать пониманием (интерпретацией), без которого математика невозможна. Существуют ли какие-либо числа, кроме тех, которые можно задать конечной математической фразой? Очевидно, что невозможно привести пример такого числа. Значит, их не существует в нашей интерпретации теории чисел!

Я, пожалуй, уточню, что я не предлагаю совсем отказываться от понятия "бесконечность". Не существует максимального натурального числа, значит, натуральных чисел бесконечно много. Но я предлагаю не оперировать бесконечностью как чем-то осознаваемым, как в задачах вроде "Собака догоняет человека, находящегося на бесконечном расстоянии от неё. Первый метр она пробегает за секунду, каждый следующий метр вдвое быстрее, чем предыдущий. Как быстро она догонит человека, движущегося с конечной скоростью?". Такие операции быстро приведут к парадоксам. А определение вещественного числа как бесконечной десятичной дроби по сути ничем не лучше формулировок в этой задаче. Говоря о сумме ряда 1+1/2+1/4+1/8+1/16+..., я предлагаю не оперировать бесконечным количеством слагаемых, а записывать вместо этого вполне конечную формулу Σ 1/2n, которую можно преобразовать в другую конечную формулу "2". Бесконечных формул не бывает.

Следующие возникающие вопросы: сколько же точек на числовой прямой (счётное или континуум)? И является ли "конечным" (представимым в виде конечной формулы) числом произвольная физическая величина (скажем, гравитационная постоянная или масса электрона)? Ведь, казалось бы, это невычислимые величины из физического (а не математического) мира, которые мы можем измерять с произвольной точностью, получая новые десятичные знаки, т.е. это вещественное число именно как бесконечная десятичная дробь, без какой-либо конечной формулы. С числовой прямой просто: как захотим, так и будет. То, что на ней есть иррациональные числа, легко показать (построить квадрат со стороной 1 и отложить отрезок, равный его диагонали - полученная точка рациональной не будет). Но вот наличие "бесконечных" чисел на ней показать не получится. Поэтому вполне можно решить, что числовая прямая является интерпретацией множества "конечных" чисел. С физикой несколько сложнее. Сейчас отношение массы протона к массе электрона неизвестно, поэтому никакой конечной математической формулы нет, и потому можно считать, что оно "бесконечное". Но после построения "теории всего" это отношение станет вычислимым, и отношение станет "конечным". То же можно сказать и про остальные физические величины. Так что тут вопрос сводится к тому, возможно ли построить теорию всего, или нет. Можно сказать: мы не знаем ответ на этот вопрос, поэтому предположение о том, что теорию всего построить нельзя, вполне законно, и в этом предположении физические постоянные не являются "конечным" числами даже в перспективе. Но это тоже не совсем так. Вместо физической постоянной можно рассматривать какое-нибудь полностью случайное число - например, на основании квантовых эффектов каждую секунду генерировать очередную случайную цифру. В каждый момент времени мы будем иметь вполне конечное (и даже рациональное) число, а рассматривать бесконечное время - это всё равно, что человека, находящегося на бесконечном расстоянии от собаки, это просто другая формулировка определения вещественного числа, не привязанная к реальности и не имеющая интерпретации. Так что и для описания физического мира (как приближённо измеряемого, так и полностью познанного) конечных чисел тоже совершенно достаточно.

Я сам знаю несколько слабостей этого подхода, но хотелось бы услышать критику со стороны.

UPD 24.05.2015 Как оказалось, существует целая теорема Лёвенгейма-Скулема, которая (если убрать формальности) говорит о том, что если непротиворечивая формальная система аксиом имеет бесконечную модель, то она имеет и счётную модель. И это строго доказывается. Из этого, в частности, следует, что счётная модель должна быть и у теории множеств, что, вроде бы, противоречит явно несчётным множествам мощности континуум. Это называется парадокс Скулема. Видать, эту теорему и связанный с ней парадокс я как-то интуитивно и почувствовал настолько, что описал их смысл тут. :)
gul_kiev: (Default)
В физике есть какое-то количество физических постоянных и какое-то количество единиц измерения.
Эти количества неразрывно связаны между собой: мы можем сделать одну из фундаментальных постоянных безразмерной (положить равной единице), тогда у нас и на одну из единиц измерения станет меньше. Например, вместо лошадиной силы или калории появится Джоуль, который уже не самостоятельная единица измерения, а кг·м22.
Таким образом всякие многочисленные единицы измерения сводятся к нескольким основным. В принципе, можно было бы и скорость света в вакууме принять за единицу, и измерять время в м-1. Но это уже было бы слишком неудобно в быту.

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

Следующий возникающий вопрос: что значит "остальные физические постоянные можно математически вывести из основных"?
Вот есть два числа: "пи" и "масса электрона". Оба действительные. π - иррационально, трансцендентно; me - наверняка сказать трудно, скорее всего, тоже.
Но если в формуле, описывающей мироздание, число π воспринимается нормально, то число me - нет, это не математическое описание. Почему, как формализовать отличие между этими числами?
π - это сумма ряда рациональных чисел. Но me - это тоже сумма какого-то ряда рациональных чисел, поскольку каждое действительное число является пределом последовательности рациональных чисел.

Можно определить "аналитическое число" или "математически познаваемое число" как число, которое можно записать математической формулой конечного размера (как сумма ряда или предел последовательности) - но какие символы можно использовать в этой формуле? Не получится ли парадокс, как с самым большим числом, которое можно описать фразой из не более двадцати слов? (Фраза "назовём самое большое число, которое можно описать фразой из не более двадцати слов, Q, и возьмём Q плюс один" состоит из менее 20 слов).

Множество "аналитических чисел" счётно, действительных - континуум. Любое число, которое мы можем описать математически - аналитическое. Если бы мы знали устройство мироздания, масса электрона была бы вычислимой, и тоже стала аналитическим числом, как и число "пи". Значит, она и есть аналитическое число, просто у нас пока недостаточно знаний, чтобы найти формулу для его записи. Получается, что мы принципиально не можем привести пример неаналитического числа и оперировать ими, несмотря на то, что их много больше, чем аналитических (аналитических всего лишь столько же, сколько натуральных). Прямо как "тёмная материя", только в математике. :-)

Где-то здесь близко есть парадокс, причём парадокс, затрагивающий основы теории множеств, но у меня не получается его ухватить.

Это я попытался вспомнить и воспроизвести свои размышления 25-летней давности, когда я был школьником

September 2017

S M T W T F S
     12
3456789
10111213 141516
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 22nd, 2017 02:41 am
Powered by Dreamwidth Studios