Как сделать стоп в машине тьюринга

Обновлено: 02.07.2024

Аннотация: Посвящена простой классической вычислительной модели (описанию) алгоритма (алгоритмизируемого процесса) – машине А.Тьюринга, проблеме остановки такой машины (завершаемости такого процесса) и связям этой проблемы с классической алгоритмической проблемой равенства слов в свободных полугруппах.

Зачем нужны простые вычислительные модели?

До сих пор нам было удобно ссылаться на программистский опыт , говоря об алгоритмах, программах, интерпретаторах, пошаговом выполнении и т.д. Это позволяло нам игнорировать детали построения тех или иных алгоритмов под тем предлогом, что читатель их легко восстановит (или хотя бы поверит все-таки не каждый читатель в своей жизни писал интерпретатор паскаля на паскале).

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

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

Другая причина, по которой важны простые вычислительные модели (таких моделей много разные виды машин Тьюринга, адресные машины и т.п.), связана с теорией сложности вычислений, когда нас начинает интересовать время выполнения программ. Но этот вопрос выходит за рамки классической теории алгоритмов.

Машины Тьюринга: определение

Машина Тьюринга имеет бесконечную в обе стороны ленту, разделенную на квадратики ( ячейки ). В каждой ячейке может быть записан некоторый символ из фиксированного (для данной машины) конечного множества , называемого алфавитом данной машины. Один из символов алфавита выделен и называется " пробелом" предполагается, что изначально вся лента пуста, то есть заполнена пробелами.

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

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

произвольное конечное множество A ( алфавит ); его элементы называются символами ;
некоторый выделенный символ \in A" />
( пробел, или пустой символ );
конечное множество S , называемое множеством состояний ;
некоторое выделенное состояние \in S" />
, называемое начальным ;
таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа (см. ниже);
некоторое подмножество , элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

Таблица переходов устроена следующим образом: для каждой пары указана тройка . Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A -> S x A x , определенная на тех парах, в которых состояние не является заключительным.

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

Машины Тьюринга: обсуждение

Разумеется, наше определение содержит много конкретных деталей, которые можно было бы изменить. Например, лента может быть бесконечной только в одну сторону. Можно придать машине две ленты. Можно считать, что машина может либо написать новый символ, либо сдвинуться, но не то и другое вместе. Можно ограничить алфавит , считая, скажем, что в нем должно быть ровно 10 символов. Можно потребовать, чтобы в конце на ленте ничего не было, кроме результата работы (остальные клетки должны быть пусты). Все перечисленные и многие другие изменения не меняют класса вычислимых на машинах Тьюринга функций. Конечно, есть и небезобидные изменения. Например, если запретить машине двигаться налево, то это радикально поменяет дело по существу лента станет бесполезной, так как к старым записям уже нельзя будет вернуться.

Как понять, какие изменения безобидны, а какие нет? Видимо, тут необходим некоторый опыт практического программирования на машинах Тьюринга, хотя бы небольшой. После этого уже можно представлять себе возможности машины, не выписывая программы полностью, а руководствуясь лишь приблизительным описанием. В качестве примера опишем машину, которая удваивает входное слово (изготавливает слово XX , если на входе было слово X ).

Если машина видит пробел ( входное слово пусто), она кончает работу. Если нет, она запоминает текущий символ и ставит пометку (в алфавите помимо символов 0 и 1 будут еще их " помеченные варианты" и ). Затем она движется направо до пустой клетки, после чего пишет там копию запомненного символа. Затем она движется налево до пометки; уткнувшись в пометку, отходит назад и запоминает следующий символ и так далее, пока не скопирует все слово .

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

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

Другой пример неформального рассуждения: объясним, почему можно не использовать дополнительных символов, кроме 0 , 1 и пустого символа. Пусть есть машина с большим алфавитом из N символов. Построим новую машину, которая будет моделировать работу старой, но каждой клетке старой будет соответствовать блок из k клеток новой. Размер блока (число k ) будет фиксирован так, чтобы внутри блока можно было бы закодировать нулями и единицами все символы большого алфавита. Исходные символы 0 , 1 и пустой будем кодировать как 0 , за которым идут (k-1) пустых символов, 1 , за которым идут (k-1) пустых символов, и группу из k пустых символов. Для начала надо раздвинуть буквы входного слова на расстояние k , что можно сделать без дополнительных символов (дойдя до крайней буквы, отодвигаем ее, затем дойдя до следующей, отодвигаем ее и крайнюю и так далее); надо только понимать, что можно идентифицировать конец слова как позицию, за которой следует более k пустых символов. Ясно, что в этом процессе мы должны хранить в памяти некоторый конечный объем информации, так что это возможно. После этого уже можно моделировать работу исходной машины по шагам, и для этого тоже достаточно конечной памяти (е конечного числа состояний), так как нам важна только небольшая окрестность головки моделируемой машины. Наконец, надо сжать результат обратно.

