Google Doodle — Головоломка с машиной Тьюринга — Обновление: сыграйте сейчас

Обновление: машина Тьюринга Google Doodle, которая была готова отпраздновать 100-летие Алана Тьюринга всего на день, вернулась. Теперь вы можете играть в нее сколько угодно и когда захотите.

Дудл доступен в живой игровой форме в архиве дудлов.

Google Doodle часто является шедевром дизайна, но на этот раз это шедевр информатики. Каракули — это полная машина Тьюринга, с которой вы можете взаимодействовать, пытаясь решить головоломку.

Что действительно интересно, так это то, что этот простой рисунок демонстрирует все идеи программирования — условные выражения и циклы, данные и хранилище — а также идею машины хранимых программ.

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

В случае каракуля лента ограничена тем, что вы видите на экране, а контроллер ограничен операциями, которые вам предоставляются на каждом этапе головоломки.

В чем именно загадка?

Если вы нажмете зеленую кнопку «Перейти», вы увидите число в поле вверху справа. Это целевой номер, который дает первую букву Google, то есть G. Ваша проблема состоит в том, чтобы решить, как настроить контроллер на преобразование начального числа на ленте в целевое число.

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

Например, на исходной ленте есть стрелка влево и стрелка вправо, что означает просто переместить ленту на одно место в этом направлении. Состояние с 0 записывает ноль в эту позицию, а состояние с 1 записывает единицу в эту позицию.

Оповещение о спойлере — здесь описано решение первой буквы. Если вам не нужна помощь, переходите к «Легко!».

Например, если вам дана следующая стартовая конфигурация:

Затем, если вы просто нажмете зеленую кнопку Go, произойдет то, что устройство чтения ленты переместится на одно место влево, запишет 0, затем переместится на три места вправо и запишет 0. Результатом будет 00010, что не целевой номер.

Чтобы получить целевой номер, вы должны изменить инструкции «записать 0» на инструкции «записать 1» — вы просто щелкаете по ним, чтобы изменить их. Если вы снова запустите машину, вы обнаружите, что она перемещается влево, записывает 1, перемещается на три позиции вправо и записывает 1, что дает правильное значение:

Затем рисунок проверяет, совпадают ли два числа, и если они совпадают, он дает вам первую букву — G.

Легкий!

Что ж, первый шаг прост, но уровень необходимой логики повышается с каждой буквой Google.

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

Контроллер выше говорит — «Перемещает на одно место влево, если на ленте есть 0, перейти в состояние ниже и записать ноль». Затем программа завершается, потому что остальные состояния справа пусты.

Третья буква вводит состояние обратной петли:

Если вы нажмете на значок круглой стрелки, то в каком состоянии вы вернетесь к изменениям. В этой части головоломки вам просто нужно решить, в какое состояние вернуться.

После этого никаких новых государственных символов не вводится, но проблемы усложняются. Последний просит вас выбрать правильную версию из четырех операций.

Это действительно очень весело, и наблюдение за тем, как машина выполняет свою «программу», действительно дает вам представление о том, как на самом деле работает машина Тьюринга или любой другой компьютер.

Когда вы решите первые шесть головоломок, вы увидите, что «большая» программа выполняет последовательность 1,10,101,10110 ,,,

Если вы решите первые шесть головоломок, вам будут предложены еще шесть более сложных. Все, что вам нужно сделать, чтобы увидеть новый набор проблем, — это попытаться воспроизвести снова — обновите страницу и нажмите зеленую стрелку.

Небольшое примечание: двоичный код, используемый для представления букв, — это старый код телетайпа Бодо, который использовался в то время, когда Тьюринг взламывал коды.

Если вы действительно застряли, есть видео, которое показывает вам решения, но не смотрите его!

Постарайтесь не смотреть это видео! В нем есть ответ, но нет никаких объяснений.

Благодарим Google за забавный и познавательный рисунок.

К счастью, Google Doodles не так эфемерны, как кажется. Если вы хотите найти его в архиве Google Doodle, помните, что это каракули к 100-летию со дня рождения Алана Тьюринга, 23 июня 2012 г.