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

Когда в 2010 году вышел Inception, аудиторию увлекла идея о том, что целые миры вложены в последовательно более глубокие слои пейзажа снов. Начало, казалось, задело за живое, играя на тропе, который, кажется, мгновенно создает ощущение таинственности и удивления - рекурсии и самореференции. В этом образе нет ничего нового. Циклическая икона змеи, поедающей собственный хвост, существовала в Древнем Египте и вошла в греческую традицию как Уроборос. Русские плотники создавали наборы матрешек более века, причем некоторые наборы содержат десятки кукол, встроенных друг в друга каскадом самоподобия.

«Все, что мы видим или кажемся, - всего лишь сон во сне». -Эдгар Аллан По

Еще до того, как я смог определить это, я помню, как был восхищен и очарован рекурсией. Обычная поездка в продуктовый магазин означала, что вы уставились на пакет масла Land-O-Lakes, на котором женщина-коренная американка держала пакет масла Land-O-Lakes, на котором держалась женщина-коренная американка. … Это продолжалось вечно! Я помню, как смотрел на эту упаковку с детским удивлением, привлеченный тайной этого самореферентного изображения.

Стоя там в холодных окрестностях молочной секции супермаркета, я понял, что мы можем определить последовательности, которые входят в бесконечную регрессию. Такое же ощущение покалывания поразило меня в 14 лет, когда я подключил видеокамеру к телевизору, а затем направил камеру на экран. Телевизор отображал то, что видела камера, но камера видела то, что отображал телевизор, что приводило к бесконечному каскаду экранов внутри экранов, исчезающих глубоко в каком-то виртуальном мире внутри экрана телевизора. С обоими этими явлениями я знал, что то, что я вижу, было в некотором смысле иллюзией - если вы увеличите масштаб упаковки масла Land-O-Lakes с помощью микроскопа, вы на самом деле не найдете бесконечно много копий самого себя, в то время как На самом деле экран телевизора не может регрессировать до бесконечности, потому что вы в конечном итоге максимально увеличите разрешение телевизора. И все же я не мог избавиться от ощущения, что эти физические ограничения были чем-то менее реальными, чем идея о том, что теоретически эти последовательности продолжаются вечно. Возможно, это было моим первым намеком на то, что абстрактная концепция может быть в некотором смысле более верной, чем холодная реальность пикселей и частиц.

Мое увлечение рекурсией осталось, поскольку я продолжал изучать языки, математику и информатику. Рекурсия - это больше, чем рекламный трюк или забавный трюк; на самом деле это происходит каждый день в различных академических, художественных, биологических и технологических контекстах. Чем больше я узнаю, тем больше вижу рекурсию вокруг себя. Теперь я понимаю, что это не совпадение, поскольку рекурсия, возможно, является единственной концепцией, которая наиболее полно объясняет, какими существами мы являемся как люди.

Язык

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

Я знаю, ты думаешь, что я вёл себя странно.

Обратите внимание, что приведенное выше предложение на самом деле состоит из предложения, встроенного в предложение, встроенное в предложение. Я вёл себя странно. Вы думаете, что я вёл себя странно. Я знаю, ты думаешь, что я вёл себя странно. Это грамматическое правило, написанное символически, может быть выражено как:

S →NP V S

Здесь S означает «предложение», NP означает «фраза существительного», V означает «глагол» (в данном контексте это, в частности, определенный класс глаголов познания, таких как знать / думать / полагать ). Правило или «уравнение» выше имеет символ S как слева, так и справа. Это означает, что мы можем взять правую часть уравнения и заменить ее на букву S.

S →NP V NP V S.

Мы можем легко продолжать, встраивая предложения в предложения до бесконечности. Это означает, что не существует верхней границы длины или сложности человеческих высказываний. Даже с ограниченным словарным запасом человеческий язык может выражать произвольное количество мыслей. Это качество человеческого языка означало, что вокализации Homo sapiens больше не ограничивались конкретными устоявшимися значениями, такими как «Опасно!» или «Еда такая». Человеческий язык дал нам возможность выражать все, что мы хотели, и делиться своими идеями с другими людьми.

Каждый день люди обычно генерируют предложения, которые никогда раньше не произносились за всю историю человечества. Что еще более удивительно, эти предложения легко понимаются другими. Вы можете проснуться с мыслью, беспрецедентной в истории нашего вида, и к вечеру спорить и проповедовать свою идею в умах ваших друзей. Люди использовали эту способность во благо и во зло: чтобы учить детей миру, разрабатывать системы рабства и геноцида, планировать миссии на Луну, подталкивать других к самоубийству, формулировать вопросы о происхождении Вселенной. , чтобы обманывать и манипулировать ради личной выгоды. Все, чего мы достигли как вид, основывается на языке.

