Машина Тьюринга из Lego

Немного поцитирую вики ^[1]:

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

А теперь поцитирую создателей:

Мы построили эту машину в честь Алана Тьюринга, чтобы показать, как просто устроен компьютер. Главная цель — сделать так, чтобы можно было воочию увидеть большинство производимых машиной операций. Для создания был использован LEGO MINDSTORMS NXT set.

У оригинальной модели была бесконечная лента, но при использовании LEGO это было довольно проблематично реализовать, поэтому на данном устройстве 32 позиции.

Основной текст программы:

W(0|1) = write either 0 or 1 on the tape
M(F|B) = move the tape either forward or backward
J(_|0|1)[0-9]+ = read & jump (always, when 0, or when 1) to a row in the instruction table

PS Разверните видео на весь экран.

Сайт проекта ^[2].

Автор: Sterhel