Компьютеры из желудей и спичек

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

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

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

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

— 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.

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

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

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

— YAML.

Сам по себе это просто формат, но в Helm в него вставляют шаблоны на языке Go (условия, циклы), и они полны по Тьюрингу. Для Ansible полноту показали на чистом языке плейбуков, без плагинов и шаблонов Jinja2. Сам конфиг безобиден, а шаблоны и язык автоматизации над ним уже можно считать программой, которая, например, способна зависнуть.

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

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

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

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

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

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

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

Телеграм: t.me/ainewsline

Источник: vk.com

Комментарии: