Решение
Построим сам граф. Столбцы – вершины графа, строки – его рёбра. Если ребро инцидентно вершине, то клетка будет закрашена. Получим:
Составим остовное дерево для данного графа. Остовное дерево графа – это подграф графа, состоящий из всех вершин графа и минимального числа рёбер так, чтобы из любой вершины можно добраться в любую. Сначал включаем в оствное дерево ребро 
Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также оставляем. Ребро 
добавляет к остовному дереву вершину 
, его также оставляем. Ребро 
не добавляет к остовному дереву новых вершин, поэтому его в остовное дерево не включаем. Ребро 
добавляет к остовному дереву вершину 
, поэтому его также включаем. В остовное дерево включены все вершины графа, поэтому остовное дерево построено.
4. А) Написать таблицу состояний данного автомата.
б) Считая автомат неинициальным, построить эквивалентный автомат Мура. Проверить работу данного и построенного автоматов над одним и тем же словом.
Регулярные грамматики и конечные автоматы
Регулярные грамматики — это грамматики, которые способны точно определить каждый регулярный язык, и по этой причине являются эквивалентными конечному автомату и регулярным выражениям.
Регулярные грамматики способны точно определить каждый регулярный язык, и поэтому являются эквивалентными конечному автомату и регулярным выражениям. Регулярные грамматики выступают как подмножества контекстно-свободных грамматик. Регулярная грамматика может задаваться совокупностью правил в качестве левой или правой регулярной грамматики.
В правой регулярной грамматике весь набор правила может быть в одном из следующих форматов:
- A → a
- A → aB
- A → ε
В левой регулярной грамматике весь набор правил может быть в одном из следующих форматов:
- A → a
- A → Ba
- A → ε
- Большие буквы (A, B) призваны обозначить не терминалы из множества N.
- Строчные буквы (a, b) служат для обозначения терминалов из множества Σ.
- ε должен обозначать пустую строку, то есть строку, имеющую длину нуль.
Класс правой и левой регулярной грамматики считаются эквивалентными, поскольку каждый класс в отдельности является достаточным, чтобы задать все регулярные языки. Каждую регулярную грамматику можно преобразовать из левой регулярной грамматики в правую, и наоборот.
Все контекстно-свободные грамматики могут быть легко преобразованы в вид, в котором присутствуют только правила из лево-регулярной или право-регулярной грамматики. Причём для контекстно-свободной грамматики допускается наличие тех и других грамматик одновременно. Отсюда следует вывод, что такие грамматики способны отобразить каждый из контекстно-свободных языков. Регулярные грамматики способны обладать или лево-регулярными правилами, или право-регулярными правилами, но никак не обоими типами одновременно. То есть, они способны описать только подмножество языков, именуемых регулярными языками.
Регулярные грамматики и конечные автоматы
Конечным автоматом является определённое устройство, которое обладает конечным числом состояний и предназначено для прочтения слов заданного конечного алфавита. По умолчанию считается, что слово занесено на некоторую ленту, составленную из ячеек, в каждую из которых занесена одна буква алфавита. Чтение ленты выполняется в дискретные такты времени в направлении слева направо. Подразумевается, что считывание произвольного слова «a» автомат должен начинать из специально заданного начального состояния. Считывание очередного символа в текущем такте времени должно сопровождаться перемещением вправо к прочтению следующего символа и изменением текущего состояния, которое должно определяться считанной в текущем такте буквой и состоянием, в котором автомат находится в текущем такте. Слово, имеющее длину l, автомат обрабатывает в течение l тактов. Итог прочтения слова «а» должен определяться состоянием, в котором автомат может оказаться после завершения обработки данного слова.
Приведённое в словесной форме описание конечного автомата и его функционирования можно заменить при помощи следующего формального определения. Конечный автомат К * может быть определён с помощью следующего выражения:
- А = <а1, а2, . an>является входным алфавитом.
- Q =
- q0 является выделенным начальным состоянием автомата.
- g является функцией переходов, определенной на множестве QxA = <(qi, 0)\i=l. m; j=1. n>и принимающей значения из множества Q (когда g(qi,aj) = qk, то это значит, что конечный автомат, который находился в состоянии qi , после прочтения буквы aj перешёл в состояние qk).
- F является выделенным подмножеством (Fc Q), то подмножеством «хороших» состояний автомата.
Работа конечного автомата «К» по чтению входного слова а = ai1, ai2,…aip может быть представлена следующим образом. Пусть qa(t) будет обозначать состояние, в котором окажется автомат «К» после t тактов обработки текущего слова (здесь t=0,1,2. р):
- qa (0) = qо (перед началом работы автомат находился в состоянии q0), qa(1) = g(qa(0), ai.1) (прочитав первую букву, автомат переходит в состояние q« (1)).
- qа (2) = g (q a(1), ai2) (прочитав вторую букву, автомат переходит из состояния qa (1) в состояние qа (2)).
- qа(Р) = g(qа(Р — 1), aip) (прочитав все слово, автомат переходит из состояния qa(p-1) в состояние qа (Р)).
Считается, что слово «а» принято автоматом «К», если qa(p)ϵF , то есть после прочтения всего слова автомат должен находиться в одном из «хороших» состояний.
Пусть L(K) является совокупностью слов, которые принимает автоматом К. Совокупность L(K) именуется языком, который способен распознать данный конечный автомат «К». Язык L считается регулярным, если он может быть распознан некоторым конечным автоматом.
Конечный автомат, определяемый выражением:
Может быть удобно задан специальной диаграммой переходов. Диаграмма переходов является ориентированным графом, множество вершин которого совпадает с множеством состояний Q=
На рисунке ниже изображена диаграмма автомата K1, работающего над словами алфавита A=
Рисунок 1. Диаграмма автомата K1. Автор24 — интернет-биржа студенческих работ
Автомат имеет два состояния, q0 и q1, причем «хорошим» считается лишь состояние q1.
Начав работу в состоянии q0, автомат под влиянием символов a, b из этого состояния не может выйти, а под влиянием символа «с» реализуется переход в состояние q1. Далее любой поступающий символ (буква) оставляет автомат в том же состоянии. Это означает, что автомат K1 распознает язык L1, который состоит из слов, имеющих в своем составе букву «с». Этот язык может считаться регулярным.
Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2
Статья написана, собрана и сверстана Brotherofken. Спасибо ему огромное.
В предыдущей статье я попытался изложить все основные определения и принципы, чтобы сделать эту статью максимально понятной. Все не уместилось, так что я настоятельно советую ознакомиться с этими файлами:
Базис, Базис2, Минимизация. Далее в этой статье я оставил несколько разъясняющих пометок курсивом.
В этой статье я попробую объяснить доступным языком что такое абстрактный автомат, способы его представления. Так как теория автоматов полна математики и сложна, постараюсь писать человеческим языком, чтобы неподготовленный читатель смог понять о чём идёт речь.
- Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
- Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.
Абстрактный автомат
Автомат должен будет реализовывать некоторые функции, которые заданы разработчиком. Он может быть простым сумматором, может реализовывать какую-либо микрокоманду процессора, выбирать слова из оперативной памяти или заниматься синтаксическим анализом выражения.
В общем виде, не вдаваясь в подробности, абстрактный автомат можно представить следующим образом: 
Или, если перейти от иллюстрации к математическому описанию:
A = <A, B, C, δ, λ>
- Множество – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.
- Множество – представляет собой множество значений на физических выходах автомата.
- Множество
– а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата. - δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.
- λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.
Такой автомат функционирует дискретно по времени, то есть значения входов, выходов и внутреннее состояние автомата изменяются в дискретные моменты времени.
Итак мы в общем виде описали что есть Абстрактный автомат. Примером такого автомата может быть триггер, регистр ЭВМ или сумматор.
- Автоматы Мили. Описывается системой уравнений:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t-1) ). - Автоматы Мура. Описывается уравнениями:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t) ).
Т.е. автомат типа Мили вырабатывает выходной сигнал когда у него меняется входной, в зависимости от его предыдущего состояния. При этом длительность выходного сигнала не зависит от длительности входного, а только от его присутствия. В автоматах типа Мура выходной сигнал зависит от состояния автомата в текущий момент времени т.е. автомат будет вырабатывать определенный выходной сигнал пока не изменит свое состояние.
Способы задания автоматов
Как мы выяснили в первой части — автомат представляет собой совокупность входного и выходного алфавитов, множества внутренних состояний и функций, определяющих переходы и выходы. Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому.
- При помощи графов.
- При помощи таблиц переходов и выходов.
Графы
Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.
Для графа Мили на дугах указываются сходные и выходные буквы. Выходные буквы пишутся над дугами, символизируя то, что выходное состояние зависит от состояния автомата в предыдущий момент времени.
Для графа автомата Мура на дугах записываются только входные буквы, выходные же указываются около вершин.
Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным. Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным, а автомат Мура – частичным.
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.
На этом о графах всё.
Таблицы переходов и выходов.
Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.
ТПВ графа Мили
В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3. 
ТПВ графа Мура
Для графа Мура строят отмеченную таблицу переходов. Выделяется дополнительный столбец для выходных букв.
В клетке под входной буквой пишется в какое состояние автомат переходит, в крайней правой клетке — какую выходную букву возвращает. 
Пример синтеза автомата
При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат?
Чтобы задать граф нужно словесное описание алгоритма работы триггера. Читаем:
Кодируем входной и выходной алфавиты:
A =
B =
Строим граф автомата Мили: 
Вот такая забавная чебурашка получилась :-). Теперь можно построить таблицу переходов и выходов: 
Если расписать эту таблицу преобразовав условные обозначения в фактические, то получим таблицу которая представляет из себя таблицу переходов триггера. Затем её можно упростить: 
Нанесём полученную функцию на карту Вейча и минимизируем:
Выпишем, что получилось: 
Строим по функции схему (Выполняли домашнее задание?):
Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём: 
А на схеме асинхронный RS триггер обозначается вот так:
Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.
Name already in use
automata_programming / 03.Turing_Machine / 03.Turing_Machine.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Абстрактные вычислительные машины
Материал взят с ресурса Планета информатики
Машина Тьюринга — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
То есть, всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
- Внешний алфавит. Конечное множество (например, А ), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, Q0 ) должна представлять собой пустой символ.
- Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, Q1 ) должно быть начальным (запускающим программу). Еще одно из состояний ( Q0 ) должно быть конечным (завершающим программу) – состояние останова.
- Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Передвигаться на одну ячейку влево или вправо.
- Менять свое внутреннее состояние.
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Пример работы машины Тьюринга Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0 . Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова. Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).
Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):
Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние Q2 (команды которого совпадают с командами Q1 предыдущей программы).
Материал взят с ресурса Планета информатики
На ленте машины Тьюринга содержится последовательность символов + . Напишите программу для машины Тьюринга, которая каждый второй символ + заменит на — . Замена начинается с правого конца последовательности. Автомат в состоянии Q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1 . Автомат в состоянии Q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Дана десятичная запись натурального числа n > 1 . Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1 . Автомат в состоянии Q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Дано натуральное число n > 1 . Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1 , при этом в выходном слове старшая цифра не должна быть 0 . Например, если входным словом было 100 , то выходным словом должно быть 99 , а не 099 . Автомат в состоянии Q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд ( ) . Например, дано ) ( ( ) ( ( ) , надо получить ) . . . ( ( . Автомат в состоянии Q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Дана строка из букв a и b . Разработать машину Тьюринга, которая переместит все буквы a в левую, а буквы b — в правую части строки. Автомат в состоянии Q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2 . Автомат в состоянии Q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Даны два натуральных числа m и n , представленные в унарной системе счисления. Соответствующие наборы символов | разделены пустой клеткой. Автомат в состоянии Q1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n . Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Даны два натуральных числа m и n , представленных в унарной системе счисления. Соответствующие наборы символов | разделены пустой клеткой. Автомат в состоянии Q1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит разность чисел m и n . Известно, что m > n . Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово да , иначе — нет . Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
В состоянии Q1 машина ищет правый конец числа, в состоянии Q2 — пропускает знак + , при достижении конца последовательности — останавливается. В состоянии Q3 машина знак + заменяет на знак — , при достижении конца последовательности она останавливается.
Решение этой задачи аналогично рассмотренному выше примеру.
Состояние Q1 — уменьшаем младшую (очередную) цифру на 1 . Если она не равна нулю, то после уменьшения сразу — останов, если же младшая цифра равна 0 , то вместо нее пишем 9 , смещаемся влево и вновь выполняем вычитание. В клетку [ A0 , Q1 ] машина Тьюринга никогда не попадет, поэтому ее можно не заполнять.
Задача 4 (усложнение задачи 3)
Состояние Q1 — уменьшаем младшую (очередную) цифру на 1 . Если она больше 1 , то после уменьшения — сразу останов, если же младшая цифра равна 0 , то вместо нее пишем 9 , смещаемся влево и вновь выполняем вычитание. Если уменьшаемая цифра равна 1 , то вместо нее пишем 0 и переходим в состояние Q2 .
Состояние Q2 — после записи 0 в каком-либо разряде надо проанализировать, не является ли этот ноль старшей незначащей цифрой (т.е. не стоит ли слева от него в записи выходного слова A0 ).
Состояние Q3 — если записанный 0 является старшей незначащей цифрой, то его надо удалить из записи выходного слова.
Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.
Состояние Q1 : если встретили ( , то сдвиг вправо и переход в состояние Q2 ; если встретили A0 , то останов.
Состояние Q2 : анализ символа ( на парность, в случае парности должны увидеть ). Если парная, то возврат влево и переход в состояние Q3 .
Состояние Q3 : стираем сначала ( , затем ) и переходим в Q1 .
Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:
aaa -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
a -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
bbb -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
b -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
ab -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
Результат обсуждения. Машина Тьюринга должна «понимать», по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние Q1 — движение по цепочке из букв a , а Q2 — состояние движения по цепочке из букв b . Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии Q1 или Q2 , т.е. встретили A0 , машина должна остановиться, мы обработали всю строку.
Рассмотрим следующие варианты входных слов:
Результат обсуждения. Первый вариант входного слова можно последовательно обработать следующим образом: 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 (цепочку вида заменяем на цепочку вида .
состояние Q1 — поиск правой (младшей) цифры числа;
состояние Q2 — умножение очередной цифры числа на 2 без прибавления 1 переноса;
состояние Q3 — умножение очередной цифры числа на 2 с прибавлением 1 переноса.
Машина Тьюринга для этой программы выглядит тривиально просто — в ней всего одно состояние. Такая машина Тьюринга выполняет следующие действия: стирает самый правый штрих, ищет разделитель (пустую ячейку) и в эту пустую ячейку помещает штрих, тем самым сформирована непрерывная последовательность штрихов длины n + m .
Однако, как ни странно, решение этой задачи вызывает большие трудности. Очень часто ученики строят машину Тьюринга, которая выполняет циклические действия: последовательно пододвигают правые n штрихов к левым.
В этом случае их программа выглядит следующим образом:
состояние Q1 — поиск разделителя;
состояние Q2 — передвинули штрих;
состояние Q3 — проверка на конец (все ли штрихи передвинули).
На примере этой задачи четко видно, как часто дети пытаются решить задачу уже знакомыми способами. Мне кажется, что, предлагая ученикам задачи на составление машин Тьюринга, мы развиваем способность к нахождению необычных решений, развиваем способность творчески думать!
Эта задача кажется школьникам достаточно легкой, но трудности возникают с остановом машины Тьюринга. Ниже приведен один из возможных вариантов машины Тьюринга для этой задачи.
Идея решения (условие останова). На ленте есть два исходных массива штрихов.
Штрихи начинаем стирать с левого конца массива m . И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n . Но прежде чем стереть правый штрих в массиве n , проверяем, единственный он (т.е. последний, который надо стереть) или нет.
Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу.
Состояние Q1 — поиск разделителя между массивами штрихов при движении справа налево;
состояние Q2 — поиск левого штриха в массиве m ;
состояние Q3 — удаление левого штриха в массиве m ;
состояние Q4 — поиск разделителя при движении слева направо;
состояние Q5 — поиск правого штриха в массиве n ;
состояние Q6 — проверка единственности этого штриха в массиве n , т.е. определяем, был ли он последним;
состояние Q7 — если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.
При решении этой задачи следует обратить внимание на правильное выписывание алфавита:
Состояние Q1 — поиск правого конца числа;
состояние Q2 — анализ младшей цифры числа; если она равна 0 или 5 , т.е. число делится на 5 , то переход в состояние Q3 , иначе переход в состояние Q5 ;
состояние Q3 — запись буквы Д справа от слова на ленте;
состояние Q4 — запись буквы А справа от слова и останов машины;
состояние Q5 — запись буквы Н справа от слова;
состояние Q6 — запись буквы Е справа от слова;
состояние Q7 — запись буквы Т справа от слова и останов машины.
Машина Поста — абстрактная вычислительная машина, предложенная Эмилем Постом в 1936 году, создана независимо от машины Тьюринга, но сообщение о машине Поста опубликовано на несколько месяцев позднее. Отличается от машины Тьюринга большей простотой, при том обе машины алгоритмически «эквивалентны» и обе разработаны для формализации понятия алгоритма и решения задач об алгоритмической разрешимости, то есть, демонстрации алгоритмического решения задач в форме последовательности команд для машины Поста.
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты. Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0 , либо помеченной меткой 1 . За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
где i — номер команды, K — действие каретки, j — номер следующей команды (отсылка). Всего для машины Поста существует шесть типов команд:
- V j — поставить метку, перейти к j -й строке программы;
- X j — стереть метку, перейти к j -й строке;
- <- j — сдвинуться влево, перейти к j -й строке;
- -> j — сдвинуться вправо, перейти к j -й строке;
- ? j1; j2 — если в ячейке нет метки, то перейти к J1 -й строке программы, иначе перейти к J2 -й строке;
- ! — конец программы («стоп», останов). В команде «стоп» переход на следующую строку не указывается.
После программы запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой «стоп»;
- работа никогда не закончится.
Для сложения и вычитания натуральных (целых неотрицательных) чисел P и Q их можно представить на ленте набором из P единиц и Q , отделённых друг от друга одним нулём; пусть исходное положение каретки находится на крайней левой 1 группы единиц Q :
Сложение двух чисел тривиально — достаточно поставить 1 между числами и стереть одно крайнее правое 1 у представления Q .
Программа вычитания таких чисел состоит из последовательного изменения крайних левых 1 у представления Q и правых 1 у представления P . В начале программы каретка установлена на крайнюю левую 1 у Q :