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

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

[Для просмотра данной ссылки нужно зарегистрироваться]

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

МАШИНА ТЬЮРИНГА - очень простое вычислительное устройство. Она имеет ленту бесконечной длины, разделенную на ячейки. Каждая ячейка может быть пустой или содержать символ, выбираемый из некоторого конечного списка. Также машина Тьюринга имеет головку, которая перемещается вдоль ленты и может читать или записывать символы. Машина имеет внутренне состояние, которое может быть либо состоянием останова либо выражается целым числом между 0 и некоторой максимальной величиной. Когда машина переходит в состояние останова, она заканчивает вычисления. Хотя машина Тьюринга очень проста, однако любое вычисление, которое можно сдалать на современном компьютере, может быть выполнено на машине Тьюринга.

Язык программирования является Тьюринг-полным (Turing-complete), если любая вычислимая функция, может быть вычислена конечной программой, записанной на этом языке.

Большинство широко используемых языков программирования — тьюринг-полные.


на русском, со справкой и примерами
files.unn(489.3 Kb)

ibitsa, хоть поподробнее бы написал, что это и зачем

Чтобы логическое мышление развивать... вот есть ещё нормальные алгорифмы Маркова... вот так ещё круче