Математика

Моя мама рассказывает мне, что, когда мне было два года, я села на задницу с подгузником и заметила: «Мама, числа никогда не заканчиваются». Сидя там и считая все числа, которые я знал, я пришел к выводу, что ничто не стояло между мной и простым вечным счетом! Осознание того, что вы всегда можете добавить единицу к числу и, таким образом, продолжать расширять последовательность чисел до бесконечности, на самом деле является рекурсивной концепцией, как это дано в следующем рекурсивном определении (только целые числа).

f(0) = 0

f (x) = f (x-1) +1 для x ›0

Рекурсивные формулы, подобные этой, могут быть даны последовательностям, подобным числам Фибоначчи, в которых каждый член последовательности определяется как сумма двух предыдущих членов. Вооружившись только этим рекурсивным определением и начальными условиями или базовым случаем, вы можете вычислять числа Фибоначчи с настоящего момента до конца времен. Рекурсия также позволяет доказывать бесконечные последовательности чисел, используя принцип математической индукции. Именно с помощью рекурсии мы действительно можем охватить бесконечность нашим ограниченным разумом. Бесконечность - это не просто большое число. Он качественно другой. Собака может сказать вам разницу между одним лакомством и множеством лакомств. Насколько нам известно, только люди могут понять, что бесконечность простирается за пределы того, что мы можем видеть или визуализировать. Хотя я никогда не умел считать до бесконечности, я знаю, что в каком-то смысле она существует.

Цифровая революция

Самым значительным изобретением ХХ века было не атомная бомба, самолет или ракета. Все эти инструменты (и все предыдущие изобретения человека - от колеса до печатного станка и автомобиля) были разработаны для выполнения одной конкретной задачи и были сконструированы таким образом, чтобы их форма соответствовала их предполагаемым функциям. Гениальные изобретатели придумали и построили невероятно сложные устройства для невероятно специфических задач: хронометраж, ткачество, разделка рыбы, аэрация газонов, штамповка алюминиевых банок. Какими бы точными и полезными ни были эти машины, они были негибкими. Вне определенного набора условий они бесполезны. Может ли кто-нибудь построить машину, которая уничтожит все машины? Что-то, что могло бы адаптироваться к любому количеству новых сценариев без необходимости переделывать?

В середине 20 века британский математик и ученый-компьютерщик Алан Тьюринг разработал теорию вычислений, используя обманчиво простую модель, теперь известную как машина Тьюринга. Каждая машина Тьюринга состоит из подвижной головки, которая может читать и записывать двоичные данные (нули и единицы) на бесконечном рулоне ленты. Машина Тьюринга кодирует набор состояний (и переходов между состояниями), которые определяют, как она должна себя вести. В зависимости от того, как эти состояния установлены в машине, машина Тьюринга может автоматически решать различные вычислительные задачи, которые могут быть выражены как ввод в двоичном формате на рулоне ленты. Одна машина Тьюринга могла бы вычислить, был ли данный вход палиндромом; другая машина Тьюринга может напечатать разницу двух входных чисел. На изображении ниже показан пример того, как это визуализировать, но имейте в виду, что машина Тьюринга была теоретической моделью, используемой для разработки доказательств теории вычислений, а не физической машиной.

Хотя это звучит изящно, само по себе это не квалифицирует изобретение Тьюринга как величайшее изобретение 20-го века. Скорее, огромным нововведением Тьюринга было осознание того, что он может построить машину Тьюринга, функция которой заключалась в моделировании машины Тьюринга. Он прочитал бы описание любой другой машины Тьюринга в качестве входных данных, а затем вел бы себя как эта машина Тьюринга. Эта идея - передать описание машины Тьюринга в качестве двоичного входа в другую машину Тьюринга - работает рекурсией. Так родилась Универсальная машина Тьюринга, машина, которая положит конец всем машинам. Прошли те времена, когда для каждой задачи создавалась новая машина. Никогда не прикасаясь к внутренностям этого универсального компьютера, вы можете заставить его решать проблемы по вашему выбору, передавая ему как данные, так и инструкции.

Теоретически может существовать бесконечная рекурсия: универсальная машина Тьюринга может моделировать другую универсальную машину Тьюринга, которая может моделировать другую универсальную машину Тьюринга, и так далее. На практике это развитие означало рождение программирования в том виде, в каком мы его знаем: мы создаем ЦП общего назначения (центральные процессоры), а затем вводим программы, которые сообщают ЦП, как себя вести. Благодаря этому изобретению в наших рюкзаках и карманах теперь есть универсальные компьютеры, на которых можно запускать произвольные программы и приложения для решения огромного количества задач. Если вы хотите, чтобы ваш iPhone делал что-то, чего он в настоящее время не делает, вам не нужно переделывать iPhone, вы просто создаете новое приложение, не выходя из дома. Хотя мы радикально улучшили память, скорость и вычислительную мощность, современные компьютеры принципиально не отличаются от того, что задумал Тьюринг.

Рекурсия настолько фундаментальна в информатике, что я убедился, что первые студенты-информатики, которых я когда-либо учил, были подвержены рекурсивному мышлению - как только они освоили написание простых функций на языке блочного кодирования с перетаскиванием, я попросил их предсказать поведение функции выглядит следующим образом:

Функция greet состоит из двух шагов: печать «Hello» и выполнение функции greet. Если это кажется круглым, то это так. Пока мои ученики изучали код, их нахмуренные брови и нерешительные разговоры для некоторых уступили место взглядам осознания. Некоторые студенты выяснили, что это приведет к тому, что программа войдет в бесконечный цикл печати слова «Привет», замедлится и в конечном итоге приведет к сбою их браузеров. Тем не менее, рекурсивный код не содержит ошибок. Предоставляя условия выхода в рекурсивной функции, программисты могут заставить рекурсию выполнять полезную работу, которая фактически завершается через конечный период времени. Часто рекурсия предоставляет элегантный способ решить проблему с помощью удивительно небольшого количества строк кода. Рекурсивные структуры данных, такие как двоичные деревья, позволяют очень эффективно хранить и извлекать данные по сравнению с нерекурсивными структурами, такими как массивы или списки.

Искусство и красота

В 1300-х годах художник Джотто написал триптих Стефанески, трехпанельный алтарь, оплаченный могущественным кардиналом. В странном повороте кардинал показан в углу картины, держа картину. Таким образом, триптих встроен в себя. Мне нравится представлять себе средневековых детей, их внимание, возможно, отстающих во время долгой церковной службы, которые смотрят на алтарь и испытывают те же чувства, что и я в детстве в молочном отделе супермаркета, глядя на масло Land-O-Lakes. упаковка.

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

Природа тоже полна рекурсивной красоты. Брокколи Романеско, овощ слишком математически совершенен, чтобы казаться реальным, состоит из спирали уменьшенных копий самого себя. Раковины наутилуса также самоподобны, что, по-видимому, позволяет моллюску внутри использовать одни и те же правила роста во всех масштабах. С одной стороны, нет ничего удивительного в том, что рекурсия встречается в природе, поскольку она позволяет простым правилам создавать сложности. И все же удивительно, что такая математическая красота так явно существует в природе, в то время как только люди могут в полной мере оценить ее.

Человеческая природа

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

Вся жизнь на Земле по существу рекурсивна: ДНК считается молекулой жизни, потому что она обладает уникальным свойством содержать инструкции для создания копий самой себя. Быть организмом - значит содержать будущие итерации вашего вида внутри вашего собственного генетического кода. В то время как вся органическая жизнь участвует в этой цепочке референции, люди идут еще дальше и добавляют когнитивный слой самореферентности. Глядя в зеркало, можно созерцать себя. Глядя на МРТ, ваш мозг может исследовать сам себя. Наше существование характеризуется осознанием самих себя, условиями жизни и движения в мире, при этом имея способность размышлять о своем собственном выборе и спрашивать, почему мы делаем то, что делаем. Мы с самого раннего возраста понимаем, что человеческие жизни сами по себе рекурсивны: у меня есть родители, у каждого из которых были свои родители, у каждого из которых были свои родители, и так далее. Рекурсивное мышление позволяет мне проникать в жизни и умы людей, которые жили за тысячелетия до меня, а также мечтать о жизнях людей, которые будут жить через тысячелетия после меня. Есть причина, по которой рекурсия не только сбивает нас с толку, но и радует нас, внушает путаницу, но при этом хорошо нас устраивает. Без этого мы не были бы такими, какие мы есть.