Утверждение о том, что всякая вычислимая функция вычислима на машине Тьюринга, называют тезисом Тьюринга. Конечно, его смысл зависит от того, что понимать под словами " вычислимая функция ". Если понимать их в расплывчато-интуитивном смысле (" функция вычисляется алгоритмически, то есть по четким, недвусмысленным, однозначным правилам" или что-то в таком роде), конечно, ни о каком доказательстве тезиса Тьюринга не может быть речи. Можно лишь говорить, что многовековая практика человечества от Евклида до Кнута не встретилась с примером алгоритма, который нельзя было бы записать как программу машины Тьюринга и т.п. Впрочем, еще один (не слишком убедительный) аргумент приведен ниже.

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

В заключение обсуждения приведем обещанный выше аргумент в пользу того, что любая вычислимая функция вычислима на машине Тьюринга. Пусть есть функция , которую человек умеет вычислять. При этом, он, естественно, должен использовать карандаш и бумагу, так как количество информации , которое он может хранить " в уме", ограничено. Будем считать, что он пишет на отдельных листах бумаги. Помимо текущего листа, есть стопка бумаг справа и стопка слева; в любую из них можно положить текущий лист , завершив с ним работу, а из другой стопки взять следующий. У человека есть карандаш и ластик. Поскольку очень мелкие буквы не видны, число отчетливо различимых состояний листа конечно, и можно считать, что в каждый момент на листе записана одна буква из некоторого конечного (хотя и весьма большого) алфавита. Человек тоже имеет конечную память , так что его состояние есть элемент некоторого конечного множества . При этом можно составить некоторую таблицу, в которой записано, чем кончится его работа над листом с данным содержимым, начатая в данном состоянии (что будет на листе, в каком состоянии будет человек и из какой пачки будет взят следующий лист ). Теперь уже видно, что действия человека как раз соответствуют работе машины Тьюринга с большим (но конечным) алфавитом и большим (но конечным) числом внутренних состояний.

Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического устройства (рис. 2.6).

Лента выступает в качестве внешней памяти; она считается неограниченной (бесконечной) - уже это свидетельствует о том, что машина Тьюринга является модельным устройством, поскольку ни одно реальное устройство не может обладать памятью бесконечного размера.

Рис. 2.6. Схема машины Тьюринга

Как и в машине Поста, лента разбита на отдельные ячейки, однако, в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево. Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите А = а₁. а_п> - этот алфавит называется внешним. В нем выделяется специальный символ - ∆, называемый пустым знаком - его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке a_i знаком a_j. При этом возможны сочетания:

j =i— это означает, что в обозреваемой ячейке знак не изменился;
i ≠ 0, j = 0 означает, что хранившийся в ячейке знак заменяется пустым, т.е. стирается;
i = 0, j ≠ 0 означает, что пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;
i ≠ j ≠ 0 соответствует замене одного знака другим.

Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). Оно может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q = q₁…q_m, z>, причем, состояние z соответствует завершению работы, a q₁ является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (a_i, q_i) и три выходных (а_i+₁, q_i₊1, D_i₊₁) (см. рис. 2.7):

Рис. 2.7. Изображение логического устройства

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (a_i), а на другой вход - знак, обозначающий состояние ЛУ в данный момент (q_i). В зависимости от полученного сочетания знаков (a_i, q_i) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (a_i₊₁), подает команду перемещения головки (D_i₊₁ из R, L и S), а также дает команду на вызов следующего управляющего знака (q_i₊₁). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние. Схема функционирования такой машины представлена на рис. 2.8.

Рис. 2.8. Схема функционирования машины Тьюринга

