Немного поцитирую вики:
Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
А теперь поцитирую создателей:
Мы построили эту машину в ознаменование года Алана Тьюринга*, чтобы показать, как просто устроен компьютер. Главная цель — сделать так, чтобы можно было воочию увидеть большинство производимых машиной операций. Для создания был использован LEGO MINDSTORMS NXT set.
* Тьюринг родился 23 июня 1912.
У оригинальной модели была бесконечная лента, но при использовании 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 Разверните видео на весь экран.
Сайт проекта.
