Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов, страница 4

Нахождение минимального значения из двух заданных чисел f(x, y) = min(x, y).4. Нахождение максимального значения из двух заданных чисел f(x, y) = max(x, y).5. Усеченное вычитание x − 1, если x > 1,x ÷1 = если x < 1.0,6. Функция r(x, y) - остаток от деления y на x.7. Функция q(x, y) - частное от деления y на x.8. Доказать, что предикат Pdn(x) "x делится на n" примитивно-рекурсивен для любого n.9. Доказать, что предикат Pdn,m(x) "x делится на n и m" примитивно-рекурсивен длялюбых n и m.10. Доказать, что отношение x1 > x2 примитивно-рекурсивно.11. Доказать, что предикат f(x) = g(x) примитивно-рекурсивен, если функции f(x) и g(x)примитивно-рекурсивны.12.

Дано множество слов одинаковой длины, причем первые два слова выделены.Построить цепь от первого выделенного слова ко второму так, чтобы все слова этой цепибыли только из заданного множества. Соседние слова построенной цепи должны отличатьсятолько одной буквой.13. Дано множество слов. Построить из них кроссворд заданной конфигурации (числослов может быть больше требуемого количества для заполнения кроссворда).14. Грани кубика разбиты на клетки 5х5. Каждая из клеток выкрашена в белый илисиний цвет. Переход из клетки в клетку допускается только через общую сторону приусловии совпадения цветов этих клеток. Построить маршрут перехода из одной заданнойклетки в другую заданную клетку этого же цвета.15.

Имеется клетчатая ткань размером NxN клеток. Разрезать ее на M квадратных частей,не нарушая целостности клеток.3. МАШИНЫ ТЬЮРИНГА3.1. Общие сведенияОдним из первых формальных определений алгоритма было определение английскогоматематика А. Тьюринга, который в 1936 г. описал схему некоторой гипотетической(абстрактной) машины и формализовал правила выполнения действий при помощи описанияработы этой машины.Машина Тьюринга является абстракцией, которую нельзя реализовать практически.Поэтому алгоритмы для машины Тьюринга должны выполняться другими средствами.Основным следствием формализации алгоритмов с использованием машины Тьюрингаявляется возможность доказательства существования или несуществования алгоритмоврешения различных задач.Описывая различные алгоритмы для машин Тьюринга и доказывая реализуемостьвсевозможных композиций алгоритмов, Тьюринг убедительно показал разнообразиевозможностей предложенной им конструкции, что позволило ему выступить со следующимтезисом: “Всякий алгоритм может быть реализован соответствующей машиной Тьюринга”.Доказать тезис Тьюринга нельзя, так как в его формулировке не определено понятие “всякийалгоритм”.

Его можно только обосновать, представляя различные алгоритмы в виде машинТьюринга. Было доказано, что класс функций, вычислимых на этих машинах, совпадает склассом частично рекурсивных функций.3.2. Неформальное определение машины ТьюрингаМашина Тьюринга представляет собой автомат,имеющий бесконечную в обе стороны ленту, считывающую головку и управляющееустройство. Управляющее устройство может находиться в одном из состояний, образующихконечное множество Q = {q0, q1, ..., qn}.

Множество Q называют внутренним алфавитоммашины Тьюринга.Принципиальное отличие машины Тьюринга от вычислительных машин состоит в том,что ее запоминающее устройство представляет собой бесконечную ленту, из-за которойневозможна ее физическая реализация. Лента разделена на ячейки, в каждой из которыхможет быть записан один из символов конечного алфавита A = {a0, a1, .

. . , am}, которыйназывают входным алфавитом машины Тьюринга. Во время функционирования машиныТьюринга может быть заполнено конечное число ячеек. Считывающая головка в каждыймомент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке исостояния управляющего устройства записывает в ячейку новый символ или оставляет егобез изменения, сдвигается на ячейку влево или вправо или остается на месте. При этомуправляющее устройство переходит в новое состояние или остается в старом. Средисостояний управляющего устройства выделены начальное состояние q0 и заключительноесостояние qz.Таким образом, за один такт работы машина Тьюринга может считать символ, записатьвместо него новый или оставить его без изменения и сдвинуть головку на одну ячейку влевоили вправо или оставить ее на месте.3.3. Формальное определение машины ТьюрингаАлфавит A – это некоторое конечное множество символов.Цепочкой над алфавитом называется последовательность символов из этого алфавита.Длина цепочки x представляет собой число символов в цепочке и обозначается | x |.

