Введение

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

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

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

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

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

Ядро машины

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

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

У машины есть внутреннее состояние и таблица правил. Каждое правило определяет действие по двум условиям: текущему состоянию и прочитанному символу. Например: «В состоянии 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, содержащий восемь экземпляров исходной строки.

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

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

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

Предположим, в двумерной памяти записаны три символа: А в клетке (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:В.

Чтобы сравнить два адреса, можно поочерёдно сопоставлять их символы, перемещаясь между записями и помечая уже проверенные знаки. Чтобы увеличить координату, нужно изменить записанное число, при необходимости выполнив перенос разряда. Сравнение, копирование и прибавление единицы реализуются обычными правилами чтения, записи и движения по ленте.

Заключение

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

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

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

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

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

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

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

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

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

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

И мы, вероятно, то поколение, которое это увидит воочию.