И она работает!
Недавно энтузиаст-конструктор, известный под псевдонимом The Bananaman 2018, представил на платформе Lego Ideas рабочую модель машины Тьюринга, собранную из деталей конструктора LEGO. Она состоит примерно из 2900 деталей. Это одна из самых сложных моделей, которые когда-либо собирались из конструктора
Историческая справка
Машина Тьюринга, изобретённая математиком Аланом Тьюрингом в 1936 году, представляет собой гипотетический механизм, который может имитировать любой компьютерный алгоритм. В основе этой концепции лежит идея бесконечно длинной ленты с символами, «головки» для чтения и записи информации, конечного набора состояний и таблицы инструкций, которые определяют, какое действие следует выполнить в следующий момент.
Что умеет машина Тьюринга из Lego?
LEGO-модель машины Тьюринга не просто декоративная, она действительно работает. Модель способна выполнять алгоритмические вычисления, что делает её не только интересной с точки зрения инженерии, но и образовательной.
Машина использует 4 возможных символа и 8 возможных состояний, что в сумме дает 32 возможные комбинации символ-состояние. Каждая инструкция состоит из 7 битов (3 для состояния, 2 для символа, 1 для движения влево/вправо и 1 для остановки), что позволяет создавать сложные программы.
Основные компоненты машины Тьюринга
1. Лента:
Лента представляет собой бесконечную последовательность ячеек, каждая из которых может содержать один из нескольких символов. В LEGO-модели лента выполнена из физического материала и имеет конечную длину, но концептуально она считается бесконечной.
2. Головка для чтения и записи:
Головка перемещается вдоль ленты, читая символы и записывая новые. В LEGO-модели головка управляется системой шестерен и рычагов, которые позволяют ей двигаться влево и вправо по ленте.
3. Состояния:
Машина Тьюринга имеет конечное множество состояний. В каждом состоянии машина выполняет определенные действия в зависимости от символа, который она читает на ленте. В LEGO-модели предусмотрено 8 состояний, что позволяет создавать 32 различные комбинации символов и состояний.
4. Таблица инструкций:
Таблица инструкций определяет, какое действие должна выполнить машина в зависимости от текущего состояния и символа на ленте. Действия включают:
- Запись нового символа на ленту
- Перемещение головки влево или вправо
- Переход в новое состояние.
Принцип работы
1. Чтение символа:
Головка считывает символ с текущей ячейки ленты. В LEGO-модели это осуществляется механически, с помощью системы шестерен и рычагов.
2. Выполнение инструкции:
На основе текущего состояния и считанного символа машина выполняет инструкцию из таблицы. Это может включать запись нового символа, перемещение головки и переход в новое состояние.
3. Запись символа:
Если инструкция требует записи нового символа, головка заменяет текущий символ на ленте новым символом.
4. Перемещение головки:
Головка перемещается на одну ячейку влево или вправо в зависимости от инструкции. В LEGO-модели это движение осуществляется с помощью механической системы.
5. Переход в новое состояние:
Машина переходит в новое состояние, определенное инструкцией. Этот процесс повторяется до тех пор, пока не будет достигнуто конечное состояние или не будет выполнена остановка.
Проект машины Тьюринга из LEGO, созданный The Bananaman 2018, является впечатляющим примером того, как можно использовать конструкторы LEGO для создания сложных и функциональных моделей. Этот проект не только демонстрирует технические возможности LEGO, но и служит образовательным инструментом, позволяя лучше понять принципы работы вычислительных машин.