Машина Тьюринга – это теоретическая модель вычислений, предложенная Аланом Тьюрингом в 1936 году. Она представляет собой абстрактное устройство, состоящее из: 1. Бесконечной ленты: Лента разделена на ячейки, каждая из которых содержит один символ из конечного алфавита. Лента может быть как бесконечной вправо, так и вправо и влево, но важно, чтобы она была бесконечной в каком-то направлении. 2. Головки чтения/записи: Головка может двигаться по ленте влево или вправо, читать символ в текущей ячейке, записывать в неё другой символ и изменять своё состояние...

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