Понять - значит упростить

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

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

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

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

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

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

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

( Что я об этом думаю )

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

А давайте посмотрим на это с другой, неожиданной стороны.
( Read more... )

Всем известно мнемоническое правило для запоминания цветов радуги по первым буквам:
Каждый Охотник Желает Знать, Где Сидит Фазан.

Есть менее известные, но не менее красивые правила:

Как Однажды Жак Звонарь Головой Свалил Фонарь.
Каждая Образованная Женщина Завтракает Горячими Сырыми Фрикадельками
Кварк Окружает Жаркий Занавес Глюонов, Создающих Флюиды

Украинские:

Чому Олені Живуть Зимою Без Своїх Фантазій?
Чекання Постріла в Жопу Змушує Бути Сильним Фізично.

Число "пи" (по количеству букв в словах):

Это я знаю и помню прекрасно: пи многие знаки мне лишни, напрасны.

Раз у Коли и Арины
Распороли мы перины.
Белый пух летал, кружился,
Куражился, замирал,
Ублажился,
Нам же дал
Головную боль старух.
Ух, опасен пуха дух!

Число "е":

Мы порхали и блистали,
но застряли в перевале:
не признали наши крали
авторалли

Корень из двух:

Я Катя, я дура, но я вот нашла корень из два

Планеты солнечной системы, по первым буквам (все, кроме одной, включают Плутон, который уже не настоящая планета):

Можно Вылететь За Марс, Ювелирно Свернув У Нашей Планеты
Мы Все Знаем: Мама Юли Села Утром На Пилюли
Между Волками Зайчишка Метался, Юркнул, Споткнулся, Упал - Не Поднялся
Медвежонок Ветчину Закусил Малиной, Юркий Суслик Утащил Ножик Перочинный
Мрачное Венерическое Заболевание Может Юрко Сразить Усталую Нимфоманку
Старый Морской Волк Замучил Молодого Юнгу, Совершенно Утомив Несчастного Подростка

Если по клавишам фортепиано отсчтитывать месяцы, начиная от ноты фа - белые клавиши будут приходиться на месяцы, в которых 31 день.
(По костяшкам общеизвестно).

Геологические периоды:
Каждый отдельный студент должен купить поллитра. Ты, Юрик, мал - подожди немного, а?
(Кембрий, ордовик, силур, девон, карбон, пермь, триас, юра, мел, палеоген, неоген, антропоген).

Группа "Освобождение труда" (первая марксистская организация): Плеханов, Игнатов, Засулич, Дейч, Аксельрод (для запоминания важен именно этот порядок; так он указан и в Википедии).

Оказывается, примерно до 60-х годов XX века люди в основном видели чёрно-белые сны, а потом - цветные. Сейчас чёрно-белые сны встречаются очень редко, раньше так же редко встречались цветные.

В шутку предположу, что те, кто показывает нам сны, проапдейтили оборудование. :)

Давно известно, что обработка информации - это потеря информации. Компьютер, вычисляющий "2+2", на входе имеет больше информации, чем на выходе (на входе два числа, на выходе одно). Программа обычно имеет много входных данных, которые перерабабывает и выдаёт результат (например, "42").

А вот недавно обнаружил Принцип Ландауэра:

В любой вычислительной системе, независимо от ее физической реализации, при потере 1 бита информации выделяется теплота в количестве по крайней мере W Джоулей:
W = k T ln 2
k - константа Больцмана, T - абсолютная температура вычислительной системы.

Одним из способов обойти ограничения, накладываемые этим принципом, является использование обратимых вычислений.

Обратите внимание, засада в том, что минимальное выделяемое кол-во теплоты пропорционально температуре. Если охладить - можно меньше выделять тепла, но его труднее отводить. Если нагреть - отводить проще, но и выделяться будет больше.

Но вообще, наличие столь простой формулы для связи битов с джоулями для меня неожиданно. Как и концепция обратимых вычислений.

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


Via

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

Неожиданно.
Хотя, конечно, можно ставить под сомнение.

Недавно я высказывал сомнения, что случайные мутации и естественный отбор могут привести к наблюдаемым результатам за данное время.

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

А во-вторых, bormal сказал мне совершенно очевидное соображение, и теперь меня искренне удивляет, как я его не учёл. При половом размножении отбор происходит не путём выживания более приспособленных, а путём выбора самкой того самца, который ей по каким-то причинам больше нравится (ну и, возможно, иногда самец тоже может предпочитать одну самку другой). У высших организмов такая оценка носит сложный и комплексный характер, в результате чего эволюция идёт практически со скоростью искусственного отбора.

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

Из обсуждения интересных экспериментов Рамачандрана открыл для себя понятия "квалии" и "философский зомби". Интересно. Даже странно, что раньше не сталкивался.

Нейробиолог Рамачандран считает, что животные не чувствуют боль так, как человек, что у них это только поведенческие реакции, по его мнению у животных нет квалий. Не могу с этим согласиться. Хотя вопрос действительно неочевиден и выходит за рамки естественных наук (его даже можно признать бессмысленным), он даёт пищу для размышлений и о людях (одинаково ли внутренне ощущают боль ребёнок и солдат? можно ли этим управлять?), и о животных (этично ли есть мясо? правильно ли "очеловечивать" собаку?), и о душé...

Не люблю видеоролики вместо текста, не люблю форму лекций (американских), однако вот это мне понравилось, есть интересные моменты.


Если не грузится, вот оно же на ютубе:
Первая часть
Вторая часть