Длинапустой цепочки равна нулю.Конкатенацией цепочек X и Y называют цепочку, полученную приписыванием символовцепочки Y справа к цепочке X.Машиной Тьюринга называется семерка видаT = (Q, A, δ, p0, pz, a0, a1), гдеQ – конечное множество состояний, в которых может находиться управляющееустройство;A – входной алфавит;δ – функция переходов, δ = Q ⋅ A → Q ⋅ A ⋅ S, гдеS = {R, L, E} - направления сдвига;p0 – начальное состояние; p0 ∈ Q;pz – заключительное состояние; pz ∈ Q;a0 – символ для обозначения пустой ячейки, a0 ∈ A;a1 – специальный символ - разделитель цепочек на ленте, a1 ∈ A.Командой машины Тьюринга называется элемент функции переходов qa → pbr, где q иp∈ Q; a и b∈A; r∈S.

Каждая команда описывает один такт работы машины Тьюринга.Конфигурация машины Тьюринга представляется следующим образом: t = <CqaB>, гдеC - цепочка, находящаяся слева от считывающей головки;q - состояние машины Тьюринга;a - символ, находящийся под головкой машины Тьюринга;B - цепочка, находящаяся справа от головки машины Тьюринга.Конфигурация <CqaB> непосредственно переходит в конфигурацию <CnqnanBn>, еслиновая конфигурация получена в результате применения одной команды к исходнойконфигурации.Обозначим непосредственный переход из одной конфигурации в другую следующимобразом: <CqaB>⇒<CnqnanBn>.Конфигурация, содержащая начальное состояние, называется начальной, а содержащаязаключительное состояние - заключительной.

Если цепочка С в конфигурации пустая, тоначальная и заключительная конфигурации называются стандартными.Машина Тьюринга перерабатывает цепочку x в цепочку y, если, действуя из начальнойконфигурации и имея на ленте цепочку x, машина Тьюринга переходит в заключительнуюконфигурацию, имея на ленте цепочку y. Если начальная и заключительная конфигурацииявляются стандартными, то процесс переработки x в y является правильной переработкой.3.4. Способы представления машины ТьюрингаСуществует три способа представления машины Тьюринга: совокупностью команд, ввиде графа, в виде таблицы соответствия.3.4.1.

Представление машины Тьюринга совокупностью командСовокупность всех команд, которые может выполнять машина, называется еепрограммой.Машина Тьюринга считается заданной, если заданы ее внешний и внутренний алфавиты,программа, начальная конфигурация и указано, какие из символов обозначают пустуюячейку и заключительное состояние.Чтобы записать совокупность команд, нужно воспользоваться следующими правилами:1) начальному шагу алгоритма ставится в соответствие q 0 - начальное состояние;2) циклы реализуются так, что последнее действие цикла должно соответствоватьпереходу в то состояние, которое соответствует началу цикла;3) соседним шагам алгоритма соответствует переход в смежные состояния, которыесоответствуют этим пунктам;4) последний шаг алгоритма вызывает переход в заключительное состояние.В качестве примера рассмотрим совокупность команд машины Тьюринга, котораяинвертирует входную цепочку, записанную с использованием нулей и единиц.Пусть алфавит машины Тьюринга задан множеством A={0, 1, ε}, гдесимвол ε соответствует пустой ячейке, а число состояний устройства управления задано ввиде множества Q = {q0, q1, qz}.Если, например,начальная конфигурация имеет вид q0110011, то конечнаяконфигурация после завершения операции инвертирования должна иметь вид qz001100.

Длярешения задачи машиной будет порождена следующая последовательность команд:q01 → q00R,q10 → q10L,q11 → q11L,q00 → q01R,q1ε → qzεR.q0 ε → q1εL,В стандартной начальной конфигурации головка стоит над первым символом слева, иустройство управления находится в начальном состоянии. На следующем такте машинаТьюринга, не меняя своего состояния, заменяет символ 0 на 1 или 1 на 0 и сдвигается вправона один символ. После просмотра всей цепочки под головкой оказывается символ,указывающий на пустую ячейку.

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

Представление машины Тьюринга графомПри представлении машины Тьюринга посредством графа необходимо каждомусостоянию поставить в соответствие вершину графа, а каждой команде - помеченную дугу.Машина Тьюринга из рассмотренного примера инвертирования цепочки, состоящей изсимволов 0 и 1, будет представлена в виде графа следующим образом:0→0L0→1Rε→εLε →Rq0qzq11→0R1→1LНачальная и конечная вершины графа обычно выделяются; на рисунке они отмеченычерным кружком. Если на очередном такте работы машины Тьюринга символ на ленте неизменяется, то в правой части команды его можно не писать (ε на ребре в состояние qz ).3.4.3. Представление машины Тьюринга таблицей соответствияПри представлении машины Тьюринга данным способом составляется таблица, вкоторой каждому состоянию соответствует строка, а каждому символу из входного алфавита- столбец.