Тени разума
Роджер Пенроуз написал книгу "Тени разума: в поисках науки о сознании", в которой, ни много ни мало, формально математически доказал невычислимость человеческого мышления (т.е. теоретическую невозможность его моделирования на компьютере).
Я попробую вкратце пересказать её основные положения для тех, кто читать саму книгу не собирается (может, заодно и сам лучше пойму). Там, на самом деле, интересно.
Для начала определимся, что есть невычислимость, о чём вообще речь.
Существуют математические задачи, для которых формально доказана алгоритмическая неразрешимость. Например, существование решения системы диофантовых уравнений (это уравнения, которые нужно решить в целых числах). Или задача замощения - возможно ли замостить плоскость заданными многоугольниками (всюду плотно, без дырок и наложений). Доказано, что не существует алгоритма, позволяющего ответить на эти вопросы (хотя сами эти ответы, безусловно, есть). В общем, далеко не для всякой вполне детерминированной задачи обязан существовать алгоритм её решения, даже в теории.
Может ли физический мир быть невычислимым, недоступным для численного моделирования? До сих пор таких физических законов не находили, но ничто не мешает им быть. Нетрудно представить себе виртуальную (игрушечную) вселенную, построенную на таких законах. Например, перенумеровать диофантовы уравнения, сделать время дискретным, и постановить, что частица летит влево, если уравнение имеет решение, и вправо, если не имеет. Такая вселенная полностью детерминирована, но её моделирование на компьютере теоретически невозможно.
Это уже само по себе очень любопытное утверждение, возможно, требующее времени и дополнительной информации для осознания.
Теперь, собственно, доказательство невычислимости человеческого разума.
Можно перенумеровать все возможные алгоритмы, и входные данные представить в виде натурального числа. Это сделать не очень трудно, если вспомнить, что в математике натуральное число - это не 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) мы назовём необоснованным, т.е. дающим какие-то результаты, но не всегда верные. Судя по всему, Алан Тьюринг видел выход из этого парадокса именно в этом, он считал наличие ошибок необходимым атрибутом человеческого мышления. Если же предположить, что способность ошибаться не является фундаментальной способностью человеческого разума, то придётся признать, что человеческий разум действует не алгоритмически (т.е. некоторые его проявления невозможно промоделировать алгоритмом).
Это доказательство очень близко к доказательству Гёделя его знаменитой теоремы о неполноте, и фактически является его вариацией. Только применено оно с несколько другими начальными условиями и, соответственно, получены несколько другие выводы. Вместо существования недоказуемых (в рамках теории) утверждений получилась неалгоритмизуемость человеческого сознания.
Что я об этом думаю.
Есть известный парадокс самореференции. Если определение некоторого объекта содержит ссылку на сам этот объект или какие-то его свойства, то очень легко получить противоречие. Простой пример: "это утверждение ложно". Такое утверждение не может быть ни ложным, ни истинным, оно содержит противоречие. Более формально-математический пример привёл Рассел, когда ввёл "множество всех множеств, не содержащих себя в качестве подмножества". Само это множество должно включать себя, но это противоречит его определению. В примере Рассела самореференция в явном виде отсутствует, однако это не избавляет от парадокса. Математики вынуждены от него уйти, постановив, что не любой набор множеств можно рассматривать как множество, и ввели понятие "класс множеств". Несколько искусственное, на мой взгляд, ограничение, но что им оставалось делать?
В доказательстве Гёделя (или, точнее, в его варианте, использованном Пенроузом) появляется подобный парадокс.
В упрощённом виде его можно сформулировать так. Возьмём утверждение P: "Можно утверждать, что это утверждение ложно". Допустим, мы имеем дело с обоснованной системой, т.е. которая не может выдавать ложные суждения. Из того, что P истинно, следует (в обоснованной системе), что P ложно, следовательно, компьютер непременно заявит, что P ложно. Однако, мы, обладая этим пониманием (что P с точки зрения формального компьютера непременно должно быть ложно), обнаруживаем, что утверждение "Можно утверждать, что P ложно" и является самим утверждением P, т.е. оно на самом деле истинно!
Это ничем принципиально не отличается от обычного "это утверждение ложно", просто добавляется один шаг косвенности. Всё остальное (двойной диагональный метод, перенумерация всех возможных алгоритмов) необходимо, чтобы уйти от самореференции, а побочным эффектом является маскировка этого парадокса. А именно. Вычисление A(k,n): "Можно утверждать, что утверждение Ck(n) ложно". Возьмём вычисление Ck(n), эквивалентное вычислению A(n,n). Тогда утверждение A(k,k) как раз и будет звучать "Можно утверждать, что Ck(k) ложно", т.е. "Можно утверждать, что это утверждение ложно".
Книжка на самом деле интересная, я из неё узнал массу любопытного и полезного. Однако её ключевой момент, формальное доказательство невычислимости человеческого разума, увы, принять не могу. Несмотря на то, что собственно с тезисом согласен, т.к. считаю, например, что никакой компьютер не может обладать qualia.
Я попробую вкратце пересказать её основные положения для тех, кто читать саму книгу не собирается (может, заодно и сам лучше пойму). Там, на самом деле, интересно.
Для начала определимся, что есть невычислимость, о чём вообще речь.
Существуют математические задачи, для которых формально доказана алгоритмическая неразрешимость. Например, существование решения системы диофантовых уравнений (это уравнения, которые нужно решить в целых числах). Или задача замощения - возможно ли замостить плоскость заданными многоугольниками (всюду плотно, без дырок и наложений). Доказано, что не существует алгоритма, позволяющего ответить на эти вопросы (хотя сами эти ответы, безусловно, есть). В общем, далеко не для всякой вполне детерминированной задачи обязан существовать алгоритм её решения, даже в теории.
Может ли физический мир быть невычислимым, недоступным для численного моделирования? До сих пор таких физических законов не находили, но ничто не мешает им быть. Нетрудно представить себе виртуальную (игрушечную) вселенную, построенную на таких законах. Например, перенумеровать диофантовы уравнения, сделать время дискретным, и постановить, что частица летит влево, если уравнение имеет решение, и вправо, если не имеет. Такая вселенная полностью детерминирована, но её моделирование на компьютере теоретически невозможно.
Это уже само по себе очень любопытное утверждение, возможно, требующее времени и дополнительной информации для осознания.
Теперь, собственно, доказательство невычислимости человеческого разума.
Можно перенумеровать все возможные алгоритмы, и входные данные представить в виде натурального числа. Это сделать не очень трудно, если вспомнить, что в математике натуральное число - это не 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) мы назовём необоснованным, т.е. дающим какие-то результаты, но не всегда верные. Судя по всему, Алан Тьюринг видел выход из этого парадокса именно в этом, он считал наличие ошибок необходимым атрибутом человеческого мышления. Если же предположить, что способность ошибаться не является фундаментальной способностью человеческого разума, то придётся признать, что человеческий разум действует не алгоритмически (т.е. некоторые его проявления невозможно промоделировать алгоритмом).
Это доказательство очень близко к доказательству Гёделя его знаменитой теоремы о неполноте, и фактически является его вариацией. Только применено оно с несколько другими начальными условиями и, соответственно, получены несколько другие выводы. Вместо существования недоказуемых (в рамках теории) утверждений получилась неалгоритмизуемость человеческого сознания.
Что я об этом думаю.
Есть известный парадокс самореференции. Если определение некоторого объекта содержит ссылку на сам этот объект или какие-то его свойства, то очень легко получить противоречие. Простой пример: "это утверждение ложно". Такое утверждение не может быть ни ложным, ни истинным, оно содержит противоречие. Более формально-математический пример привёл Рассел, когда ввёл "множество всех множеств, не содержащих себя в качестве подмножества". Само это множество должно включать себя, но это противоречит его определению. В примере Рассела самореференция в явном виде отсутствует, однако это не избавляет от парадокса. Математики вынуждены от него уйти, постановив, что не любой набор множеств можно рассматривать как множество, и ввели понятие "класс множеств". Несколько искусственное, на мой взгляд, ограничение, но что им оставалось делать?
В доказательстве Гёделя (или, точнее, в его варианте, использованном Пенроузом) появляется подобный парадокс.
В упрощённом виде его можно сформулировать так. Возьмём утверждение P: "Можно утверждать, что это утверждение ложно". Допустим, мы имеем дело с обоснованной системой, т.е. которая не может выдавать ложные суждения. Из того, что P истинно, следует (в обоснованной системе), что P ложно, следовательно, компьютер непременно заявит, что P ложно. Однако, мы, обладая этим пониманием (что P с точки зрения формального компьютера непременно должно быть ложно), обнаруживаем, что утверждение "Можно утверждать, что P ложно" и является самим утверждением P, т.е. оно на самом деле истинно!
Это ничем принципиально не отличается от обычного "это утверждение ложно", просто добавляется один шаг косвенности. Всё остальное (двойной диагональный метод, перенумерация всех возможных алгоритмов) необходимо, чтобы уйти от самореференции, а побочным эффектом является маскировка этого парадокса. А именно. Вычисление A(k,n): "Можно утверждать, что утверждение Ck(n) ложно". Возьмём вычисление Ck(n), эквивалентное вычислению A(n,n). Тогда утверждение A(k,k) как раз и будет звучать "Можно утверждать, что Ck(k) ложно", т.е. "Можно утверждать, что это утверждение ложно".
Книжка на самом деле интересная, я из неё узнал массу любопытного и полезного. Однако её ключевой момент, формальное доказательство невычислимости человеческого разума, увы, принять не могу. Несмотря на то, что собственно с тезисом согласен, т.к. считаю, например, что никакой компьютер не может обладать qualia.