23 июня 1912 года родился Алан Тьюринг – английский математик, логик, криптограф. Он внес большой вклад в развитие информатики, в его честь названа самая престижная в мире награда в области информатики – Премия Тьюринга. Во время Второй мировой Тьюринг активно занимался криптоанализом, в том числе криптоанализом немецкого шифратора Enigma (на портале Эрудит.Онлайн есть конкурс по криптографии «Энигма»). В этой статье остановимся подробнее на машине Тьюринга и попытаемся объяснить ее работу максимально простым языком...

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