June 22, 2012

Машина Тьюринга на сайте Гугла

Очередной дудл появился на сайте Гугла. Дудлы – это различные вариации логотипа Google, приуроченные к определенным событиям, праздникам, юбилеям и т. д. Я уже как-то писал про синтезатор Муга, а сегодня вы будете приятно удивлены тем, что на странице Гугла уже начал работать оригинальный дудл с анимированной машинкой Тьюринга (уже тысячной с 1998 года) по случаю 100-летия со дня рождения её изобретателя — Алана Тьюринга.

Машина Тьюринга была пригодна для решения любой разрешимой математической или логической задачи. В 1936 г., будучи студентом Кембриджского университета, английский математик Алан Тьюринг написал статью "О вычислимых числах", в которой рассмотрел гипотетическое устройство (впоследствии получившее название "машина Тьюринга") - прообраз программируемого компьютера.

Машина Тьюринга предназначалась для выполнения логических операций: она могла читать, писать и стирать символы, записанные в клетках бесконечной ленты. На каждом шаге вычислений следующее действие машины целиком и полностью определялось ее текущим состоянием и символом, который в данный момент считывается.

Команды машины Тьюринга описывают пять состояний; в каждом из них от машины требуется выполнить определенные действия. В приведенном здесь примере машина Тьюринга настроена на удвоение целых положительных чисел. Ее команды описывают пять состояний; в каждом из них от машины требуется выполнить определенные действия. Свою работу машина Тьюринга начинает в состоянии 1, в этот момент считывающая головка установлена в начало записанного числа. Машина завершит работу после выполнения 16 шагов - в этот момент на ленте будет записано удвоенное количество символов.

Цель Алана Тьюринга заключалась не в изобретении компьютера, а в описании задач, не имеющих решения. Вместе с тем в гипотетической машине Тьюринга были предвосхищены некоторые черты современных компьютеров. Например, бесконечную ленту можно рассматривать как своеобразную универсальную внутреннюю память.

Можете также просмотреть видео "How to solve the ALAN TURING Google Doodle"