Машины Тьюринга для чайников

Чем машина Тьюринга отличается от «обычного» компьютера

В какой-то момент вы познакомились с машинами Тьюринга как с первым теоретическим описанием компьютера. Однако, если вы были похожи на меня, когда вы впервые познакомились с машиной Тьюринга, объяснение не имело большого смысла.

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

Я попытаюсь объяснить компьютер Тьюринга, сравнивая его различные части с обычным компьютером, следуя тому, что мы называем архитектурой фон Неймана.

Практический пример машины Тьюринга

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

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

В то время электронной памяти, которая могла бы хранить целые программы, не существовало, и люди не были знакомы с ней. Однако люди привыкли отображать данные на перфолентах. Телетайпы, биржевые котировки, телеграфы и т. Д. Использовали перфоленту для хранения и загрузки данных.

Кассета

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

Машинный алфавит

«Предопределенный алфавит?» Что это за чепуха? Это сделано для того, чтобы учесть тот факт, что теоретически машина может иметь множество различных способов представления данных. Например. компьютер, с которым вы обычно работаете, работает с единицами и нулями. Таким образом, алфавит - это всего лишь 0 и 1. Алфавит в этом контексте означает просто набор символов. Каждая ячейка на ленте должна быть буквой этого алфавита.

Деревянная машина Тьюринга имеет алфавит b, 0 и 1. Каждая из этих «букв» представлена ​​тремя различными конфигурациями деревянных колышков.

Разностная машина Чарльза Бэббиджа, напротив, не была двоичным цифровым компьютером. Вместо этого он работал напрямую с десятичными числами. Таким образом, его алфавит состоял из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Каждая из этих цифр (или символов) в алфавите машины была представлена ​​позицией шестерни с десятью зубы. В современном цифровом компьютере 1 и 0 представлены двумя разными уровнями напряжения.

Однако имейте в виду, что то, что такое ячейка, является весьма теоретическим. До сих пор мы думали об этом как об отдельных битах или цифрах. Однако это может быть и целый байт. Дело в том, что ячейка читается как единое целое и обрабатывается как единое целое.

Чтение и перемещение ленты

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

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

Сравнение с машиной фон Неймана

В машине фон Неймана программа хранится в оперативной памяти. ЦП компьютера считывает инструкцию из памяти и выполняет ее. Инструкцией могут быть такие вещи, как:

  1. Считать байт из ячейки памяти 3 в регистр 4 ЦП.
  2. Сложите байты в регистре 3 и 4, как если бы они были целыми числами, и сохраните результат в регистре 3.
  3. Запишите 2 байта в регистр 5 внутри ЦП в ячейку памяти 6.
  4. Умножьте два числа в двух разных регистрах, вычтите или разделите.
  5. Измените счетчик программ (переход), чтобы начать выполнение кода в другом месте в памяти.
  6. Условный прыжок. Переход к определенной инструкции в памяти в зависимости от результата предыдущего расчета.

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

Чтение и запись данных

Лента - это место, где вы читаете и записываете данные. Это не то место, где вы получаете инструкции к программе. И это не оперативная память. В машине фон Неймана вы можете сказать: запишите это число в память в ячейку 4. В машине Тьюринга вы можете записывать только в текущую позицию. Других вариантов нет.

Выполнение программы

В машине фон Неймана программа находилась в памяти в виде набора инструкций, которые считывались последовательно. Программа в машине Тьюринга не такая. Он не читается по одной инструкции за раз. Он не организован как последовательность инструкций.

Вместо этого это немного похоже на программирование на основе событий. Когда вы программируете графический интерфейс, вы присоединяете код к таким событиям, как «нажата кнопка A» или «ползунок C перетащили». Машина Тьюринга немного похожа в том, что в таблице конфигурации указано, что должно произойти для данного состояния, когда определенный символ считывается в текущей ячейке ленты ввода / вывода.

У машины Тьюринга есть какая-то ячейка памяти, которая отслеживает ее текущее состояние. Состояние может быть просто числом или буквой. Текущее состояние в сочетании с тем, что читается на ленте, формирует входные данные для «программы» в таблице конфигурации.