В данной схеме отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты - она предназначена для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохраняется следующее состояние (q_i₊₁), а в D - команда сдвига (D_i₊₁). Из Q по линии обратной связи q_i₊₁ поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.

Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: q_ia_j→q_i'a_j'D_k, т.е. после обзора символа a_j головкой в состоянии a_i, в ячейку записывается символ a_j', головка переходит в состояние q_i', а лента совершает движение D_k. Для каждой комбинации q_ia_j имеется роено одно правило преобразования (правил нет только для z, поскольку, попав в это состояние, машина останавливается). Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов q_ia_j одну и только одну тройку выходных q_i'a_j'D_k - она называется логической функцией машины и обычно представляется в виде таблицы (функциональной схемой машины), столбцы которой обозначаются символами состояний, а строки - знаками внешнего алфавита. Если знаков внешнего алфавита п, а число состояний ЛУ т, то, очевидно, общее число правил преобразования составит п∙т.

Конкретная машина Тьюринга задается перечислением элементов множеств А и Q, а также, логической функцией, которую реализует ЛУ, т.е. набором правил преобразования. Ясно, что различных множеств A, Q и логических функций может быть бесконечно много, т.е. и машин Тьюринга также бесконечно много.

Совокупность состояний всех ячеек ленты, состояния ЛУ и положение головки называется конфигурацией машины.

Записать конфигурацию можно следующим образом: ∆а₁q_ia_j. а_k∆ которая означает, что в слове из k символов обозревается секция номер j и при этом управляющее устройство находится в состоянии q_i. Ясно, что конфигурация машины может содержать любое количество символов внешнего алфавита и лишь один символ внутреннего. Часто конфигурацию записывают в виде α₁q_iα₂, где α₁ - слово на ленте слева от головки, α₂ - слово на ленте справа от головки, включая обозреваемый знак. Слева от α₁ и справа от α₂ лента пуста. Конфигурация, изображенная на рис. 2.6., может быть записана следующим образом: а₁∆а₂∆qa₃а₄а_k, на рис. 2.8.- 1q1111.

Перед началом работы на пустую ленту записывается исходное слово α конечной длины в алфавите А; головка устанавливается над первым символом слова α, ЛУ переводится в состояние q₁ (т.е. начальная конфигурация имеет вид q₁α). Поскольку в каждой конфигурации реализуется только одно правило преобразования, начальная конфигурация однозначно определяет всю последующую работу машины, т.е. всю последовательность конфигураций вплоть до прекращения работы.

В зависимости от начальной конфигурации возможны два варианта развития событий:

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

В первом случае говорят, что данная машина применима к начальной информации, во втором - нет. Вся совокупность входных конфигураций, при которых машина обеспечивает получение результата, образуют класс решаемых задач. Очевидно, применять машину Тьюринга для задачи, не входящей в класс решаемых, бессмысленно. С другой стороны, во многих случаях возможно расширение класса решаемых задач за счет создания другой машины Тьюринга. Возникает вопрос: можно ли построить такую универсальную машину (хотя бы на теоретическом уровне), которая решала бы любую задачу?

Рассмотрим решение задачи о добавлении 1 к унарному числу посредством машины Тьюринга. Внешний алфавит может быть задан множеством А = , где 1 соответствует заполненной секции, а ∆ - пустому знаку, причем заполненные следуют друг за другом подряд. Внутренний алфавит задается множеством Q = q, z>, где q соответствует рабочему состоянию ЛУ, a z-остановке. Набор всех правил преобразования (логическая функция) может быть представлен функциональной схемой:

Рис. 2.9. Логическая функция

Составляется функциональная схема в виде таблицы таким образом, что знаки, обозначающие колонки и строки, определяют входные параметры ЛУ, а в ячейке таблицы на их пересечении стоит выходная команда. В частности, если головка машины обозревает секцию ленты со знаком 1 и машина находится в рабочем состоянии (q), то результатом ее работе на данном такте должно стать повторение 1 в данной секции и переход на одну секцию вправо R (при этом, как указывалось, лента сдвигается влево) - эта команда записывается как q1R. Если же в обозреваемой секции ∆, а состояние ЛУ q, то ∆ будет заменен 1, сдвига ленты производиться не будет и машина остановится – z1S. При комбинации на входе ∆z, как и 1z, машина находится в нерабочем состоянии - не происходит ни изменения конфигурации, ни движения - по этой причине такие комбинации в функциональных схемах в дальнейшем отображаться не будут.

Пусть начальной является конфигурация 1q1111*. Тогда работа машины в соответствии с описанной логической функции будет происходить следующим образом:

Такт 1 Обозревается 1, в ЛУ состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11 q111.

Такт 2 - аналогичным образом осуществляется переход к конфигурации 111q11.

Такт 3 - переход к конфигурации 1111q1.

Такт 4 - переход к конфигурации 11111q∆ (здесь для лучшего понимания правый ∆ указан в явном виде).

