Машина Тьюринга
Математическая игрушка с бесконечной бумажной лентой и считывающей головкой, придуманная в 1936 году, чтобы доказать, чего компьютеры не могут.
Модель состоит из четырёх частей: ленты, разбитой на ячейки; головки, которая читает и пишет по одному символу; конечного набора состояний; и таблицы, говорящей, что делать при данном состоянии и символе под головкой. Вот и весь аппарат. Ни арифметики, ни регистров, ни адресации — и всё же она вычисляет всё, что вычисляет любая другая модель вычислений.
Строить её никто не собирался. Алану Тьюрингу нужно было определение «механической процедуры», достаточно бедное, чтобы строго рассуждать о том, чего не может ни одна процедура. Ответ на Entscheidungsproblem Гильберта оказался отрицательным: существуют вопросы, которые не решает никакой алгоритм, например, останавливается ли произвольная программа. В тот же год к тому же выводу пришёл Алонзо Чёрч через лямбда-исчисление; эквивалентность двух моделей и составляет содержание тезиса Чёрча — Тьюринга.
Универсальная машина Тьюринга принимает на ленте описание другой машины и имитирует её. Это идея хранимой программы, высказанная за десять лет до появления железа, способного её воплотить. Назвать язык тьюринг-полным — значит сказать, что он умеет имитировать такую машину; в этот клуб входит и CSS с парой расширений, и, вероятно, что-нибудь, чего вы не планировали.