Снятся ли трехмерному андроиду четырехмерные овцы?

Введение

Данный материал служит логическим продолжением этой статьи. В ней утверждается, что вычислительная машина представляет собой математическую структуру, над созданием которой трудились величайшие умы своего времени.

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

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

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

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

Ядро машины

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

В качестве символов могут выступать любые знаки: буквы, цифры, графические метки или иероглифы. Стандартная модель Тьюринга требует лишь предварительного определения конечного набора символов — алфавита, в который обязательно входит знак пустой ячейки. Ноли и единицы здесь не имеют никакого приоритета.

Устройство обладает внутренним состоянием и таблицей переходов. Каждое правило предписывает конкретное действие на основе двух параметров: текущего состояния и прочитанного символа. Например: «Находясь в состоянии A и обнаружив кружок, замени его палочкой, сместись вправо и перейди в состояние B». Из подобных элементарных шагов и складываются любые вычисления.

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

Формула и кремний

Давайте мысленно модернизируем эту конструкцию.

Заменим бесконечную ленту адресуемой памятью. Пронумеруем ячейки, чтобы можно было обращаться к ним напрямую по номеру (адресу), минуя промежуточные позиции. Введем несколько временных ячеек — регистров — и арифметико-логическое устройство, избавившись от необходимости совершать долгие перемещения головки ради каждого сложения.

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

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

Введем в систему счетчик команд — специальный регистр, фиксирующий адрес следующей инструкции. Теперь процессор циклически повторяет одну и ту же последовательность:

Считать команду → Декодировать → Исполнить → Вычислить адрес следующего шага.

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

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

0: Загрузить в регистр A значение из ячейки 100
1: Прибавить к A значение из ячейки 101
2: Записать A в ячейку 102
3: Остановиться

Инструкции занимают ячейки с 0 по 3, исходные числа находятся в 100 и 101, а результат отправляется в 102. Хранение программ и данных в общей памяти представляет собой фундаментальный принцип архитектуры фон Неймана. Дополнив эту схему модулями ввода-вывода, мы получим привычную архитектуру современного компьютера.

Ноль, один

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

В электронных схемах удобнее всего задействовать два диапазона напряжений — условные «низкий» и «высокий» уровни, обозначаемые как 0 и 1. Их значительно проще и надежнее различать с запасом на неизбежные помехи, чем множество промежуточных градаций. Комбинации таких двоичных сигналов позволяют кодировать любые данные: числа, текстовые символы и процессорные инструкции.

Строго говоря, компьютер вовсе не обязан быть двоичным — существуют иные способы представления информации. Бинарный подход обусловлен исключительно инженерным удобством, а не жестким математическим требованием. Более того, сами по себе 0 и 1 не тождественны числам: их истинный смысл определяется исключительно выбранным способом кодирования и алгоритмом обработки.

Увеличиваем размерности

В классической машине Тьюринга память организована в виде одномерной ленты: у каждой ячейки есть ровно два соседа, а головка перемещается либо влево, либо вправо. Но что мешает изменить пространственную топологию ячеек? Измерения здесь определяют саму структуру носителя информации.

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

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

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

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

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

Клетчатый лист

Заменим линейную ленту бесконечным клетчатым полем. Теперь положение головки определяется парой целых координат — (x, y). Вместо двух направлений движения появляются четыре: влево, вправо, вверх и вниз. Перемещение по диагонали за один такт запрещено. Так перед нами предстает двумерная машина Тьюринга.

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

До:             После:

· · · ·         А Б В ·
А Б В ·         А Б В ·

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

Решетка из кубов

Теперь трансформируем клетчатое поле в бесконечную трехмерную решетку, которую интуитивно можно представить как пространство, заполненное кубическими ячейками. Каждая позиция обладает тремя координатами — (x, y, z). К четырем прежним направлениям добавляется пара новых: вдоль третьей оси в обе стороны.

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

(3, 2, 0) → (3, 2, 1)