Такт 5 Обозревается ∆, в ЛУ состояние q. Выходная команда z1S - вместо ∆ в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация 111111z.

* Как указывалось выше, незначащие пустые секции слева и справа от заполненных в конфигурацию не включаются; поскольку в данной задаче несколько заполненных секций следуют подряд, только они и указываются в конфигурации.

Имеется запись многоразрядного целого числа п в десятичной системе счисления; построить машину Тьюринга, которая обеспечивала бы вычисление значение n + 1.

Используем внешний алфавит А = , в котором символ ∆ соответствует пустому знаку. Внутренний алфавит, как и в предыдущей задаче, образуется двумя состояниями - рабочим (q) и остановкой (z) (Q = q, z>). Исходное число п, а также результат - п + 1 - записываются в десятичной системе, причем, цифры размещаются по одной в соседних ячейках без пропусков. Функциональную схему представляется таблицей (для удобства строка будут соответствовать состоянию q, а столбцы - знакам внешнего алфавита):

Рис. 2.10. Функциональная схема

Пусть начальной конфигурацией будет 21 q9.

Такт 1 q9→q0L, т.е. 9 будет заменена на 0 и головка сдвинется на разряд десятков - промежуточная конфигурация 2q10.

Такт 2 q1→z2S, т.е. 1 будет заменена на 2 и произойдет остановка с конечной конфигурацией 2z20, т.е. получен результат сложения 219 + 1.

Пусть начальной будет конфигурация 99q9.

Такт 1 q9→q0L, т.е. сформируется промежуточная конфигурация 9q90.

Такт 2 q9→ q0L - возникнет конфигурация q900.

Такт 3 q9→q0L - возникнет q∆000.

Такт 4 q∆→z1S - возникнет z1000 и работа прекращается.

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

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

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

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

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

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

Далее мы рассмотрим SWITCH-технологию проектирования автоматных программ, в которой с подобными процессами сталкиваешься сплошь и рядом. С одной стороны, она так изменила модель конечного автомата, что фактически вывела ее за рамки теории автоматов. А, с другой стороны, вводит в программирование понятия, которые с трудом воспринимаются программистами, а, порой, просто являются лишними, т.к. существуют более привычные аналоги из теории программ и практики программирования.

В лекции достижением автоматного программирования объявлено введение в него понятия автоматизированных объектов управления, заимствованное из теории автоматического управления (ТАУ). Но, напомним, что в ТАУ рассматривают не столько объекты, а системы, среди которых выделяют следующие [4]:

Исходя из этого, правильнее было бы говорить о системах автоматического управления (САУ). Теперь посмотрим на типовую функциональную схему САУ, показанную рис. 1. Если ленту машины Тьюринга считать объектом управления, то исполнительными устройствами (ИсУ) будут элементы МТ, реализующие изменение содержимого ленты и передвигающие головку, а измерительными устройствами (ИзУ) — элементы, читающие информацию с ленты.

Рис.1. Функциональная схема САУ

Но зачем обращаться к ТАУ, если есть более близкая к программированию практика проектирования вычислительных систем, в которой операционные устройства (ОУ), к которым, безусловно, относится и МТ, рассматриваются в виде комбинации операционного (ОА) и управляющего (УА) автоматов. И это ближе к тому, к чему мы в конечном итоге стремимся — обоснованию мощности автоматного программирования. На рис. 2 представлен скрин текста из монографии Майорова С.А., Новикова Г.И. Структура электронных вычислительных машин [5], в которой вопросы проектирования ОУ рассмотрены весьма детально.

Рис.2. Концепция управляющего и операционного автоматов

Но, если сравнивать теорию проектирования ЭВМ и теорию программ, то между ними прослеживается явная структурная аналогия. В теории программирования модель любой программы на структурном уровне можно представить, как схему программы S = (M, A, C), где M – множество элементов памяти, A – множество операторов, C – управление [10]. Следуя этому подходу, любую программу машины Тьюринга также можно определить как схему программы, в которой множество M представлено ячейками ленты, множество операторов – действиями МТ, связанными 1) с анализом ячеек, 2) изменением символов в ячейках ленты и 3) перемещением головки.

