Алан Тьюринг
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
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 до конца данной последовательности и встретит пустую ячейку.
Получим такую программу:
Работу Машины Тьюринга можете посмотреть на видео ниже.
ПРЕДЛАГАЮ КОЛЛЕГАМ
Тема “Машина Тьюринга” в школьном
курсе информатики
И.Н. Фалина,
Москва
Во многих учебниках по информатике при
изучении понятия и свойств алгоритма
присутствуют фразы такого содержания:
“…существует много разных способов для записи
одного и того же алгоритма, например, запись в
виде текста, запись в виде блок-схемы, запись на
каком-либо алгоритмическом языке, представление
алгоритма в виде машины Тьюринга или машины
Поста…”. К сожалению, такого типа фразы являются
единственными, где упоминается машина Тьюринга.
Без сомнения, объем часов, отводимых на изучение
алгоритмов, не позволяет включать в эту тему еще
и изучение способов записи алгоритма в виде
машины Тьюринга. Но эта тема крайне интересна,
важна и полезна для школьников, особенно
увлекающихся информатикой.
Тема “Машина Тьюринга” может
изучаться в 8–11-х классах в рамках темы
“Информационные процессы. Обработка
информации”, на факультативных занятиях, в
системе дополнительного образования, например, в
школах юных программистов. Изучение этой темы
может сопровождаться компьютерной поддержкой,
если у учителя есть программный
тренажер-имитатор “Машина Тьюринга”. В классах
с углубленным изучением программирования
школьники могут самостоятельно написать
программу “Машина Тьюринга”. В рамках этой
статьи вашему вниманию предлагается практикум
по решению задач на тему “Машина Тьюринга”.
Теоретический материал по данной теме не раз
печатался на страницах газеты “Информатика”,
например, в № 3/2004 статья И.Н. Фалиной “Элементы
теории алгоритмов”.
Краткий теоретический материал
Машина Тьюринга — это строгое
математическое построение, математический
аппарат (аналогичный, например, аппарату
дифференциальных уравнений), созданный для
решения определенных задач. Этот математический
аппарат был назван “машиной” по той причине, что
по описанию его составляющих частей и
функционированию он похож на вычислительную
машину. Принципиальное отличие машины Тьюринга
от вычислительных машин состоит в том, что ее
запоминающее устройство представляет собой
бесконечную ленту: у реальных вычислительных
машин запоминающее устройство может быть как
угодно большим, но обязательно конечным. Машину
Тьюринга нельзя реализовать именно из-за
бесконечности ее ленты. В этом смысле она мощнее
любой вычислительной машины.
В каждой машине Тьюринга есть две
части:
1) неограниченная в обе стороны лента,
разделенная на ячейки;
2) автомат (головка для
считывания/записи, управляемая программой).
С каждой машиной Тьюринга связаны два
конечных алфавита: алфавит входных символов A =
{a0, a1, …, am}и алфавит состояний Q =
{q0, q1, …, qp}. (С разными машинами
Тьюринга могут быть связаны разные алфавиты A
и Q.) Состояние q0 называется пассивным.
Считается, что если машина попала в это
состояние, то она закончила свою работу.
Состояние q1 называется начальным.
Находясь в этом состоянии, машина начинает свою
работу.
Входное слово размещается на ленте по
одной букве в расположенных подряд ячейках.
Слева и справа от входного слова находятся
только пустые ячейки (в алфавит А всегда
входит пустая буква а0 — признак того, что
ячейка пуста).
Автомат может двигаться вдоль ленты
влево или вправо, читать содержимое ячеек и
записывать в ячейки буквы. Ниже схематично
нарисована машина Тьюринга, автомат которой
обозревает первую ячейку с данными.
Автомат каждый раз “видит” только
одну ячейку. В зависимости от того, какую букву ai
он видит, а также в зависимости от своего
состояния qj автомат может выполнять
следующие действия:
- · записать новую букву в обозреваемую
ячейку; - · выполнить сдвиг по ленте на одну
ячейку вправо/влево или остаться неподвижным; - · перейти в новое состояние.
То есть у машины Тьюринга есть три вида
операций. Каждый раз для очередной пары (qj,
ai) машина Тьюринга выполняет команду,
состоящую из трех операций с определенными
параметрами.
Программа для машины Тьюринга
представляет собой таблицу, в каждой клетке
которой записана команда.
Клетка (qj, ai)
определяется двумя параметрами — символом
алфавита и состоянием машины. Команда
представляет собой указание: куда передвинуть
головку чтения/записи, какой символ записать в
текущую ячейку, в какое состояние перейти машине.
Для обозначения направления движения автомата
используем одну из трех букв: “Л” (влево), “П”
(вправо) или “Н” (неподвижен).
После выполнения автоматом очередной
команды он переходит в состояние qm
(которое может в частном случае совпадать с
прежним состоянием qj). Следующую
команду нужно искать в m-й строке таблицы на
пересечении со столбцом al (букву al
автомат видит после сдвига).
Договоримся, что когда лента содержит
входное слово, то автомат находится против
какой-то ячейки в состоянии q1. В процессе
работы автомат будет перескакивать из одной
клетки программы (таблицы) в другую, пока не
дойдет до клетки, в которой записано, что автомат
должен перейти в состояние q0. Эти
клетки называются клетками останова. Дойдя
до любой такой клетки, машина Тьюринга останавливается.
Несмотря на свое простое устройство,
машина Тьюринга может выполнять все возможные
преобразования слов, реализуя тем самым все
возможные алгоритмы.
Пример. Требуется построить машину
Тьюринга, которая прибавляет единицу к числу на
ленте. Входное слово состоит из цифр целого
десятичного числа, записанных в
последовательные ячейки на ленте. В начальный
момент машина находится против самой правой
цифры числа.
Решение. Машина должна прибавить
единицу к последней цифре числа. Если последняя
цифра равна 9, то ее заменить на 0 и прибавить
единицу к предыдущей цифре. Программа для данной
машины Тьюринга может выглядеть так:
В этой машине Тьюринга q1 —
состояние изменения цифры, q0 —
состояние останова. Если в состоянии ql
автомат видит цифру 0..8, то он заменяет ее на 1..9
соответственно и переходит в состояние q0,
т.е. машина останавливается. Если же он видит
цифру 9, то заменяет ее на 0, сдвигается влево,
оставаясь в состоянии ql. Так
продолжается до тех пор, пока автомат не встретит
цифру меньше 9. Если же все цифры были равны 9, то
он заменит их нулями, запишет 0 на месте старшей
цифры, сдвинется влево и в пустой клетке запишет
1. Затем перейдет в состояние q0, т.е.
остановится.
Практические задания
1. На ленте машины Тьюринга содержится
последовательность символов “+”. Напишите
программу для машины Тьюринга, которая каждый
второй символ “+” заменит на “–”. Замена
начинается с правого конца последовательности.
Автомат в состоянии q1 обозревает один
из символов указанной последовательности. Кроме
самой программы-таблицы, описать словами, что
выполняется машиной в каждом состоянии.
2. Дано число n в восьмеричной
системе счисления. Разработать машину Тьюринга,
которая увеличивала бы заданное число n на 1.
Автомат в состоянии q1 обозревает некую
цифру входного слова. Кроме самой
программы-таблицы, описать словами, что
выполняется машиной в каждом состоянии.
3. Дана десятичная запись натурального
числа n > 1. Разработать машину Тьюринга,
которая уменьшала бы заданное число n на 1.
Автомат в состоянии q1 обозревает
правую цифру числа. Кроме самой
программы-таблицы, описать словами, что
выполняется машиной в каждом состоянии.
4. Дано натуральное число n > 1.
Разработать машину Тьюринга, которая уменьшала
бы заданное число n на 1, при этом в выходном
слове старшая цифра не должна быть 0. Например,
если входным словом было “100”, то выходным
словом должно быть “99”, а не “099”. Автомат в
состоянии q1 обозревает правую цифру
числа. Кроме самой программы-таблицы, описать
словами, что выполняется машиной в каждом
состоянии.
5. Дан массив из открывающих и
закрывающих скобок. Построить машину Тьюринга,
которая удаляла бы пары взаимных скобок, т.е.
расположенных подряд “( )”.
Например, дано “) ( ( ) ( ( )”, надо
получить “) . . . ( ( ”.
Автомат в состоянии q1
обозревает крайний левый символ строки. Кроме
самой программы-таблицы, описать словами, что
выполняется машиной в каждом состоянии.
6. Дана строка из букв “a” и “b”.
Разработать машину Тьюринга, которая переместит
все буквы “a” в левую, а буквы “b” — в
правую части строки. Автомат в состоянии q1
обозревает крайний левый символ строки. Кроме
самой программы-таблицы, описать словами, что
выполняется машиной в каждом состоянии.
7. На ленте машины Тьюринга находится
число, записанное в десятичной системе
счисления. Умножить это число на 2. Автомат в
состоянии q1 обозревает крайнюю левую
цифру числа. Кроме самой программы-таблицы,
описать словами, что выполняется машиной в
каждом состоянии.
8. Даны два натуральных числа m и n,
представленные в унарной системе счисления.
Соответствующие наборы символов “|” разделены
пустой клеткой. Автомат в состоянии q1обозревает
самый правый символ входной последовательности.
Разработать машину Тьюринга, которая на ленте
оставит сумму чисел m и n. Кроме самой
программы-таблицы, описать словами, что
выполняется машиной в каждом состоянии.
9. Даны два натуральных числа m и n,
представленных в унарной системе счисления.
Соответствующие наборы символов “|” разделены
пустой клеткой. Автомат в состоянии q1
обозревает самый правый символ входной
последовательности. Разработать машину
Тьюринга, которая на ленте оставит разность
чисел m и n. Известно, что m > n.
Кроме самой программы-таблицы, описать словами,
что выполняется машиной в каждом состоянии.
10. На ленте машины Тьюринга находится
десятичное число. Определить, делится ли это
число на 5 без остатка. Если делится, то записать
справа от числа слово “да”, иначе — “нет”.
Автомат обозревает некую цифру входного числа.
Кроме самой программы-таблицы, описать словами,
что выполняется машиной в каждом состоянии.
Решения заданий
Задача 1
В состоянии q1 машина ищет
правый конец числа, в состоянии q2 —
пропускает знак “+”, при достижении конца
последовательности — останавливается. В
состоянии q3 машина знак “+” заменяет
на знак “–”, при достижении конца
последовательности она останавливается.
Задача 2
Решение этой задачи аналогично
рассмотренному выше примеру.
Задача 3
Состояние q1 — уменьшаем
младшую (очередную) цифру на 1. Если она не равна
нулю, то после уменьшения сразу — останов, если
же младшая цифра равна 0, то вместо нее пишем 9,
смещаемся влево и вновь выполняем вычитание. В
клетку [a0, q1] машина Тьюринга
никогда не попадет, поэтому ее можно не
заполнять.
Задача 4 (усложнение задачи 3)
Состояние q1 — уменьшаем
младшую (очередную) цифру на 1. Если она больше 1,
то после уменьшения — сразу останов, если же
младшая цифра равна 0, то вместо нее пишем 9,
смещаемся влево и вновь выполняем вычитание.
Если уменьшаемая цифра равна 1, то вместо нее
пишем 0 и переходим в состояние q2.
Состояние q2 — после записи
“0” в каком-либо разряде надо проанализировать,
не является ли этот ноль старшей незначащей
цифрой (т.е. не стоит ли слева от него в записи
выходного слова a0).
Состояние q3 — если
записанный “0” является старшей незначащей
цифрой, то его надо удалить из записи выходного
слова.
Те клетки, в которые машина Тьюринга
никогда не попадает, оставляем пустыми.
Задача 5
Состояние q1: если встретили
“(”, то сдвиг вправо и переход в состояние q2;
если встретили “a0”, то останов.
Состояние q2: анализ символа
“(” на парность, в случае парности должны
увидеть “)”. Если парная, то возврат влево и
переход в состояние q3.
Состояние q3: стираем сначала
“(”, затем “)” и переходим в q1.
Задача 6
Решение этой задачи обычно вызывает у
школьников затруднение. При разборе решения этой
задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие
варианты входных слов и попросите их
сформулировать, что должна делать машина
Тьюринга, каков внешний вид выходного слова, чем
с точки зрения машины Тьюринга эти варианты
различаются:
aaa —> выходное слово совпадает с
входным, просматриваем входное слово до тех пор,
пока оно не заканчивается.
a —> выходное слово совпадает с
входным, просматриваем входное слово до тех пор,
пока оно не заканчивается.
bbb —> выходное слово совпадает с
входным, просматриваем входное слово до тех пор,
пока оно не заканчивается.
b —> выходное слово совпадает с
входным, просматриваем входное слово до тех пор,
пока оно не заканчивается.
ab —> выходное слово совпадает с
входным, просматриваем входное слово до тех пор,
пока оно не заканчивается.
Результат обсуждения. Машина
Тьюринга должна “понимать”, по цепочке каких
букв она идет, т.е. у нее должно быть как минимум
два состояния. Пусть состояние q1 —
движение по цепочке из букв “a”, а q2
— состояние движения по цепочке из букв “b”.
Заметим, что цепочка может состоять и из одной
буквы. Если мы дошли до конца строки в состоянии q1
или q2, т.е. встретили a0, машина
должна остановиться, мы обработали всю строку.
Рассмотрим следующие варианты входных
слов:
bba —> abb
bbbaab —> aabbbb
aabbbaab —> aaaabbbb
Результат обсуждения. Первый
вариант входного слова можно последовательно
обработать следующим образом: bba —> bbb
—> вернуться к левому концу цепочки из букв “b”
—> abb (заменить первую букву в этой цепочке
на “a”). Для выполнения этих действий нам
потребуется ввести два новых состояния и, кроме
того, уточнить состояние q2. Таким
образом, для решения этой задачи нам нужно
построить машину Тьюринга со следующими
состояниями:
q1 — идем вправо по цепочке
букв “a”. Если цепочка заканчивается a0,
то переходим в q0; если заканчивается
буквой “b”, то переходим в q2;
q2 — идем вправо по цепочке
букв “b”, если цепочка заканчивается a0,
то переходим в q0; если заканчивается “a”,
то заменяем букву “a” на “b”, переходим в
состояние q3 (цепочку вида 
заменили на цепочку вида 
);
q3 — идем влево по цепочке
букв “b” до ее левого конца. Если встретили a0
или “a”, то переходим в q4;
q4 — заменяем “b” на “a”
и переходим в q1 (цепочку вида заменяем на цепочку вида 
.
Задача 7
состояние q1 — поиск правой
(младшей) цифры числа;
состояние q2 — умножение
очередной цифры числа на 2 без прибавления 1
переноса;
состояние q3 — умножение
очередной цифры числа на 2 с прибавлением 1
переноса.
Задача 8
Машина Тьюринга для этой программы
выглядит тривиально просто — в ней всего одно
состояние. Такая машина Тьюринга выполняет
следующие действия: стирает самый правый штрих,
ищет разделитель (пустую ячейку) и в эту пустую
ячейку помещает штрих, тем самым сформирована
непрерывная последовательность штрихов длины n
+ m.
Однако, как ни странно, решение этой
задачи вызывает большие трудности. Очень часто
ученики строят машину Тьюринга, которая
выполняет циклические действия: последовательно
пододвигают правые n штрихов к левым.
В этом случае их программа выглядит
следующим образом:
состояние q1 — поиск
разделителя;
состояние q2 — передвинули
штрих;
состояние q3 — проверка
на конец (все ли штрихи передвинули).
На примере этой задачи четко видно, как
часто дети пытаются решить задачу уже знакомыми
способами. Мне кажется, что, предлагая ученикам
задачи на составление машин Тьюринга, мы
развиваем способность к нахождению необычных
решений, развиваем способность творчески думать!
Задача 9
Эта задача кажется школьникам
достаточно легкой, но трудности возникают с
остановом машины Тьюринга. Ниже приведен один из
возможных вариантов машины Тьюринга для этой
задачи.
Идея решения (условие останова). На
ленте есть два исходных массива штрихов.
Штрихи начинаем стирать с левого конца
массива m. И поочередно стираем самый левый
штрих в массиве m и самый правый штрих в
массиве n. Но прежде чем стереть правый штрих
в массиве n, проверяем, единственный он (т.е.
последний, который надо стереть) или нет.
Опишем сначала состояния машины
Тьюринга, которые необходимы для решения нашей
задачи, а затем составим программу-таблицу.
Состояние q1 — поиск
разделителя между массивами штрихов при
движении справа налево;
состояние q2 — поиск левого
штриха в массиве m;
состояние q3 — удаление
левого штриха в массиве m;
состояние q4 — поиск
разделителя при движении слева направо;
состояние q5 — поиск правого
штриха в массиве n;
состояние q6 — проверка
единственности этого штриха в массиве n, т.е.
определяем, был ли он последним;
состояние q7 — если он был
последним, то останов, иначе переход на новый
цикл выполнения алгоритма.
Задача 10
При решении этой задачи следует
обратить внимание на правильное выписывание
алфавита:
A = {a0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Д, А,
Н, Е, Т}.
Состояние q1 — поиск
правого конца числа;
состояние q2 — анализ
младшей цифры числа; если она равна “0” или “5”,
т.е. число делится на 5, то переход в состояние q3,
иначе переход в состояние q5;
состояние q3 — запись
буквы “Д” справа от слова на ленте;
состояние q4 — запись
буквы “А” справа от слова и останов машины;
состояние q5 — запись
буквы “Н” справа от слова;
состояние q6 — запись
буквы “Е” справа от слова;
состояние q7 — запись
буквы “Т” справа от слова и останов машины.
Свойства машины Тьюринга как
алгоритма
На примере машины Тьюринга хорошо
прослеживаются свойства алгоритмов. Попросите
учащихся показать, что машина Тьюринга обладает
всеми свойствами алгоритма.
Дискретность. Машина Тьюринга
может перейти к (к + 1)-му шагу только после
выполнения к-го шага, т.к. именно к-й шаг
определяет, каким будет (к + 1)-й шаг.
Понятность. На каждом шаге в ячейку
пишется символ из алфавита, автомат делает одно
движение (Л, П, Н), и машина Тьюринга переходит в
одно из описанных состояний.
Детерминированность. В каждой
клетке таблицы машины Тьюринга записан лишь один
вариант действия. На каждом шаге результат
определен однозначно, следовательно,
последовательность шагов решения задачи
определена однозначно, т.е. если машине Тьюринга
на вход подают одно и то же входное слово, то
выходное слово каждый раз будет одним и тем же.
Результативность. Содержательно
результаты каждого шага и всей
последовательности шагов определены однозначно,
следовательно, правильно написанная машина
Тьюринга за конечное число шагов перейдет в
состояние q0, т.е. за конечное число шагов
будет получен ответ на вопрос задачи.
Массовость. Каждая машина Тьюринга
определена над всеми допустимыми словами из
алфавита, в этом и состоит свойство массовости.
Каждая машина Тьюринга предназначена для
решения одного класса задач, т.е. для каждой
задачи пишется своя (новая) машина Тьюринга.
ОТ РЕДАКЦИИ
Все приведенные в статье задачи можно
решить просто в тетради, начертив информационную
ленту и программу-таблицу. Но можно сделать этот
процесс более увлекательным и наглядным:
воспользоваться машинной реализацией —
интерпретатором машины Поста и машины Тьюринга
“Algo2000”, созданным Радиком Зартдиновым.
Программа обладает интуитивно понятным
интерфейсом, и требования у нее самые умеренные:
компьютер IBM PC AT 486 и выше, наличие операционной
системы Windows’95/98/NT.
Посмотрим в общих чертах, как работает
“Algo2000”.
В меню программы выберем пункт Интерпретатор
и укажем, с какой машиной мы хотим работать (в
нашем случае это “машина Тьюринга”).
Перед нами появится поле машины
Тьюринга.
Теперь необходимо задать внешний
алфавит, т.е. в строке Внешний алфавит
указать, какие символы в него входят (если строка Внешний
алфавит не видна, нужно выбрать пункт меню Вид
| Внешний алфавит). Каждый символ можно указать
только один раз. После окончания ввода внешнего
алфавита формируется первый столбец таблицы: он
заполняется символами внешнего алфавита в том же
порядке. При редактировании внешнего алфавита
автоматически изменяется таблица: вставляются,
удаляются или меняются местами строки.
Не забудем, что нужно как-то расставить
символы внешнего алфавита по секциям ленты
(можно все секции оставить пустыми) и поставить
каретку против одной из секций, т.е. надо задать
программу и некоторое состояние машины.
Теперь можно приступить
непосредственно к записи алгоритма решения
задачи. Он задается в виде таблицы: в каждый
столбец верхней строчки заносятся символы
внутреннего алфавита, в каждую строчку первого
столбца — символы внешнего алфавита. В ячейках
на пересечении других столбцов и строчек
помещаются команды. Если на пересечении
какой-либо строки и какого-либо столбца мы
получим пустую клетку, то это означает, что в
данном внутреннем состоянии данный символ
встретиться не может.
Например, мы составляем алгоритм
нахождения разности двух целых положительных
чисел (в десятичной системе счисления), если
известно, что первое число больше второго, а
между ними стоит знак минус.
Поле программы будет выглядеть так:
Формат команды в каждой ячейке — aKq.
Здесь:
a — новое содержание текущей ячейки (новый символ
внешнего алфавита, который заносится в текущую
ячейку), K — команда лентопротяжного механизма
машины Тьюринга (влево, вправо, стоп), q — новое
внутреннее состояние машины Тьюринга.
Кнопка 
запустит
программу. Если выполнение не было
приостановлено, то оно всегда начинается с
нулевого внутреннего состояния Q0.
Программу можно выполнить по шагам.
Для этого нажмите на кнопку 
на панели инструментов (если
кнопки не видны, нужно выбрать пункт меню Вид |
Панель инструментов) или выберите в главном
меню Пуск | Пошагово. Если необходимо
полностью прервать выполнение программы, то это
можно сделать с помощью кнопки на панели
инструментов или с помощью главного меню (Пуск |
Прервать). Пункт меню Скорость позволяет
регулировать скорость выполнения программы.
Выполнение программы будет идти до тех
пор, пока не встретится команда “Стоп” или не
возникнет какая-нибудь ошибка.
При возникновении вопросов в ходе работы с
программой-интерпретатором обращайтесь к
справочному файлу Algo2000.hlp. Его, так же, как и
саму программу “Algo2000”, можно найти на сайте
газеты “Информатика” https://inf.1sept.ru
в разделе “Download”.
Видеоурок: Введение в алгоритмы. Машина Тьюринга
Лекция: Вычислимость. Эквивалентность алгоритмических моделей
Машина Тьюринга
Машина Тьюринга – это устройство, состоящее из центра управления, а также ряда ячеек.
Управляющее устройство данной машины имеет возможность двигаться по ряду ячеек, и считывать все значения, которые им присвоены.
Для работы машины Тьюринга написан алгоритм, который направлен на работу управляющего устройства. Данный алгоритм позволяет задавать значение той ячейки, в которой находится управляющее устройство. Так же можно задать некоторое действие устройства в данной ячейке.
Для задания значений ячейкам в машине Тьюринга используют ограниченный алфавит. А для перехода от одного значения к другому используют следующую команду:
q1a1 ->q2a2D.
Слева от команды написано состояние или значение данной ячейки в рассматриваемый момент времени, а справа значение, которое будет иметь данная ячейка после изменения свойств. D – это передвижение управляющего устройства. Если на месте данной буквы стоит L, то необходимо управляющее устройство необходимо передвинуть влево, если R – то вправо, а если N, то остаться на месте.
Машина Поста
Машина Поста очень похожа на машину Тьюринга, поскольку имеет те же возможности, однако она намного проще. Данная машина имеет бесконечный ряд ячеек, которые могут принимать значения только 1 или 0. Алгоритм данной машины прост, состоит всего из нескольких строк и имеет небольшое количество команд:
-
L – каретка машины переходит влево,
-
R – каретка машины переходит вправо,
-
1 – в ячейке, где находится каретка, ставится значение 1,
-
0 – в ячейке, где находится каретка, ставится значение 0,
-
S – машина Поста завершает свою работу,
-
? p1, p2 – если ячейка, в которой находится каретка содержит символ 0, то необходимо выполнить строку p1, если же там стоит 1, то выполняем p2.
Нормальные алгоритмы Маркова
Алгоритм Маркова позволяет изменять слова заменой их частей. Данный алгоритм имеет множество значений, а замена производится подстановкой.
С помощью специального правила над строкой выполняется ряд действий, которые приводят её к необходимому состоянию. Это возможно при ненулевой строке. Каждая новая подстановка начинается с первой возможной. Если подстановка прошла успешно, то специальное правило завершает алгоритм. Формулы для завершения алгоритма помечаются звездочкой *. Обратите внимание на то, что в данном случае звездочка не должна быть включена в алфавит. Если же необходимо использовать её для замены строк, то в качестве завершающего знака следует использовать другой символ, не входящий в алгоритм.
#статьи
- 25 янв 2023
-
0
Машина Тьюринга — что это: роскошь или средство вычисления?
Рассказываем о концепции, которая легла в основу всех современных компьютеров.
Иллюстрация: Wikimedia Commons / Colowgee для Skillbox Media
Востоковед, интересующийся IT. В прошлом редактор раздела «Системный блок» журнала «Fакел», автор журналов Computer Gaming World RE, Upgrade Special, руководитель веб-ресурсов компании 1С-Softclub.
Любой, кто интересуется информатикой, компьютерами и IT, рано или поздно встретит термин «машина Тьюринга». Понять, что это, с помощью соответствующей страницы в «Википедии» категорически невозможно, даже не пытайтесь. Поэтому мы решили справиться сами — и вам рассказать.
Всё, что нужно знать о машине Тьюринга
- Зачем она нужна
- Как устроена
- Принцип работы
- Роль в истории
- Полнота по Тьюрингу
- Примеры реализации
- При чём тут грибы?
В XVII веке знаменитый математик Готфрид Лейбниц мечтал о создании машины, которая могла бы определять истинность математических утверждений.
Три века спустя другой выдающийся математик, Давид Гильберт, мечтая о том же, сформулировал задачу. Он хотел найти алгоритм, который принимал бы в качестве входных данных описание любой проблемы разрешимости. А после конечного числа шагов останавливался бы и выдавал один из двух ответов: «истина» или «ложь».
Фото: Wikimedia Commons
Чуть позже, в 1930-е годы, к этому же вопросу обратился третий, не менее знаменитый, математик Макс Ньюман. Он преподавал в Кембридже, был криптоаналитиком и одним из создателей Colossus — самого большого компьютера тех времён.
«Есть ли конкретный метод или механический процесс, который можно применить к математическому утверждению и он ответит, доказуемо ли это утверждение?»
Из лекций Макса Ньюмана,
цитата по книге Чарльза Петцольда «Читаем Тьюринга»
Фото: Wikimedia Commons
Среди студентов Ньюмана был пока ещё никому не известный математик Алан Тьюринг. Валяясь на лугах Гранчестера, где любили отдыхать тогдашние хипстеры, он размышлял над словами Ньюмана. Итогом этих раздумий стала статья On Computable Numbers, with an Application to the Entscheidungsproblem
«Я предполагаю, что Тьюринг с самого начала своей работы ставил перед собой цель доказать неразрешимость Entscheidungsproblem. Он сказал мне, что „главная идея“ статьи пришла к нему, когда он лежал на лугах Гранчестера летом 1935 года. Главной идеей мог быть либо его анализ вычислений, либо осознание существования универсальной машины, а значит, и диагональный аргумент для доказательства неразрешимости».
Из воспоминаний ученика и друга Тьюринга Робина Ганди,
цитата по книге The Universal Turing Machine. A Half-Century Survey (1995), Rolf Herken
Фото: Christie’s
Именно в этой статье, опубликованной в 1936 году, была впервые описана машина Тьюринга. Правда, сам автор использовал понятие «вычислительная машина» (computing machine); в честь него модель назовут чуть позже.
Фото: Wikimedia Commons
Тьюринг пошёл не по привычному пути формул и доказательств, а начал с описания машины, которая совершает несколько простых операций. Хотя компьютеров тогда не было, если не считать прообразов вычислительных машин, созданных Чарльзом Бэббиджем и Вэниваром Бушем.
Машина Тьюринга — это абстрактная вычислительная машина, мысленный эксперимент для решения проблемы математической логики. Она состоит из трёх элементов:
- бесконечной ленты с ячейками;
- автомата или головки для чтения и записи;
- программы.
Изображение: Computational Error and Complexity in Science and Engineering / V. Lakshmikantham, S. K. Sen / Mathematics in Science and Engineering, 2005
Машина работает следующим образом: головка может прочитать содержимое конкретной ячейки, стереть, перезаписать и/или передвинуться на ячейку влево или вправо и повторить считывание/запись.
«В некоторых конфигурациях, в которых ячейка пуста (то есть не содержит символа), машина записывает новый символ в эту ячейку: в других конфигурациях она стирает символ. Машина может также поменять ячейку, но только путём смещения его на одно место вправо или влево».
А. Тьюринг,
«О вычислительных числах, с приложением к проблеме принятия решений»
Действия головки определяются программой. Она записывается в виде таблицы, где есть внешний и внутренний алфавиты и таблица переходов между ними. Внешний алфавит — это конечное множество, элементы которого называются буквами или символами. Внутренний алфавит — это конечное множество состояний головки. Таблица переходов описывает поведение головки. Команда, которую должна выполнить головка, определяется пересечением внешнего и внутреннего алфавитов в таблице.
На рисунке выше изображена лента, входная информация (11В) расположена так, что в каждой клетке по одному символу. До и после неё — нулевые ячейки. Исходное состояние головки — q1. Это состояние запускает работу машины. Головка может сдвинуться влево и вместо 0 записать цифру или букву. Также она может сдвинуться вправо и перезаписать 1 другой цифрой или буквой. Или передвинуться ещё на ячейку влево/вправо без перезаписи.
Головка может также остаться на месте и ничего не делать. Выполнение операций прекращается после того, как головка считывает пассивное состояние — q0.
В чём же важность этой, на первый взгляд, нехитрой конструкции?
Историческое значение машины Тьюринга в том, что это первая математическая модель универсальных вычислений. Другими словами, всё, что можно вычислить, описывается как машина Тьюринга. Это не единственная модель вычислений, но, пожалуй, самая известная и популярная. И ещё это описание работы компьютера, которое Тьюринг дал до появления компьютеров.
«Его машины предлагали мост, связь между абстрактными символами и физическим миром».
Эндрю Ходжес,
«Алан Тьюринг: Энигма»
Также новаторство Тьюринга было в том, что его машина использовала двоичную систему во времена, когда преобладала десятичная. Привычные для нас двоичные числа для большинства читателей в 1936 году были не столь знакомы. Так, компьютер ENIAC (1943–1945) использовал десятичную систему. А слово «бит» (сокращение от binary digit, «двоичная цифра») появилось в публикациях только в 1948 году.
Важность работы Тьюринга была ещё и в том, что он описал универсальный компьютер «общего назначения». Это революционная концепция. В то время компьютеры разрабатывались специально для определённых видов работ. Например, Вэнивар Буш со студентами в 1920-е годы придумал аналоговый компьютер, известный как дифференциальный анализатор. Он решал обыкновенные дифференциальные уравнения — и это было всё, что он делал.
«Не нужно разрабатывать разные машины для выполнения различных вычислительных процессов. Все они могут быть выполнены с помощью одного цифрового компьютера, соответствующим образом запрограммированного для каждого случая».
А.Тьюринг,
«Вычислительная техника и интеллект»
Никто не доказал, что существует более эффективная модель вычислений, чем машина Тьюринга. Она отвечает на вопрос, какие минимальные условия нам нужны для выполнения любого вычисления. Ответ на этот вопрос показывает нам ограничения компьютеров. Если мы можем произвести определённое вычисление на машине Тьюринга, значит, его можно сделать на любом другом компьютере. Это называется «полнота по Тьюрингу».
Полнота по Тьюрингу — одно из базовых понятий в информатике. Полный по Тьюрингу язык программирования или компьютер способен имитировать машину Тьюринга. Он теоретически может выразить все задачи, решаемые компьютерами; почти все языки программирования Тьюринг-полные, если не обращать внимания на ограничения памяти.
Другими словами, можно написать на Java или C++ программу, которая будет действовать как машина Тьюринга. «Полными» также являются и HTML5, и CSS3. А вот SQL не полный — на нём пишутся в основном запросы к базе данных, а не полноценные программы.
Несмотря на то что данная разработка — это мысленный эксперимент, нашлись энтузиасты, которые попытались сконструировать её физический прототип.
Пожалуй, наиболее впечатляющую модель воспроизвел Ричард Ридел. У него ушло на её создание шесть месяцев.
Фото: Wikimedia Commons
Другие умельцы реализовали машину Тьюринга в Excel:
Несмотря на то что машина Тьюринга была придумана почти 100 лет назад, эта концепция не только не устарела, но и используется сейчас. Робототехник Джошуа Бонгард и биолог Майкл Левин в своих работах предлагают уйти от узкого понимания компьютеров и рассматривать живые организмы тоже как вычислительные машины.
И для того, чтобы определить, можно ли причислить этих крабов к компьютерам, они рассматривают их как машину Тьюринга. Правда, здесь у учёных возникают сложности, потому что в случае с грибами или жидкостями сложно определить, где лента, где считывающая головка, а где программа.
Кроме того, биологические системы эволюционируют и меняются со временем, что также усложняет применение к ним жёстких математических определений.
Но ничего лучше машины Тьюринга, похоже, не придумали, поэтому Бонгарду и Левину придётся найти, где у крабов лента, а где считывающая головка.
Высшее образование со Skillbox
Программа бакалавриата по аналитике данных и машинному обучению от РАНХиГС. Стань востребованным IT-специалистом, получи диплом государственного вуза и измени мир с помощью высоких технологий.
Узнать подробнее
Учись бесплатно:
вебинары по программированию, маркетингу и дизайну.
Участвовать
Машина Тьюринга
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Что собой представляет машина Тьюринга?
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
- Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
- Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
- Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Передвигаться на одну ячейку влево или вправо.
- Менять свое внутреннее состояние.
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Пример работы машины Тьюринга
Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).
Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):
Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние q2 (команды которого совпадают с командами q1 предыдущей программы).
|
Решение задач Машина Тьюринга |
Задание
1
Написать
программу на машине Тьюринга, прибавляющую число 2 к введенному числу.
Решение
Задание
2
Написать на
машине Тьюринга программу, прибавляющую 3 к введенному числу.
Решение
Задание
3
Перенести
первый символ непустого слова P в его конец. Алфавит: A={a,b,c}.
Решение
Если первый символ
– это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает
в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где
делается всё то же самое, только в конце записывается символ b. Если же первым
был символ c, тогда переходим в состояние q4, в котором автомат дописывает за
входным словом символ c.
Задание
4
Если первый и
последний символы (непустого) слова P одинаковы, тогда это слово не менять, а
иначе заменить его пустым словом. Алфавит: A={a,b,c}.
Решение
Для решения этой
задачи предлагается выполнить следующие действия:
1. Запомнить
первый символ входного слова, не стирая его (перейти в состояние q1, если первый
символ – a, q3, если первый
символ – b и q5, если первый
символ – c).
2. Переместить
автомат под последний символ и сравнить его с запомненным (в q2 для a, в q4 для b и в q6 для c). Если они равны,
то больше ничего не делать.
3. В противном
случае уничтожить всё входное слово (q7).
Задание 5
Удалить из
слова P его второй
символ, если такой есть. Алфавит: A={a,b}.
Решение
Запомнить
первый символ, стереть второй символ и установить на его месте первый.
Задание
6
Удалить из
слова P первое
вхождение символа a, если такое
есть. Алфавит:
A={a,b,c}.
Решение
Если первый
символ слова – a, то стереть
его и остановиться. Иначе сдвигаем символы слова на один символ вправо до тех
пор, пока не найдем символ a.
Сдвиг
символов осуществляется так: в очередной клетке записываем b (если в q1) или c (если в q2), переходим вправо и
меняем состояние на q1 (если в
текущей клетке было записано b)
или на q2 (если было
записано c), где
осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то
записываем в нее запомненный символ и останавливаем программу.
Задание
7
Если P — непустое
слово, то за его первым символом вставить символ a. Алфавит: A={a,b,c}.
Решение
Аналогично
заданию 5 запоминаем первый символ слова, меняем его на символ a, переходим на
одну клетку влево и ставим там этот символ.
Задание
8
Вставить в
слово P символ a за первым символом c, если такое есть.
Алфавит: A={a,b,c}.
Решение
Просматриваем
слово до символа c или пустой
клетки (в последнем случае останавливаем программу сразу). Затем, если c найден, запоминаем
его и меняем на символ a, а далее
запускаем цикл, который справа налево сдвигает символы слова, первоначально
вставляя символ c перед a.
Задание
9
Удалить из P все
вхождения символа a. A={a,b,c}.
Решение
Вместо сдвига
символов слова для закрытия образующихся дырок можно построить новое слово
справа от предыдущего. Чтобы разграничить эти слова, отделим их некоторым
вспомогательным символом, например знаком =, отличным от всех
символов алфавита A.
1. Идем в конец
слова и ставим знак =.
2. После этого
возвращаемся к началу входного слова.
3. Теперь наша
задача – перенести в цикле все символы входного слова, кроме a, вправо за знак = в
формируемое выходное слово. Для этого анализируем первый символ входного слова.
Если это a, тогда стираем
его и переходим к следующему символу. Если же первый символ – это b или c, тогда
стираем его и «бежим» вправо до первой пустой клетки, куда и записываем этот
символ. Снова возвращаемся налево к тому символу, который стал первым во
входном слове, и повторяем те же самые действия, но уже по отношению к этому
символу.
4. Этот цикл
завершается, когда при возврате налево мы увидим в качестве первого символа
знак =. Это признак
того, что мы полностью просмотрели входное слово и перенесли все его символы,
отличные от a, в
формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо
под выходное слово и остановиться.
Задание
10
Удвоить слово
P, поставив
между ним и его копией знак =. Алфавит: A={a,b}.
Решение
1. Вначале
записываем знак = за входным
словом. Затем возвращаемся под первый символ входного слова.
2. Далее
заменяем видимый символ a на двойник A (чтобы при
возвращении к исходному слову знать, с какого символа продолжать копирование),
«бежим» вправо до первой свободной клетки и записываем в неё символ a. После этого
возвращаемся влево к клетке с двойником A, восстанавливаем прежний символ a и сдвигаемся
вправо к следующему символу. Теперь аналогичным образом копируем второй символ
(заменяем его на A, в конец
дописываем a и т.д.) и
все последующие символы входного слова.
3. Когда мы
скопируем последний символ входного слова и вернёмся к его двойнику, то затем
после сдвига на одну позицию вправо мы попадём на знак =. Это сигнал о том,
что входное слово полностью скопировано, поэтому останавливаем программу.
Урок информатики по теме «Машина Тьюринга»
Аннотация:
Презентация по информатике на тему «Машина Тьюринга”, изучаемая в 10-ом классе в рамках темы «Алгоритм. Исполнители алгоритма». В конце предлагается пройти тест на проверку теоретических знаний по данной теме.
Целевая аудитория: для 10 класса
Автор: Хуснутдинова Резида Рашитовна
Место работы: МАОУ «Гимназия №37»
Добавил: RezedaH
Уважаемые коллеги! Автор ждёт Ваши отзывы! Оставьте своё мнение о разработке!
Всего комментариев: 1
Порядок вывода комментариев:
Физкультминутки
Физкультминутки обеспечивают кратковременный отдых детей на уроке, а также способствуют переключению внимания с одного вида деятельности на другой.
В помощь учителю
Уважаемые коллеги! Добавьте свою презентацию на Учительский портал и получите бесплатное свидетельство о публикации методического материала в международном СМИ.
Для добавления презентации на портал необходимо зарегистрироваться.
Конкурсы
Диплом и справка о публикации каждому участнику!
© 2007 — 2023 Сообщество учителей-предметников «Учительский портал»
Свидетельство о регистрации СМИ: Эл № ФС77-64383 выдано 31.12.2015 г. Роскомнадзором.
Территория распространения: Российская Федерация, зарубежные страны.
Учредитель / главный редактор: Никитенко Е.И.
Сайт является информационным посредником и предоставляет возможность пользователям размещать свои материалы на его страницах.
Публикуя материалы на сайте, пользователи берут на себя всю ответственность за содержание этих материалов и разрешение любых спорных вопросов с третьими лицами.
При этом администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта.
Если вы обнаружили, что на сайте незаконно используются материалы, сообщите администратору через форму обратной связи — материалы будут удалены.
Все материалы, размещенные на сайте, созданы пользователями сайта и представлены исключительно в ознакомительных целях. Использование материалов сайта возможно только с разрешения администрации портала.
Фотографии предоставлены 