Машина Тьюринга - это то, что мы называем конечным автоматом.

Выше представлена ​​схема такой машины. Каждый кружок с такими буквами, как A, B, C и H, обозначает состояния, в которых может находиться машина. Стрелки обозначают возможные переходы между состояниями. Например, C имеет стрелки, указывающие на B и H. Это означает, что можно перейти из состояния C в состояние B или H. Однако невозможно перейти из C в A.

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

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

  • 1/1,R стрелка, возвращающаяся на B.
  • 0/1,L стрелка идет от B к A.

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

0/1,L похоже. Когда на кране читается 0, переходите к следующему состоянию, как показано на диаграмме. Затем мы печатаем 1, прежде чем перемещать левую ленту.

Как это работает с арифметикой?

Вы, наверное, заметили, что на машине Тьюринга не определены никакие конкретные инструкции, такие как сложение, вычитание, умножение и т. Д. Машина Тьюринга гораздо более универсальна.

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

Пример вычитания

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

Это очень неэффективно, но выполняет свою работу. Помните, что идея машины Тьюринга состоит не в том, чтобы уметь эффективно вычислять, а в том, чтобы иметь возможность вычислять что-либо, что можно вычислить, с помощью как можно более простой машины.

Чтобы упростить задачу, мы не используем десятичные числа, мы даже не используем двоичные числа! Нет, мы используем унарные числа. Итак, вам нужно считать единицы. Число 3 записывается как 111. Число 4 записывается как 1111 и так далее. Это будет ужасно неэффективно при работе, скажем, с тысячами, но это не имеет значения, потому что машина Тьюринга - это математическая конструкция с бесконечно длинной лентой для хранения информации.

Итак, мой алфавит состоит из 1, 0 и c. Мы используем 1 для обозначения единиц и 0 для обозначения. Итак, 110, 011 и 101 означают всего два. c используется для разделения двух вычитаемых чисел. Таким образом, 111c1111 означает 4 - 3. В качестве альтернативы вы можете думать об этом как о 3 - 4, и в этом случае число единиц представляет собой отрицательное число.

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

Вот пример:

A  →111c1111  1/0,R

Это говорит о том, что мы находимся в состоянии A, и лента выглядит как 111c1111, а край, который переходит в B в этом случае, помечен 1/0,R, что означает, что чтение 1 запускает этот переход и вызывает выполнение действий 0,R. Эти действия записывают 0 и перемещают R вправо на ленте. → говорит, где на ленте мы находимся. Какой сейчас символ.

Итак, вот шаги:

A  →111c1111  1/0,R
B  0→11c1111  1/1,R
B  01→1c1111  1/1,R
B  011→c1111  c/c,R
C  011c→1111  1/0,L
D  011→c0111  c/c,L
E  01→1c0111  1/1,L
E  0→11c0111  1/1,L
E  →011c0111  0/0,R
A  0→11c0111  1/0,R
B  00→1c0111  1/1,R
B  000→c0111  c/c,R
C  000c→0111  0/0,R
C  000c0→111  1/0,L
D  000c→0011  0/0,L

Это продолжается некоторое время. Если вы будете следовать шаблону, то вы можете заметить, что машина Тьюринга движется вперед и назад с каждой стороны символа c. Каждый раз, когда он посещает одну сторону, он стирает единицу, а затем переходит на другую сторону и стирает там 1, заменяя ее на 0.

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

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

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

Резюме

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

  1. Лента машины Тьюринга не там, где считываются данные и инструкции. Вы не можете сравнить это с памятью программ. «Программный код», если хотите, можно представить как существующий в таблице конфигурации. Эта таблица представлена ​​в виде диаграммы состояний с кружками, соединенными стрелками.
  2. Входные данные поступают с ленты. Однако именно здесь машина Тьюринга записывает свой вывод.
  3. Нет, машина Тьюринга - это не двоичный компьютер. Он может работать с любым количеством символов, а не только с 0 и 1. Вы определяете, какие символы разрешены, определяя его алфавит.

Это не должно быть эффективным, просто чтобы быть простым.