Из сказанного можно понять, что лента лишь условно может считаться объектом управления для МТ. Хотя бы потому, что устройство управления машины Тьюринга не имеет к ней прямого доступа, т.к. все операции с ячейками реализуют опосредован-но блоки ОА. Кроме того, как представляется, не очень привычно или, если не сказать, странно считать целью управления программы, как системы управления, объект, представляющий собой память (ленту).
Таким образом, для формального определения машины Тьюринга, а в ее контексте места для модели конечного автомата, достаточно понятий теории программ. Теперь, в отличие от весьма расплывчатого определения автоматных программ, данного в рамках SWITCH-технологии, можно сказать, что автоматной программой считается программа, имеющая управление в форме модели конечного автомата.

Можно также вспомнить, что машину Тьюринга уже давно принято считать авто-матом [6] или уж, в крайнем случае, его простым расширением [7]. Но необходимо понимать, что это за автомат, что это за расширение, и эквивалентны ли они моделям классических конечных автоматов. Попробуем это как раз и уточнить.

2. Тьюрингово программирование в среде автоматного программирования

На рис. 3 показан автомат для МТ функции инкремента из монографии [8]. По форме это явно не программа для МТ, но уже и не классический конечный автомат. На рис. 4 приведен граф классического структурного конечного автомата (СКА) и его реализация в среде ВКПа (среда визуально-компонентного автоматного программирования на языке С++ в рамках библиотеки Qt и среды Qt Creator), реализующего тот же самый алгоритм блока управления (БУ) МТ.

Рис.3. Увеличение числа на единицу с помощью машины Тьюринга

Рис.4 Модель программы инкремента для МТ в форме СКА

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

Данный СКА имеет то же множество состояний, что и автомат на рис.3. При этом кроме собственно автоматного отображения, представленного СКА, он реализует еще два отображения – отображение множества предикатов (x1, …, xM) на множество одноименных входных каналов автомата, и множество выходных каналов автомата на множество одноименных действий – y1, …, yN. Например, предикат x3 вернет значение true (значение 1 для одноименного входного сигнала), если в текущей ячейке будет символ 1, а действие y4, которое будет запущено, когда одноименный выходной сигнал автомата примет значение 1, будет соответствовать перемещение головки влево (L) и т.д. и т.п.

2.1. Объектная реализация МТ на языке С++

Рассмотрим объектную программную реализацию машины Тьюринга на языке C++ в среде ВКПа, реализующую любую программу для МТ, в том числе и программу вычисления инкремента.

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

Листинг 1. Программная реализация базового класса МТ

Листинг 2. Программа инкремента для машины Тьюринга

2.2. Примеры программ для МТ с реализацией на С++

Рис. 5. Функция переходов машины Тьюринга, распознающая язык

Рис. 6. Граф СКА машины Тьюринга, распознающей язык

Блок управления МТ в форме СКА имеет 6 входных и 7 выходных каналов. Про-грамма акцептора включает также соответствующее им число предикатов и действий, которые представлены на рисунке справа от графа автомата. Реализация программы на С++ в среде ВКПа представлена на листинге 3.

Листинг 3. Программа для машины Тьюринга, распознающей язык

На листинге 3 действие y18 представляет вариант программы для МТ в соответствии с подходом SWITCH-технологии. В рамках реализации автоматного программирования среды ВКПа в этом случае вместо автомата на рис. 6 необходимо будет реализовать автомат с одним состоянием, который выдает в цикле сигнал y18. Ему соответствует закомментированная строка таблицы переходов на листинге 3. Для работы автомата по типу SWICH необходимо снять комментарий с данной строки, а остальные строки закомментировать.

Программа для МТ, находящая наибольший общий делитель (НОД) двух чисел, показана на рис. 7. Эквивалентный ей граф СКА представлен на рис. 8. Заметим, что и здесь не используются команда перезаписи символов. Реализация на С++ представлен листингом 4.

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

Рис. 8. Граф СКА, эквивалентный графу на рис. 7

Листинг 4. Программа для машины Тьюринга нахождения НОД двух чисел

В заключение еще одна программа для МТ от разработчиков SWITH-технологии, рассмотренная в статье [11], где приведена задача распознавание скобок в двух варианта. Один в форме автомата Мили, второй – смешанный автомат (соответственно на рис. 9 и рис. 11). Соответствующие им структурные автоматы приведены на рис. 10 и рис. 12. Реализацию программы на С++ демонстрирует листинг 5.

Рис. 9. Распознавание скобок произвольной глубины. Граф переходов Мили

Рис. 10. Распознавание скобок произвольной глубины. Граф СКА Мили

Рис. 11. Распознавание скобок произвольной глубины. Граф переходов смешанного автомата

Рис. 12. Распознавание скобок произвольной глубины. Граф СКА переходов сме-шанного автомата