Продолжим наш алгоритм копирования. Сперва машина превращает исходную строку АБВ в два идентичных ряда, как в предыдущем примере. Затем переносит получившуюся матрицу на соседний слой вдоль оси z. В итоге формируется трехмерный блок размером 3 × 2 × 2: два слоя, в каждом из которых содержится по две строки АБВ.

Решетка из тессерактов

Следующий концептуальный шаг математически тривиален: введем четвертую координату w. Адрес ячейки принимает вид (x, y, z, w), а число возможных направлений движения вырастает до восьми. Эту иерархию можно продолжать для любого заданного числа измерений: ячейки определяются наборами целых чисел, а хранят символы из конечного алфавита.

Представить четырехмерную решетку наглядно невозможно, но для вычислений это и не требуется. Ее можно мысленно трактовать как последовательность трехмерных пространств, пронумерованных параметром w. Переход

(3, 2, 1, 0) → (3, 2, 1, 1)

перенаправляет головку в ячейку с теми же пространственными координатами x, y, z, но расположенную в параллельном срезе вдоль четвертой оси.

Теперь программа может дублировать блок 3 × 2 × 2 из слоя w = 0 в слой w = 1. В результате образуется четырехмерная структура 3 × 2 × 2 × 2, объединяющая восемь копий первоначальной строки.

Про моделирование

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

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

Допустим, в двумерном пространстве заданы три символа: А в позиции (0,0), Б в (1,0) и В в (1,1). Вместо графической матрицы запишем эти данные на обычной линейной ленте следующим образом:

#0,0:А #1,0:Б #1,1:В#

Каждая конструкция здесь расшифровывается как «координаты ячейки — ее содержимое», а символ # служит разделителем. Например, запись 1,0:Б означает, что в ячейке с координатами (1,0) хранится литера Б.

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

А как быть со всей остальной бесконечной плоскостью? Договоримся о простом правиле: если координаты отсутствуют в общем списке, значит, соответствующая ячейка пуста.

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

q0;1,0;# 0,0:А# 1,0:Б# 1,1:В#

Эта запись означает: «Машина находится в состоянии q0, головка позиционирована в точке (1,0), далее следует карта памяти».

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

Находясь в состоянии q0 и встретив Б, записать Г, сдвинуться вверх и переключиться в состояние q1.

Таблицу подобных переходов можно жестко зашить в код симулятора. Альтернативный вариант — вынести ее на ту же ленту и заставить симулятор считывать правила как динамические данные; именно на этом принципе строится концепция универсальной машины Тьюринга.

Теперь одномерный эмулятор выполняет следующие шаги:

• Отыскивает нужную запись. Последовательно сканирует реестр, сопоставляя координаты с текущим положением головки (1,0), и находит фрагмент 1,0:Б.

• Применяет правило трансформации, заменяя литеру Б на Г.

• Обновляет служебную информацию о состоянии и координатах. Согласно принятым условиям, движение вверх увеличивает вторую координату: точка (1,0) трансформируется в (1,1), а состояние q0 сменяется на q1.

После завершения этого такта лента принимает следующий вид:

q1;1,1;# 0,0:А# 1,0:Г# 1,1:В#

Двумерная головка виртуально совершила шаг вверх, хотя физическая головка симулятора все это время перемещалась исключительно влево и вправо. На следующем такте она приступит к поиску записи 1,1:В.

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

Заключение

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

Так или иначе, отдыхая, этот древний мыслитель обратил внимание на деревянную дощечку, служившую ему до того обеденным столом. Он мысленно представил несколько ее копий, а затем объединил их так, чтобы получилась объемная шкатулка. Полученный результат показался ему весьма занятным.

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

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

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

Спустя века изысканий в этой области британский математик Алан Тьюринг предпринял попытку формализовать само понятие алгоритма для разрешения фундаментальной математической проблемы своего времени, звучавшей следующим образом:

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

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

Эту уникальную математическую конструкцию нарекли машиной Тьюринга, и заложенные в ней принципы лежат в основе абсолютно всех современных компьютеров.

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

И суждено ли нам стать тем самым поколением, которое узрит это триумфальное преображение воочию.

 

Источник