Верёвка есть вервие простое, а компьютер — это «такая вот штука». Обязательно ли нужен процессор, чтобы некая штука называлась компьютером? А всё, что с процессором — это компьютер? И где, вообще, граница?

Великий Алан Тьюринг в 1936 году описал воображаемую машину, чтобы определить, какие задачи можно решить, выполняя простые инструкции шаг за шагом. Это описание потом назвали «машиной Тьюринга»: это умозрительная модель того, что можно назвать компьютером.

В машине Тьюринга есть бесконечная лента с ячейками, в ячейках — символы из предустановленного набора (может — алфавит, а может — только единицы и нули, это зависит от реализации). Есть «считывающая головка», которая шагами движется по ленте: один шаг — одна ячейка. У машины есть текущее состояние, которое может меняться в зависимости от считанных данных. Головка считывает содержимое ячейки, по заданному правилу записывает в неё символ и сдвигается влево или вправо. Пример правила: «Если машина в состоянии А видит в ячейке 0 — надо записать в ячейку 1, шагнуть вправо и перейти в состояние Б».

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

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

Второе понятие — «полнота по Тьюрингу». Система полна по Тьюрингу, если умеет всё то, что умеет машина Тьюринга и, следовательно, может выполнить любую программу.

И тут начинается приключение: систему, полную по Тьюрингу, можно построить почти из чего попало — из игры-симуляции, из карточной игры или из армии.

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

Magic: The Gathering, коллекционная карточная игра.

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

Dwarf Fortress, игра-симулятор крепости гномов: там есть механизмы и вода.

Из шестерёнок, насосов и воды игроки собирают логические вентили. В 2010 году один игрок построил программируемый 8-битный компьютер, где единица в памяти означает воду на датчике давления. Памяти в нём 32 байта. Автор рассчитывал, что восьми команд хватит для любого вычисления. Компьютер работает даже на воде и шестерёнках, хотя с 32 байтами памяти это скорее демонстрация, чем рабочий инструмент.

Factorio, игра про постройку автоматизированных заводов.

Игровые блоки-«комбинаторы» обрабатывают числовые сигналы, а игроки из таких блоков собирают процессоры. На форуме игроков показали мини-компьютер 7×11 клеток, который считает числа Фибоначчи. Полноту по Тьюрингу заявил сам автор; программа у него короткая (9 строк), память можно расширять.

Cities: Skylines, игра-градостроитель.

Электростанция, затопленная канализацией, перестаёт работать, и это готовый логический вентиль NOT (он меняет «есть сигнал» на «нет сигнала» и наоборот). Из подобных вентилей игроки собрали 4-битный сумматор. Одно сложение занимает 15 игровых месяцев, и вся схема буквально работает на фекалиях. Автор назвал игру полной по Тьюрингу, но целый компьютер строить не стал.

Excel, табличный редактор Microsoft.

С функцией LAMBDA формулы могут вызывать сами себя. Microsoft Research прямо написала, что язык формул теперь полон по Тьюрингу: в принципе в нём можно записать любое вычисление. Здесь полноту заложили сами создатели: так и было задумано. Формулы в таблице теперь можно считать полноценным языком программирования.

HTML + CSS, язык разметки и оформления веб-страниц.

Чекбоксы хранят состояние, селекторы дают условия. На этой базе без применения JavaScript собрали клеточный автомат Rule 110 (ряд клеток, которые меняются по простому правилу), который доказанно полон по Тьюрингу. Каждый шаг приходится запускать вручную, нажимая клавиши, поэтому о полноте самого CSS до сих пор спорят. HTML-страница хранит состояние и считает правила как машина Тьюринга, но команду «сделай следующий шаг» даёт человек, и это серьёзный недостаток.

Инструкция mov в процессорах x86.

В 2013 году Стивен Долан показал, что для запуска любой программы хватает одной команды, «скопируй значение» (mov), если разрешить процессору возвращаться к началу программы. Компилятор movfuscator превращает код на C в сплошные mov и обходится даже без перехода: программа зацикливается через mov, который вызывает сбой. Сложный набор команд процессора для полноты по Тьюрингу даже избыточен: хватает копирования и повторения.

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

Полноту нашли в шаблонах C++, параметризованных типах Java и системе типов TypeScript, где программу можно записать самими типами. Компилятор выполняет программу прямо во время проверки типов. В таких языках проверка типов в общем случае может не закончиться, и для Java это в 2016 году доказал Раду Григоре.

YAML.

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

Конфиг curl, консольная утилита для передачи данных по сети.

В curl полноту по Тьюрингу получили случайно: хватило вырезания кусков из значений переменных и подключения конфигов друг в друга без ограничения глубины. Это работало в версиях 8.12–8.16, но с 8.17 вложенность ограничили пятью уровнями — и полноты не стало.

DNS, система, превращающая адреса сайтов в IP-адреса серверов.

В DNS — «почти-полнота» по Тьюрингу: через записи DNAME показали простые вычисления. Авторы исследования считают, что DNS умеет меньше, чем машина Тьюринга, но для «телефонной книги интернета» и это весьма много.

«Задача трёх тел», роман Лю Цысиня.

Учёный Джон фон Нейман предлагает императору Цинь Шихуанди собрать компьютер из армии в 30 миллионов солдат. Каждый поднимает чёрный или белый флаг (0 или 1), а группы солдат работают как логические вентили. В этом компьютере есть и несложный графический интерфейс (прогресс-бар и индикаторы).

Стоит одному солдату уснуть — и армия выдаст неверный ответ. Система должна работать даже в пятницу вечером, когда все в увольнении. Для подготовки стратегов, способных строить устойчивые системы, мы в Хекслете создали курс «Системный дизайн». Пять месяцев обучения на практических примерах и реальных проектах, от одного сервера до распределённой платформы, которая переживёт отказ отдельных её частей. Солдат спит — система работает.

Хабракомментарии.

В 2011 году Павел Гуров в посте «Используем хабракомментарии как машину Тьюринга» собрал машину из вложенных комментариев: комментарий в избранном означал единицу, а правила уместились в таблицу из девяти строк. На ней он сложил 2 и 3 и получил 5. Полноту автор не заявлял: машина выполняет одну программу, а каждый шаг делает читатель с мышкой. Но возможно, в один прекрасный день и Хабр станет полным по Тьюрингу.

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