Листинг 5. Программа для машины Тьюринга распознавания вложенности скобок

3. Заключение

Подводя итог, можно сказать, что нет формальных отличий тьюрингового программирования от автоматного, т.к. машина Тьюринга – это абстрактная модель автоматных программ. Просто в последнем случае используется более широкий набор операторов и структур данных (памяти). Теперь можно уверенно ответить и на вопрос, чем отличается машина Поста, как модель обычных программ, от машины Тьюринга — модели автоматных программ. Моделью управления и лишь только ею, т.к. остальное – память и операторы могут быть одними и теми же.
Следовательно, обычное программирование отличается от программирования автоматного только одним – моделью управления. Таким образом, пока для реализации автоматов используются обычные операторы управления типа switch и им подобные нельзя, строго говоря, такое программирование считать автоматным. Это может быть имитация автоматов с утратой их определенных свойств и не более того.

Однако, на момент публикации упомянутых статей авторам SWITCH-технологии уже была известна критика в ее адрес. Это не было тайной, т.к. с ней можно было ознакомиться на сайте SoftCraft [14]. На нем же были созданы разделы, посвященные автоматному программированию вообще и SWITH-технологии и КА-технологии в частности. Позиции авторов обсуждались на форуме сайта (он был на тот момент открыт). Но все так и остались при своем мнении.

Итоги на текущий момент таковы. Критика, высказанная в отношении SWITH-технологии когда-то давно, актуальна и на текущий момент. Она же относится и к пакету Stateflow. В SWITH-технологии как не было, так и нет четкого определения автоматного программирования, не изменился подход к реализации автоматов, сама модель не является классической, нет модели параллельных вычислений и т.д. и т.п. Без устранения этих проблем подобное автоматное программирование в лучшем случае претендует на достаточно ограниченную роль.

Причины отмеченных выше проблем довольно ясны: игнорируется теория программ, забыта теория автоматов, хотя о самих автоматах и об их замечательных свойствах сказано много хороших и правильных слов. Но по факту это другие автоматы. Автор убежден в сомнительности непродуманных попыток создавать оригинальные модели. Речь о синхронных, реактивных и других моделях. Они могут быть удобны при решении узкого класса задач и не более того. Но серьезнее то, что они выпадают из теории автоматов, не имея при этом собственной теории. А модель вне теории беспомощна, а потому фактически бессмысленна.

Open with Desktop
View raw
Copy raw contents Copy raw contents

Copy raw contents

Абстрактные вычислительные машины

Материал взят с ресурса Планета информатики

Машина Тьюринга - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

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

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

Внешний алфавит. Конечное множество (например, А ), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, Q0 ) должна представлять собой пустой символ.
Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, Q1 ) должно быть начальным (запускающим программу). Еще одно из состояний ( Q0 ) должно быть конечным (завершающим программу) – состояние останова.
Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
Передвигаться на одну ячейку влево или вправо.
Менять свое внутреннее состояние.

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

Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):

Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние 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 - запись буквы Т справа от слова и останов машины.

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты. Каждая ячейка ленты может находиться в 2 состояниях - быть либо пустой - 0 , либо помеченной меткой 1 . За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.

Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:

где i - номер команды, K - действие каретки, j - номер следующей команды (отсылка). Всего для машины Поста существует шесть типов команд:

После программы запуска возможны варианты:

работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
работа может закончиться командой "стоп";
работа никогда не закончится.

Для сложения и вычитания натуральных (целых неотрицательных) чисел P и Q их можно представить на ленте набором из P единиц и Q , отделённых друг от друга одним нулём; пусть исходное положение каретки находится на крайней левой 1 группы единиц Q :

Сложение двух чисел тривиально - достаточно поставить 1 между числами и стереть одно крайнее правое 1 у представления Q .

Программа вычитания таких чисел состоит из последовательного изменения крайних левых 1 у представления Q и правых 1 у представления P . В начале программы каретка установлена на крайнюю левую 1 у Q :

- шаг влево
? 1; 3 - если в ячейке пусто, перейти к 1 -шагу, если нет - к 3
X - удалить метку
-> - шаг вправо
? 4; 6 - если в ячейке пусто, перейти к 4 -шагу, если нет - к 6
X - удалить метку
-> - шаг вправо
? 9; 1 - если в ячейке пусто, перейти к 9 шагу, если нет - к 1
! - конец В 5 -й строке возможно зацикливание, если Q > P .

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Читайте также: