Гёдель, Эшер, Бах: эта бесконечная гирлянда

ТЕЗИС ЧЁРЧА-ТЮРИНГА, СТАНДАРТНАЯ ВЕРСИЯ: Предположим, что существует метод при помощи которого разумное существо может разделять числа на два класса. Предположим также, что этот метод всегда приводит к ответу за конечный отрезок времени, и что этот ответ — всегда один и тот же для одного и того же числа. В таком случае существует некая конечная программа на Флупе (то есть, некая общерекурсивная функция), которая будет давать точно такие же ответы, как и разумное существо.
Основная идея здесь состоит в том, что любой мыслительный процесс, делящий числа на две категории, может быть описан в форме программы на Флупе. Интуиция утверждает, что других методов, чем имеющиеся во Флупе, не существует, и что невозможно использовать эти методы иначе, чем путем бесчисленных повторений (которые Флуп допускает). Тезис Черча-Тюринга невозможно доказать как Теорему математики — это всего лишь гипотеза о процессах протекающих в человеческом мозгу.

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

Наше трехмерное пространство — это единственная известная нам реальность. Двумерность точно так же фантастична для нас, как и четырехмерность, поскольку в нашем мире ничто не плоско по-настоящему, даже поверхность тщательнейшим образом отполированного зеркала. И все же мы держимся за идею, что стена или лист бумаги на самом деле плоские, — и интересно то, что мы продолжаем, с незапамятных времен, производить иллюзии пространства на этих самых плоских поверхностях. Не абсурдно ли нарисовать несколько линий и назвать это «домом»?

Мы уже с самого начала столкнулись с тем, что формальные системы могут вести себя как неукротимые и опасные бестии, когда в них есть удлиняющие и укорачивающие правила, поскольку это может привести к бесконечному поиску среди строчек. Открытие Гёделевой нумерации показало, что у любого поиска строчки с определенным типографским свойством есть арифметический кузен: изоморфный поиск целого числа с соответствующим арифметическим свойством. Следовательно, чтобы найти разрешающий алгоритм для формальных систем, необходимо решить проблему непредсказуемо длинного поиска — хаоса — среди строчек.

...какие качества необходимы предмету, чтобы его можно было бы назвать патефоном? Почему бы Крабу не сказать, что его холодильник — это «совершенный» патефон? В доказательство он мог бы положить на холодильник любую пластинку и сказать: «Вот видите, он ее проигрывает!» Если бы Черепаха захотела что-то противопоставить этому дзен-буддйстскому акту, она должна была ответить: «Нет, ваш холодильник такого низкого качества, что его нельзя назвать патефоном: он вообще не может воспроизводить звуков (а тем более, саморазбивальных звуков)». Черепаха может записать пластинку под названием «Меня нельзя сыграть на патефоне X», только если патефон X действительно является патефоном! Метод Черепахи весьма хитер, так как он играет не на слабости системы, а на ее силе. Поэтому, чтобы он подействовал, необходимы патефоны достаточно высокого качества.

Черепаха: Вы, безусловно, замечали, как некоторые писатели стараются наращивать напряжение поближе к концу своих историй — но читатель, держа книгу в руках, ЗНАЕТ, что рассказ подходит к концу. Таким образом, у него есть дополнительная информация, которая действует как предупреждение. Напряжение и неизвестность немного подпорчены физической сущностью книги. Было бы гораздо лучше, если бы в конце романов писатели оставляли прокладку потолще.
Ахилл: Прокладку?
Черепаха: Именно; я имею в виду кучу печатных страниц, не имеющих никакого отношения к истории, но маскирующих ее скорое окончание.
Ахилл: А-а, понятно. Таким образом конец истории может отстоять на, скажем, пятьдесят или даже сто страниц от последней страницы книги?
Черепаха: Да. Это привнесло бы некоторый элемент сюрприза, поскольку читатель не будет знать заранее, сколько страниц относятся к прокладке и сколько — собственно к истории.

Черепаха: Пример первого — нехаотичного — вида поиска мы находим в проверке на свойство Гольдбаха. Надо просто перебирать простые числа, меньшие 2N, и если какая-нибудь пара таких чисел при сложении дает 2N, то следовательно 2N обладает свойством Гольдбаха; в противном случае, оно им не обладает. Подобная проверка не только наверняка закончится — вы даже можете предсказать, КОГДА она закончится.
Ахилл: Значит, это ПРЕДСКАЗУЕМО КОНЧАЮЩАЯСЯ проверка. Теперь вы, наверное, скажете мне, что некоторые теоретико-числовые свойства нуждаются в другого рода проверке, которая когда-либо кончится, но неизвестно, когда?
Черепаха: Вы как в воду глядите, Ахилл. И существование подобного типа проверки доказывает, что системе натуральных чисел в некотором роде присущ хаос.