Состояние
Шаги
Символы на ленте
Статус

Состояние Читает Пишет Сдвиг Следующее состояние

Подробнее о машинах Тьюринга

Симулятор машины Тьюринга

Машина Тьюринга — простейший из возможных компьютеров: головка, которая читает один символ бесконечной ленты, записывает символ, сдвигается на одну ячейку влево или вправо и меняет состояние, следуя короткой таблице правил. Алан Тьюринг придумал её в 1936 году, и всё, что делает ваш компьютер, в принципе можно сделать таким способом. Напишите свои правила или загрузите пример, нажмите «Пуск» и смотрите, как лента меняется шаг за шагом, а под ней строится диаграмма всей её истории. Выберите программу или напишите свою, введите входные данные и нажмите «Пуск» — или «Шаг», чтобы выполнять по одному правилу за раз; «Назад» отменяет шаг. Каждая строка программы — одно правило: состояние, читаемый символ, записываемый символ, сдвиг (L, R или N — без сдвига) и следующее состояние, например A 0 -> 1 R B. Пустую ячейку обозначайте _. Машина начинает в состоянии первого правила, на первом символе входных данных, и останавливается в H, accept или reject либо когда ни одно правило не подходит. Диаграмма показывает ленту после каждого шага, сверху вниз.

Как это работает

  1. Выберите пример программы или напишите правила вида A 0 -> 1 R B, по одному в строке, и введите входные данные.
  2. Нажмите «Пуск», чтобы смотреть, как движется головка, или «Шаг», чтобы выполнять по одному правилу за раз; «Назад» отменяет шаг.
  3. Смотрите состояние, число шагов и символы на ленте на плитках, а историю ленты — на диаграмме.

Как работает машина

В каждый момент машина находится в одном из нескольких состояний, а её головка стоит на одной ячейке ленты. Правило для этого состояния и символа под головкой говорит три вещи: какой символ записать в ячейку, сдвинуться ли влево, вправо или остаться на месте и в какое состояние перейти дальше. Вот и вся машина. Она останавливается, когда достигает состояния остановки, например H, accept или reject, или когда ни одно правило не подходит. Программе, которая прибавляет 1 к двоичному числу, нужно всего девять таких правил.

Усердные бобры

Какая машина с n состояниями, запущенная на пустой ленте, запишет больше всего единиц, прежде чем остановится? Этот вопрос задал Тибор Радо в 1962 году. Чемпионов называют усердными бобрами, и они растут быстрее любой функции, которую может вычислить компьютер. Два состояния дают 4 единицы за 6 шагов, три состояния — 6 единиц, четыре состояния — 13 единиц за 107 шагов. Чемпион с пятью состояниями, найденный в 1989 году, записывает 4098 единиц за 47 176 870 шагов, а в 2024 году участники онлайн-проекта доказали с помощью проверенной компьютером математики, что ни одна другая останавливающаяся машина с пятью состояниями не работает дольше.

Часто задаваемые вопросы

Как записать правило?

Одно правило в строке: текущее состояние, читаемый символ, записываемый символ, сдвиг (L, R или N) и следующее состояние, например A 0 -> 1 R B. Стрелка и запятые необязательны. Пустую ячейку обозначайте _, а комментарий — #. Машина начинает в состоянии первого правила; следующее состояние с именем H или halt останавливает её, а accept и reject останавливают её с вердиктом.

Может ли машина Тьюринга действительно вычислить что угодно?

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

Почему счётчик никогда не останавливается?

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

Как усердный бобёр с пятью состояниями может выполнить здесь 47 миллионов шагов?

Лента хранится как компактный массив, растущий в обе стороны, а на самой высокой скорости приложение выполняет сотни тысяч шагов между обновлениями экрана, так что весь прогон занимает несколько секунд в современном браузере. Диаграмма записывает только первые 400 шагов, ведь картинка из 47 миллионов строк не поместилась бы ни на одном экране.

Отправляется ли что-нибудь на сервер?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор