Как стирать в машине тьюринга
Алан Тьюринг
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
A={a1, a2, a3, …, an} — внешний алфавит, служит для записи исходных данных
Q={q1, q2, q3,…, qm} — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.
Машина Тьюринга
Каждая ячейка ленты может содержать символ из внешнего алфавита A = {a0,a1,…,an} (В нашем случае A={0, 1})
Допустимые действия Машины Тьюринга таковы:
1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)
2) сместиться в соседнюю ячейку
3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = {q0,q1,…,qm}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние, попав в него, автомат заканчивает работу.
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «<» (влево) или «.» (на месте)
· новое состояние автомата
В приведенной выше таблице алфавит A ={0, 1, _} (содержит 3 символа), а внутренний алфавит Q={q1, q2, q3, q4, q0}, q0 — состояние, заставляющее каретку остановиться.
Рассмотрим несколько задач решением. Скачать машину Тьюринга Вы можете на сайте в разделе СКАЧАТЬ.
Задача 1. Пусть A={0, 1, _}. На ленте в ячейках находятся символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.
Теперь определимся с состояниями каретки. Я называю их — «желания каретки что-то сделать».
q1) Каретка должна пойти вправо: если видит 0 меняет его на 1 и остается в состоянии q1, если видит 1 — меняет его на 0 и остается в состоянии q1, если видит _ — ворачивается назад на 1 ячейку «желает что-то другое», т.е переходит в состояние q2. Запишем наши рассуждения в таблицу исполнителя. Синтаксис смотрите в справке к программе)
q2) Теперь опишем «желание каретки» q2. Мы должны вернуться в первоначальное положение. Для этого: если видим 1 оставляем ее и остаемся в состоянии q2 (с тем же желанием дойти до конца ряда символов); если видим 0 — оставляем его и продолжаем двигаться влево в состоянии q2; видим _ — сдвигается вправо на 1 ячейку. Вот вы оказались там, где требуется в условии задачи. переходим в состояние q0.
Посмотреть работу программы можно на видео:
Задача 2. Дано: конечная последовательность 0 и 1 (001101011101). Необходимо выписать их после данной последовательности, через пустую ячейку, а в данной последовательности заменить их на 0. Например:
Из 001101011101 получим 000000000000 1111111.
Как видите, семь единиц записались после данной последовательности, а на их местах стоят нолики.
Приступим к рассуждениям. Определим, какие состояния необходимы каретке и сколько.
q1) увидел 1 — исправь на нолик и перейди в другое состояние q2 (новое состояние вводится, чтобы каретка не поменяла на нули все единицы за один проход)
q2) ничего не менять, двигаться к концу последовательности
q3) как только каретка увидела пустую ячейку, она делает шаг вправо и рисует единичку, если она видит единичку — то движется дальше, чтобы подписать символ в конце. Как только нарисовал единицу, переходим в состояние q4
q4) проходим по написанным единицам, ничего не меняя. Как только доходим до пустой ячейки, разделяющей последовательность от единиц, переходим с новое состояние q5
q5) в этом состоянии идем начало последовательности, ничего не меняя. Доходим до пустой ячейки, разворачиваемся и переходим в состояние q1
Состояние q0 каретка примет в том случае, когда она пройдет в состоянии q1 до конца данной последовательности и встретит пустую ячейку.
Получим такую программу:
Работу Машины Тьюринга можете посмотреть на видео ниже.
Машина Тьюринга — одно из самых интригующих и захватывающих интеллектуальных открытий 20-го века. Это простая и полезная абстрактная модель вычислений (компьютерных и цифровых), которая является достаточно общей для воплощения любой компьютерной задачи. Благодаря простому описанию и проведению математического анализа она образует фундамент теоретической информатики. Это исследование привело к более глубокому познанию цифровых компьютеров и исчислений, включая понимание того, что существуют некоторые вычислительные проблемы, не решаемые на общих пользовательских ЭВМ.
Что это и кто создал
Алан Тьюринг стремился описать наиболее примитивную модель механического устройства, которая имела бы те же основные возможности, что и компьютер. Тьюринг впервые описал машину в 1936 году в статье «О вычислимых числах с приложением к проблеме разрешимости», которая появилась в Трудах Лондонского математического общества.
Машина Тьюринга является вычислительным устройством, состоящим из головки чтения/записи (или «сканера») с бумажной лентой, проходящей через него. Лента разделена на квадраты, каждый из которых несет одиночный символ — «0» или «1». Назначение механизма состоит в том, что он выступает и как средство для входа и выхода, и как рабочая память для хранения результатов промежуточных этапов вычислений.
Из чего состоит устройство
Каждая такая машина состоит из двух составляющих:
- Неограниченная лента. Она является бесконечной в обе стороны и разделена на ячейки.
- Автомат – управляемая программа, головка-сканер для считывания и записи данных. Она может находиться в каждый момент в одном из множества состояний.
Каждая машина связывает два конечных ряда данных: алфавит входящих символов A = {a0, a1, …, am} и алфавит состояний Q = {q0, q1, …, qp}. Состояние q0 называют пассивным. Считается, что устройство заканчивает свою работу, когда попадает именно на него. Состояние q1 называют начальным — машина начинает свои вычисления, находясь на старте в нем. Входное слово располагается на ленте по одной букве подряд в каждой позиции. С обеих сторон от него располагаются только пустые ячейки.
Как работает механизм
Машина Тьюринга имеет принципиальное отличие от вычислительных устройств – ее запоминающее приспособление имеет бесконечную ленту, тогда как у цифровых аппаратов такое устройство имеет полосу определенной длины. Каждый класс заданий решает только одна построенная машина Тьюринга. Задачи иного вида предполагают написание нового алгоритма.
Управляющее устройство, находясь в одном состоянии, может передвигаться в любую сторону по ленте. Оно записывает в ячейки и считывает с них символы конечного алфавита. В процессе перемещения выделяется пустой элемент, который заполняет позиции, не содержащие входные данные. Алгоритм для машины Тьюринга определяет правила перехода для управляющего устройства. Они задают головке записи-чтения такие параметры: запись в ячейку нового символа, переход в новое состояние, перемещение влево или вправо по ленте.
Свойства механизма
Машина Тьюринга, как и другие вычислительные системы, имеет присущие ей особенности, и они сходны со свойствами алгоритмов:
- Дискретность. Цифровая машина переходит к следующему шагу n+1 только после того, как будет выполнен предыдущий. Каждый выполненный этап назначает, каким будет n+1.
- Понятность. Устройство выполняет только одно действие для одной же ячейки. Оно вписывает символ из алфавита и делает одно движение: влево или вправо.
- Детерминированность. Каждой позиции в механизме соответствует единственный вариант выполнения заданной схемы, и на каждом этапе действия и последовательность их выполнения однозначны.
- Результативность. Точный результат для каждого этапа определяет машина Тьюринга. Программа выполняет алгоритм и за конечное число шагов переходит в состояние q0.
- Массовость. Каждое устройство определено над допустимыми словами, входящими в алфавит.
Функции машины Тьюринга
В решении алгоритмов часто требуется реализация функции. В зависимости от возможности написания цепочки для вычисления, функцию называют алгоритмически разрешимой или неразрешимой. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В – слова в рамках двоичного кодового алфавита В={0.1}. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.
Программа для устройства
Программы для механизма Тьюринга оформляются таблицами, в которых первые строка и столбец содержат символы внешнего алфавита и значения возможных внутренних состояний автомата — внутренний алфавит. Табличные данные являются командами, которые воспринимает машина Тьюринга. Решение задач происходит таким образом: буква, считываемая головкой в ячейке, над которой она в данный момент находится, и внутреннее состояние головки автомата обусловливают, какую из команд необходимо выполнять. Конкретно такая команда находится на пересечении символов внешнего алфавита и внутреннего, находящихся в таблице.
Составляющие для вычислений
Чтобы построить машину Тьюринга для решения одной определенной задачи, необходимо определить для нее следующие параметры.
Внешний алфавит. Это некоторое конечное множество символов, обозначающихся знаком А, составляющие элементы которого именуются буквами. Один из них — а0 — должен быть пустым. Для примера, алфавит устройства Тьюринга, работающего с двоичными числами, выглядит так: A = {0, 1, а0}.
Непрерывная цепочка букв-символов, записываемая на ленту, именуется словом.
Автоматом называется устройство, которое работает без вмешательства людей. В машине Тьюринга он имеет для решения задач несколько различных состояний и при определенно возникающих условиях перемещается из одного положения в другое. Совокупность таких состояний каретки есть внутренний алфавит. Он имеет буквенное обозначение вида Q={q1, q2…}. Одно из таких положений — q1 — должно являться начальным, то есть тем, что запускает программу. Еще одним необходимым элементом является состояние q0, которое является конечным, то есть тем, что завершает программу и переводит устройство в позицию остановки.
Таблица переходов. Эта составляющая представляет собой алгоритм поведения каретки устройства в зависимости от того, каковы в данный момент состояние автомата и значение считываемого символа.
Алгоритм для автомата
Кареткой устройства Тьюринга во время работы управляет программа, которая во время каждого шага выполняет последовательность следующих действий:
- Запись символа внешнего алфавита в позицию, в том числе и пустого, осуществляя замену находившегося в ней, в том числе и пустого, элемента.
- Перемещение на один шаг-ячейку влево или же вправо.
- Изменение своего внутреннего состояния.
Таким образом, при написании программ для каждой пары символов либо положений необходимо точно описать три параметра: ai – элемент из выбранного алфавита A, направление сдвига каретки («←” влево, «→” вправо, «точка” — отсутствие перемещения) и qk — новое состояние устройства. К примеру, команда 1 «←” q2 имеет значение «заместить символ на 1, сдвинуть головку каретки влево на один шаг-ячейку и сделать переход в состояние q2”.
Машина Тьюринга: примеры
Пример 1. Дана задача построить алгоритм, прибавляющий единицу к последней цифре заданного числа, расположенного на ленте. Входные данные – слово – цифры целого десятичного числа, записанные в последовательные ячейки на ленту. В первоначальный момент устройство располагается напротив самого правого символа – цифры числа.
Решение. В случае если последняя цифра равняется 9, то ее нужно заменить на 0 и затем прибавить единицу к предшествующему символу. Программа в этом случае для данного устройства Тьюринга может быть написана так:
| a0 | 1 | 2 | 3 | … | 7 | 8 | 9 | ||
| q1 | 1 H q0 | 1 H q0 | 2 H q0 | 3 H q0 | 4 H q0 | … | 8 H q0 | 9 H q0 | 0 λ q1 |
Здесь q1 — состояние изменения цифры, q0 — остановка. Если в q1 автомат фиксирует элемент из ряда 0..8, то он замещает ее на один из 1..9 соответственно и затем переключается в состояние q0, то есть устройство останавливается. В случае если же каретка фиксирует число 9, то замещает ее на 0, затем перемещается влево, останавливаясь в состоянии q1. Такое движение продолжается до того момента, пока устройство не зафиксирует цифру, меньшую 9. Если все символы оказались равными 9, они замещаются нулями, на месте старшего элемента запишется 0, каретка переместится влево и запишет 1 в пустую клетку. Следующим шагом будет переход в состояние q0 – остановка.
Пример 2. Дан ряд из символов, обозначающих открывающие и закрывающие скобки. Требуется построить устройство Тьюринга, которое выполняло бы удаление пары взаимных скобок, то есть элементов, расположенных подряд – “( )”. Например, исходные данные: “) ( ( ) ( ( )”, ответ должен быть таким: “) . . . ( (”. Решение: механизм, находясь в q1, анализирует крайний слева элемент в строке.
| a0 | ( | ) | |
| q1 | a0 H q0 | ( П q2 | ) П q1 |
| q2 | a0 H q0 | ( П q2 | ) λ q3 |
| q3 | a0 H q0 | a0 П q3 | a0 П q1 |
Состояние q1: если встречен символ “(”, то совершить сдвиг вправо и переход в положение q2; если определен “a0”, то остановка.
Состояние q2: проводится анализ скобки “(” на наличие парности, в случае совпадения должно получиться “)”. Если элемент парный, то сделать возврат каретки влево и перейти в q3.
Состояние q3: осуществить удаление сначала символа “(”, а затем “)” и перейти в q1.
Художественное представление машины Тьюринга
Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
То есть всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга[1].
Устройство[править | править код]
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки[2][3], и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм,
реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку
новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и
ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
Описание машины Тьюринга[править | править код]
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Пример[править | править код]
Пример машины Тьюринга для умножения чисел в унарной системе счисления.
Запись правила «qiaj→qi1aj1R/L/N» следует понимать так: qi — состояние при котором выполняется это правило, aj — данные в ячейке, в которой находится головка, qi1 — состояние в которое нужно перейти, aj1 — что нужно записать в ячейку, R/L/N — команда на перемещение.
Машина работает по следующему набору правил:
| q0 | q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 |
|---|---|---|---|---|---|---|---|---|
| 1 | q01→q01R | q11→q2aR | q21→q21L | q31 → q4aR | q41→q41R | q71→q2aR | ||
| × | q0×→q1×R | q2×→q3×L | q4×→q4×R | q6×→q7×R | q8×→q9×N | |||
| = | q2=→q2=L | q4=→q4=R | q7=→q8=L | |||||
| a | q2a→q2aL | q3a→q3aL | q4a→q4aR | q6a→q61R | q7a→q7aR | q8a→q81L | ||
| * | q0*→q0*R | q3*→q6*R | q4*→q51R | |||||
| q5 →q2*L |
Описание состояний:
| Начало | |
| q0 | начальное состояние. Ищем «x» справа. При нахождении переходим в состояние q1 |
|---|---|
| q1 | заменяем «1» на «а» и переходим в состояние q2 |
| Переносим все «1» из первого числа в результат | |
| q2 | ищем «х» слева. При нахождении переходим в состояние q3 |
| q3 | ищем «1» слева, заменяем её на «а» и переходим в состояние q4. В случае если «1» закончились, находим «*» и переходим в состояние q6 |
| q4 | переходим в конец (ищем «*» справа), заменяем «*» на «1» и переходим в состояние q5 |
| q5 | добавляем «*» в конец и переходим в состояние q2 |
| Обрабатываем каждый разряд второго числа | |
| q6 | ищем «х» справа и переходим в состояние q7. Пока ищем заменяем «а» на «1» |
| q7 | ищем «1» или «=» справа при нахождении «1» заменяем его на «а» и переходим в состояние q2 при нахождении «=» переходим в состояние q8 |
| Конец | |
| q8 | ищем «х» слева. При нахождении переходим в состояние q9. Пока ищем заменяем «а» на «1» |
| q9 | терминальное состояние (остановка алгоритма) |
Умножим с помощью МТ 3 на 2 в единичной системе.
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).
Начало. Находимся в состоянии q0, ввели в машину данные: *111×11=*, головка машины располагается на первом символе *.
1-й шаг. Смотрим по таблице правил что будет делать машина, находясь в состоянии q0 и над символом «*». Это правило из 1-го столбца 5-й строки — q0*→q0*R. Это значит, что мы переходим в состояние q0 (то есть не меняем его), символ станет «*» (то есть не изменится) и смещаемся по введённому нами тексту «*111×11=*» вправо на одну позицию (R), то есть на 1-й символ 1. В свою очередь, состояние q01 (1-й столбец 1-я строка) обрабатывается правилом q01→q01R. То есть снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ «х». И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.
Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву «а», и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на «а» и дописывания такого же количества единиц в конце строки (слева от крайнего правого «*»). Затем меняем все «а» до знака умножения «х» обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой «а» и снова переносим единицы. Когда до знака «=» не окажется единиц — значит умножение завершено.
Полнота по Тьюрингу[править | править код]
Можно сказать, что машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам преобразует входные данные с помощью последовательности элементарных действий.
Элементарность действий заключается в том, что действие меняет лишь небольшой фрагмент данных в памяти (в случае машины Тьюринга — лишь одну ячейку), и число возможных действий не бесконечно. Несмотря на простоту машины Тьюринга, на ней можно вычислить всё, что можно вычислить на любой другой машине, осуществляющей вычисления с помощью последовательности элементарных действий. Это свойство называется полнотой.
Один из естественных способов доказательства того, что алгоритмы вычисления, которые можно реализовать на одной машине, можно реализовать и на другой, — это имитация первой машины на второй.
Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины и входные данные , которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные .
Как было сказано, на машине Тьюринга можно имитировать (с помощью задания правил перехода) все другие исполнители, каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью: суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но тем не менее всегда конечна. Теоретический предел количества информации, которая может находиться внутри заданной поверхности, с точностью до множителя равен энтропии чёрной дыры с той же площадью поверхности.
Варианты машины Тьюринга[править | править код]
Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга.
Машина Тьюринга, работающая на полубесконечной ленте[править | править код]
В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте (то есть на ленте, бесконечной в одну сторону).
Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых, произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:
Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:
Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.
Двумерные машины Тьюринга[править | править код]
- Муравей Лэнгтона
См. также[править | править код]
- JFLAP кроссплатформенная программа — симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата
- Универсальная машина Тьюринга
- Недетерминированная машина Тьюринга
- Вероятностная машина Тьюринга
- Квантовая машина Тьюринга
- Теория алгоритмов
- Тьюринговская трясина
- Диаграмма Тьюринга
- Машина Минского
Другие абстрактные исполнители и формальные системы вычислений[править | править код]
- Нормальный алгоритм Маркова (продукционное программирование)
- Машина Поста (автоматное программирование)
- Рекурсивная функция (теория вычислимости)
- Лямбда-исчисление (функциональное программирование)
- Brainfuck (императивное программирование)
Примечания[править | править код]
Литература[править | править код]
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: Вильямс, 2002. — 528 с. — ISBN 0-201-44124-1.
- Карпов Ю. Г. Теория автоматов. — Питер, 2003. — ISBN 5-318-00537-3.
- Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г. Машины Тьюринга и рекурсивные функции. — М.: Мир, 1972. — 262 с.
- Нефёдов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 260 с.
Ссылки[править | править код]
- Машина Тьюринга // Лекция Александра Шеня в проекте ПостНаука (06.04.2013)