Что такое состояние машины тьюринга. Тренажер для изучения универсального исполнителя. Многоленточная машина Тьюринга
Маши́на Тью́ринга (МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма .
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча - Тьюринга , способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
Устройство машины Тьюринга
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство , способное находиться в одном из множества состояний . Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода , которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные , и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной , если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ - состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной .
Описание машины Тьюринга
Конкретная машина Тьюринга задаётся
перечислением элементов множества букв
алфавита A, множества состояний Q и
набором правил, по которым работает
машина. Они имеют вид: q i a j →q i1 a j1 d k
(если головка находится в состоянии q i ,
а в обозреваемой ячейке записана буква
a j , то головка переходит в состояние
q i1 , в ячейку вместо a j
записывается a j1 , головка делает
движение d k , которое имеет три
варианта: на ячейку влево (L), на ячейку
вправо (R), остаться на месте (N)). Для
каждой возможной конфигурации имеется ровно одно правило.
Правил нет только для заключительного
состояния, попав в которое машина
останавливается. Кроме того, необходимо
указать конечное и начальное состояния,
начальную конфигурацию на ленте и
расположение головки машины.
Пример машины Тьюринга
Приведём пример МТ для умножения чисел в унарной системе счисления . Машина работает по следующему набору правил:
|
Набор правил |
Набор правил |
|
q 0 ×→q 1 ×R |
|
|
q 6 ×→q 7 ×R |
|
|
q 2 ×→q 3 ×L |
|
|
q 3 1 → q 4 aR |
|
|
q 4 ×→q 4 ×R |
Умножим с помощью МТ 3 на 2 в единичной системе:
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).
Полнота по Тьюрингу
Основная статья : Полнота по Тьюрингу
Можно сказать, что машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам преобразует входные данные с помощью последовательности элементарных действий .
Элементарность действий заключается в том, что действие меняет лишь небольшой кусочек данных в памяти (в случае машины Тьюринга - лишь одну ячейку), и число возможных действий конечно. Несмотря на простоту машины Тьюринга на ней можно вычислить всё, что можно вычислить на любой другой машине, осуществляющей вычисления с помощью последовательности элементарных действий. Это свойство называется полнотой .
Один из естественных способов доказательства того, что алгоритмы вычисления, которые можно реализовать на одной машине, можно реализовать и на другой, - это имитация первой машины на второй.
Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины D и входные данные X , которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные X .
Как было сказано, на машине Тьюринга можно имитировать (с помощью задания правил перехода) все другие исполнители, каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
На машине Тьюринга можно имитировать машину Поста , нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью (суммарная память компьютера - оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. - может быть очень большой, но, тем не менее, всегда конечна).
Варианты машины Тьюринга
Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга.
Машина Тьюринга, работающая на полубесконечной ленте
В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:
Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:
Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.
Транскрипт
1 Московский государственный университет им. М.В. Ломоносова Факультет вычислительной математики и кибернетики В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая Машина Тьюринга и алгоритмы Маркова. Решение задач (Учебно-методическое пособие) Москва, 2006
2 УДК ББК П32 Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие) - М.: МГУ, с. Издательский отдел факультета ВМК МГУ (лицензия ЛР от) Пособие посвящено решению задач по теме «Введение в теорию алгоритмов», изучаемой на первом курсе факультета ВМК МГУ в рамках дисциплины «Алгоритмы и алгоритмические языки». Это задачи на составление алгоритмов в виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачи теоретического характера. В пособии приводятся необходимые сведения по теории алгоритмов, подробно объясняются типичные приёмы решения задач и предлагается большой набор задач для самостоятельного решения. Пособие рассчитано на студентов первого курса факультета ВМК МГУ и преподавателей, ведущих семинарские занятия по программированию. Рецензенты: доцент Баула В.Г. доцент Корухова Л.С. Печатается по решению Редакционно-издательского совета факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова. ISBN??? Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова,
3
1. Машина Тьюринга В разделе рассматриваются задачи на составление алгоритмов для машины Тьюринга. Приводится краткое описание этой машины, на примерах объясняются основные приёмы составления таких алгоритмов и предлагаются задачи для самостоятельного решения. 1.1 Краткое описание машины Тьюринга Структура машины Тьюринга Машина Тьюринга (МТ) состоит из двух частей ленты и автомата (см. слева): лента: a b b Λ Λ a b b Λ Λ автомат: q q Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки, которые никак не нумеруются и не именуются. В каждой клетке может быть записан один символ или ничего не записано. Содержимое клетки может меняться в неё можно записать другой символ или стереть находящийся там символ. Договоримся пустое содержимое клетки называть символом «пусто» и обозначать знаком Λ («лямбда»). В связи с этим изображение ленты, показанное на рисунке справа, такое же, как и на рисунке слева. Данное соглашение удобно тем, что операцию стирания символа в некоторой клетке можно рассматривать как запись в эту клетку символа Λ, поэтому вместо длинной фразы «записать символ в клетку или стереть находящийся там символ» можно говорить просто «записать символ в клетку». Автомат это активная часть МТ. В каждый момент он размещается под одной из клеток ленты и видит её содержимое; это видимая клетка, а находящийся в ней символ видимый символ; содержимое соседних и других клеток автомат не видит. Кроме того, в каждый момент автомат находится в одном из состояний, которые будем обозначать буквой q с номерами: q1, q2 и т.п. Находясь в некотором состоянии, автомат выполняет какую-то определённую операцию (например, перемещается направо по ленте, заменяя все символы b на a), находясь в другом состоянии другую операцию. Пару из видимого символа (S) и текущего состояния автомата (q) будем называть конфигурацией и обозначать
4 Такт работы машины Тьюринга МТ работает тактами, которые выполняются один за другим. На каждом такте автомат МТ выполняет три следующих действия, причем обязательно в указанном порядке: 1) записывает некоторый символ S в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется); 2) сдвигается на одну клетку влево (обозначение L, от left), либо на одну клетку вправо (обозначение R, от right), либо остается неподвижным (обозначение N). 3) переходит в некоторое состояние q (в частности, может остаться в прежнем состоянии). Формально действия одного такта будем записывать в виде тройки: S, , q где конструкция с квадратными скобками означает возможность записи в этом месте любой из букв L, R или N. Например, такт *,L,q8 означает запись символа * в видимую клетку, сдвиг на одну клетку влево и переход в состояние q8. Программа для машины Тьюринга Сама по себе МТ ничего не делает. Для того чтобы заставить её работать, надо написать для неё программу. Эта программа записывается в виде следующей таблицы: q 1 q j q m S 1 S 2 S i S n Λ S, , q Слева перечисляются все состояния, в которых может находиться автомат, сверху все символы (в том числе и Λ), которые автомат может видеть на ленте. (Какие именно символы и состояния указывать в таблице определяет автор программы.) На пересечениях же (в ячейках таблицы) указываются те такты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ. В целом таблица определяет действия МТ при всех возможных конфигурациях и тем самым полностью задаёт поведение МТ. Описать алгоритм в виде МТ значит предъявить такую таблицу. (Замечание. Часто МТ определяют как состоящую из ленты, автомата и программы, поэтому при разных программах получаются разные МТ. Мы же будет считать, в духе современных компьютеров, что МТ одна, но она может выполнять разные программы.) 4
5
Правила выполнения программы До выполнения программы нужно проделать следующие предварительные действия. Во-первых, надо записать на ленту входное слово, к которому будет применена программа. Входное слово это конечная последовательность символов, записанных в соседних клетках ленты; внутри входного слова пустых клеток быть не должно, а слева и справа от него должны быть только пустые клетки. Пустое входное слово означает, что все клетки ленты пусты. Во-вторых, надо установить автомат в состояние q 1 (указанное в таблице первым) и разместить его под первым символом входного слова: a b b q 1 Если входное слово пустое, то автомат может смотреть в любую клетку, т.к. все они пусты. После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой строки (т.к. автомат находится в состоянии q 1) и того столбца, который соответствует первому символу входного слова (это необязательно левый столбец таблицы), и выполняется такт, указанный в этой ячейке. В результате автомат окажется в новой конфигурации. Теперь такие же действия повторяются, но уже для новой конфигурации: в таблице отыскивается ячейка, соответствующая состоянию и символу этой конфигурации, и выполняется такт из этой ячейки. И так далее. Когда завершается выполнение программы? Введём понятие такта останова. Это такт, который ничего не меняет: автомат записывает в видимую клетку тот же символ, что и был в ней раньше, не сдвигается и остается в прежнем состоянии, т.е. это такт S,N,q для конфигурации
6
2) Второй исход «плохой»: это когда МТ зацикливается, никогда не попадая на такт останова (например, автомат на каждом шаге сдвигается вправо и потому не может остановиться, т.к. лента бесконечна). В этом случае говорят, что МТ неприменима к заданному входному слову. Ни о каком результате при таком исходе не может идти и речи. Отметим, что один и тот же алгоритм (программа МТ) может быть применимым к одним входным словам (т.е. останавливаться) и неприменимым к другим (т.е. зацикливаться). Таким образом, применимость/неприменимость зависит не только от самого алгоритма, но и от входного слова. На каких входных словах алгоритм должен останавливаться? На, так сказать, хороших словах, т.е. на тех, которые относятся к допустимым исходным данным решаемой задачи, для которых задача осмысленна. Но на ленте могут быть записаны любые входные слова, в том числе и те, для которых задача не имеет смысла; на таких словах поведение алгоритма не фиксируется, он может остановиться (при любом результате), а может и зациклиться. Соглашения для сокращения записи Договоримся о некоторых соглашениях, сокращающих запись программы для МТ. 1) Если в такте не меняется видимый символ, или автомат не сдвигается, или не меняется состояние автомата, то в соответствующей позиции такта мы не будем ничего писать. Например, при конфигурации
7 1.2 Примеры на составление программ для МТ Рассмотрим примеры на составление программ для МТ, чтобы продемонстрировать некоторые типичные приёмы программирования на МТ. Для сокращения формулировки задач введём следующие два соглашения: буквой Р будем обозначать входное слово; буквой А будем обозначать алфавит входного слова, т.е. набор тех символов, из которых и только которых может состоять Р (отметим, однако, что в промежуточных и выходном словах могут появляться и другие символы). Пример 1 (перемещение автомата, замена символов) А={0,1,2,3,4,5,6,7,8,9}. Пусть Р непустое слово; значит, Р это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1 больше числа Р. Решение. Для решения этой задачи предлагается выполнить следующие действия: 1. Перегнать автомат под последнюю цифру числа. 2. Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например: Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 эту предпоследнюю цифру; например: Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100): В виде программы для МТ эти действия описываются следующим образом: Λ q1 0,R,q1 1,R,q1 2,R,q1 3,R,q1 4,R,q1 5,R,q1 6,R,q1 7,R,q1 8,R,q1 9,R,q1 Λ,L,q2 q2 1,N,! 2, N,! 3, N,! 4, N,! 5, N,! 6, N,! 7, N,! 8, N,! 9, N,! 0,L,q2 1,N,! Пояснения. q1 это состояние, в котором автомат «бежит» под последнюю цифру числа. Для этого он всё время движется вправо, не меняя видимые цифры и оставаясь в том же состоянии. Но здесь есть одна особенность: когда автомат находится под 7
8 последней цифрой, то он ещё не знает об этом (ведь он не видит, что записано в соседних клетках) и определит это лишь тогда, когда попадёт на пустую клетку. Поэтому, дойдя до первой пустой клетки, автомат возвращается назад под последнюю цифру и переходит в состояние q2 (вправо двигаться уже не надо). q2 это состояние, в котором автомат прибавляет 1 к той цифре, которую видит в данный момент. Сначала это последняя цифра числа; если она в диапазоне от 0 до 8, то автомат заменяет её цифрой, которая на 1 больше, и останавливается. Но если это цифра 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь в состоянии q2. Тем самым, он будет теперь прибавлять 1 к предыдущей цифре. Если и эта цифра равна 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь попрежнему в состоянии q2, т.к. должен выполнить то же самое действие увеличить на 1 видимую цифру. Если же автомат сдвинулся влево, а в видимой клетке нет цифры (а есть «пусто»), то он записывает сюда 1 и останавливается. Отметим, что для пустого входного слова наша задача не определена, поэтому на этом слове МТ может вести себя как угодно. В нашей программе, например, при пустом входном слове МТ останавливается и выдает ответ 1. Выше мы привели запись программы в полном, несокращённом виде. Теперь же приведём запись программы в сокращённом, более наглядном виде, при этом справа дадим краткое пояснение действий, которые реализуются в соответствующих состояниях автомата: Λ q1,r,r,r,r,r,r,r,r,r,r,l,q2 под последнюю цифру q2 1,! 2,! 3,! 4,! 5,! 6,! 7,! 8,! 9,! 0,L, 1,! видимая цифра + 1 Именно так мы и будем в дальнейшем записывать программы. Пример 2 (анализ символов) А={a,b,c}. Перенести первый символ непустого слова Р в его конец. Например: a b c b b c b a Решение. Для решения этой задачи предлагается выполнить следующие действия: 1. Запомнить первый символ слова P, а затем стереть этот символ. 2. Перегнать автомат вправо под первую пустую клетку за P и записать в неё запомненный символ. Как «бегать» вправо, мы уже знаем из предыдущего примера. А вот как запомнить первый символ? Ведь в МТ нет другого запоминающего устройства, кроме ленты, а запоминать символ в какой-то клетке на ленте бессмысленно: как только автомат сдвинется влево или вправо от этой клетки, он тут же забудет данный символ. Что делать? Выход здесь таков надо использовать разные состояния автомата. Если первый символ это a, то надо перейти в состояние q2, в котором автомат 8
9 бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c. Следовательно, то, каким был первый символ, мы фиксируем переводом автомата в разные состояния. Это типичный приём при программировании на МТ. С учётом сказанного программа будет такой: a b c Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R, анализ 1-го символа, удаление его, разветвление q2,r,r,r, a,! запись a справа q3,r,r,r, b,! запись b справа q4,r,r,r, c,! запись c справа Рассмотрим поведение этой программы на входных словах, содержащих не более одного символа. При пустом слове, которое является «плохим» для задачи, программа зациклится автомат, находясь в состоянии q1 и попадая всё время на пустые клетки, будет бесконечно перемещаться вправо. (Конечно, в этом случае программу можно было бы остановить, но мы специально сделали зацикливание, чтобы продемонстрировать такую возможность.) Если же во входном слове ровно один символ, тогда автомат сотрёт этот символ, сдвинется на одну клетку вправо и запишет в неё данный символ: c c q1 q4! Таким образом, слово из одного символа попросту сдвинется на клетку вправо. Это допустимо. Ведь клетки ленты не нумерованы, поэтому местоположение слова на ленте никак не фиксируется и перемещение слова влево или вправо заметить нельзя. В связи с этим не требуется, чтобы выходное слово обязательно находилось в том же месте, где было входное слово, результат может оказаться и левее, и правее этого места. Пример 3 (сравнение символов, стирание слова) А={a,b,c}. Если первый и последний символы (непустого) слова Р одинаковы, тогда это слово не менять, а иначе заменить его на пустое слово. Решение. Для решения этой задачи предлагается выполнить следующие действия: 1. Запомнить первый символ входного слова, не стирая его. 2. Переместить автомат под последний символ и сравнить его с запомненным. Если они равны, то больше ничего не делать. 3. В противном случае уничтожить всё входное слово. Как запоминать символ и как перегонять автомат под последний символ слова, мы уже знаем из предыдущих примеров. Стирание же входного слова реализуется 9
10 заменой всех его символов на символ Λ. При этом, раз уж автомат оказался в конце слова, будем перемещать автомат справа налево до первой пустой клетки. Эти действия описываются следующей программой для МТ (напомним, что крестик в ячейке таблицы означает невозможность появления соответствующей конфигурации при выполнении программы): a b c Λ q1,q2,q4,q6,! анализ 1-го символа, разветвление q2,r,r,r, L,q3 идти к последнему символу при 1-м символе a q3,!, q8, q8 сравнить посл. символ с a, не равны на q8 (стереть P) q4,r,r,r, L,q5 аналогично при 1-м символе b q5, q8,!, q8 q6,r,r,r, L,q7 аналогично при 1-м символе c q7, q8, q8,! q8 Λ,L, Λ,L, Λ,L,! стереть всё слово, двигаясь справа налево Пример 4 (удаление символа из слова) А={a,b}. Удалить из слова Р его второй символ, если такой есть. Решение. Казалось бы, эту задачу решить просто: надо сдвинуть автомат под клетку со вторым символом и затем очистить эту клетку: a b b a a b b a a b a Однако напомним, что внутри выходного слова не должно быть пустых клеток. Поэтому после удаления второго символа надо «сжать» слово, перенеся первый символ на одну клетку вправо. Для этого автомат должен вернуться к первому символу, запомнить его и стереть, а затем, снова сдвинувшись вправо, записать его в клетку, где был второй символ. Однако начальный «поход» вправо ко второму символу, чтобы его стереть, и последующий возврат к первому символу являются лишними действиями: какая разница переносить первый символ в пустую клетку или в клетку с каким-то символом? Поэтому сразу запоминаем первый символ, стираем его и записываем вместо второго символа: a b b a b b a a b a В виде программы для МТ всё это записывается так: a b Λ q1 Λ,R,q2 Λ,R,q3,! анализ и удаление 1-го символа, разветвление q2,! a,! a,! замена 2-го символа на a q3 b,!,! b,! замена 2-го символа на b Пример 5 (сжатие слова) А={a,b,c}. Удалить из слова Р первое вхождение символа a, если такое есть. Решение. В предыдущем примере мы переносили на позицию вправо только один сим- 10
11
вол. В данном же примере мы будем в цикле переносить вправо все начальные символы b и c входного слова до первого символа a или до пустой клетки: b c b c b a a b b a a b c a a b c b a Центральный момент здесь как перенести символ x из левой клетки в очередную клетку, где находится некоторый символ y, чтобы затем этот символ y можно было перенести в правую клетку? Если через q x обозначить состояние, в котором в видимую клетку надо записать символ x, находившийся ранее в клетке слева, тогда это действие можно изобразить так: x y y z x z q x Для этого предлагается выполнить такт x,r,q y, в котором объединены следующие три действия: во-первых, в видимую клетку записывается символ x, взятый из клетки слева; во-вторых, автомат сдвигается вправо под клетку, в которую затем надо будет записать только что заменённый символ y; в-третьих, автомат переходит в состояние q y, в котором он и будет выполнять эту запись. Повторение таких тактов в цикле и приведёт к сдвигу вправо на одну позицию начальных символов входного слова. Этот цикл должен закончиться, когда в очередной клетке окажется символ a или Λ (y=a или y=λ), а в начале цикла можно считать, что на место первого символа слева переносится символ «пусто» (x=λ). В итоге получается следующая программа для МТ: a b c Λ q1 Λ,R,! Λ,R,q2 Λ,R,q3,! q Λ : стереть 1-й символ и перенести его вправо q2 b,!,r, b,r,q3 b,! q b: запись b, перенос ранее видимого символа вправо q3 c,! c,r,q2,r, c,! q c: запись c, перенос ранее видимого символа вправо В этой программе следует обратить внимание на такт Λ,R,!, который выполняется в конфигурации
12 первый символ (на старом месте его можно пока не удалять), а затем, вернувшись на старое место, записать символ a: b c a b c a b b c a b a c a Перенос символа на одну позицию влево аналогичен переносу символа вправо, о чём говорилось в двух предыдущих примерах, поэтому приведем программу для МТ без дополнительных комментариев. Отметим лишь, что в состояниях q2, q3 и q4 автомат может видеть только пустую клетку, а в состоянии q5 он обязательно видит первый символ входного слова, но не пустую клетку. a b c Λ q1,l,q2,l,q3,l,q4,! анализ 1-го символа для переноса его влево q2 a,r,q5 приписать a слева q3 b,r,q5 приписать b слева q4 c,r,q5 приписать c слева q5,! a,! a,! заменить бывший 1-й символ на a Пример 7 (раздвижка слова) А={a,b,c}. Вставить в слово P символ a за первым вхождением символа c, если такое есть. Решение. Просматриваем входное слово слева направо до пустой клетки или до первого символа c. В первом случае c не входит в P, поэтому ничего не делаем. Во втором случае надо освободить место для вставляемого символа a, для чего сдвигаем начало слова P (от первого символа до найденного символа c) на одну позицию влево. При этом осуществляем такой сдвиг справа налево от символа c к началу слова, раз уж автомат находится под этим символом. Кроме того, чтобы затем не возвращаться к освободившейся позиции, начинаем этот сдвиг с записи a вместо найденного символа c. Поскольку этот циклический сдвиг влево реализуется аналогично циклическому сдвигу вправо из примера 5, то не будем пояснять его, а сразу приведём программу для МТ: a b c Λ q1,r,r, a,l,q4,l,! вправо до с, вставка a вместо c, перенос c влево q2,l, a,l,q3 a,l,q4 a,! перенос a справа q3 b,l,q2,l, b,l,q4 b,! перенос b справа q4 c,l,q2 c,l,q3,l, c,! перенос c справа Пример 8 (формирование слова на новом месте) А={a,b,c}. Удалить из P все вхождения символа a. Решение. Предыдущие примеры показывают, что в МТ достаточно сложно реализуются вставки символов в слова и удаления символов из слов. Поэтому иногда проще не раздвигать или сжимать входное слово, а формировать выходное сло- 12
13 во в другом, свободном месте ленты. Именно так мы и поступим при решении данной задачи. Конкретно предлагается выполнить следующие действия: 1. Выходное слово будем строить справа от входного. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком =, отличным от всех символов алфавита A (см. шаг 1). (Напомним, что на ленте могут быть записаны не только символы из алфавита входного слова.) 2. После этого возвращаемся к началу входного слова (см. шаг 2). a b c a b c = a b c = Теперь наша задача перенести в цикле все символы входного слова, кроме a, вправо за знак = в формируемое выходное слово. Для этого анализируем первый символ входного слова. Если это a, тогда стираем его и переходим к следующему символу (см. шаг 3). Если же первый символ это b или c, тогда стираем его и «бежим» вправо до первой пустой клетки (см. шаг 4), куда и записываем этот символ (см. шаг 5). b c = c = c = b Снова возвращаемся налево к тому символу, который стал первым во входном слове, и повторяем те же самые действия, но уже по отношению к этому символу (см. шаги 6-9). c = b = b = b c Этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак =. Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от a, в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться (см. шаг 10). = b c b c 9 10 С учётом всего сказанного и строим программу для МТ. При этом отметим, что помимо символов a, b и c в процессе решения задачи на ленте появляется знак =, поэтому в таблице должен быть предусмотрен столбец и для этого знака. a b c = Λ q1,r,r,r, =,q2 записать справа знак = q2,l,l,l,l,r,q3 влево к 1-му символу слова q3 Λ,R, Λ,R,q4 Λ,R,q5 Λ,R,! анализ и удаление его, разветвление q4,r,r,r,r, b,q2 запись b справа, возврат налево (в цикл) q5,r,r,r,r, c,q2 запись c справа, возврат налево (в цикл) 13
14 Пример 9 (фиксирование места на ленте) А={a,b}. Удвоить слово P, поставив между ним и его копией знак =. Например: a a b a a b = a a b Решение. Эта задача решается аналогично предыдущей: в конец входного слова записываем знак =, затем возвращаемся к началу слова и в цикле все его символы (в том числе и a) копируем в пустые клетки справа: a a b a a b = a a b = a a b = a 1 2 Однако есть и отличие: копируемые символы входного слова не удаляются, и это приводит к следующей проблеме. Записав справа копию очередного символа, мы затем должны вернуться к входному слову в позицию этого символа и потом сдвинуться вправо к следующему символу, чтобы скопировать уже его. Но как узнать, в какую позицию входного слова надо вернуться? Например, откуда мы знаем в нашем примере, что после копирования первого символа a мы должны вернуться именно к первому символу входного слова, а не ко второму или третьему? В предыдущей задаче мы всегда возвращались к первому из оставшихся символов входного слова, а теперь мы сохраняем все символы, поэтому непонятно, какие символы мы уже скопировали, а какие ещё нет. Отметим также, что в МТ ячейки ленты никак не нумеруются, нет в МТ и счетчиков, которые позволили бы определить, сколько символов мы уже скопировали. В общем виде проблема, с которой мы столкнулись, следующая: как зафиксировать на ленте некоторую позицию, в которой мы уже были и к которой позже должны вернуться? Обычно эта проблема решается так. Когда мы оказываемся в этой позиции в первый раз, то заменяем находящийся в ней символ на его двойник на новый вспомогательный символ, причем разные символы заменяем на разные двойники, например a на A и b на B. После этого мы выполняем какие-то действия в других местах ленты. Чтобы затем вернуться к нашей позиции, надо просто отыскать на ленте ту клетку, где находится символ A или B. Затем в данной клетке можно восстановить прежний символ, если нам больше не надо фиксировать эту позицию (именно для восстановления прежнего символа и надо было заменять разные символы на разные двойники). Воспользуемся этим приёмом в нашей задаче, выполняя следующие действия: 1. Как уже сказано, вначале записываем знак = за входным словом (см. шаг 1 выше). 2. Затем возвращаемся под первый символ входного слова (см. шаг 2 выше). 3. Далее заменяем видимый символ a на двойник A (см. шаг 3 ниже), «бежим» вправо до первой свободной клетки и записываем в неё символ a (см. шаг 4). После этого возвращаемся влево к клетке с двойником A (см. шаг 5), восстанавливаем прежний символ a и сдвигаемся вправо к следующему символу (см. шаг 6). 14
15 a a b = A a b = A a b = a A a b = a a a b = a a A b = a a A b = a a a a B = a a b a a b = a a b Теперь аналогичным образом копируем второй символ (заменяем его на A, в конец дописываем a и т.д.) и все последующие символы входного слова. 4. Когда мы скопируем последний символ входного слова и вернёмся к его двойнику (после шага 12), то затем после сдвига на одну позицию вправо мы попадём на знак = (шаг 13). Это сигнал о том, что входное слово полностью скопировано, поэтому работу МТ надо завершать. С учётом всего сказанного получаем следующую программу для МТ: a b = A B Λ q1,r,r, =,L,q2 поставить = справа от слова q2,l,l,r,q3 налево под 1-й символ q3 A,R,q4 B,R,q5,! анализ и замена очередного символа q4,r,r,r, a,q6 запись a справа q5,r,r,r, b,q6 запись b справа q6,l,l,l, a,r,q3 b,r,q3 возврат, восстановление, к след. символу Отметим, что в этой программе можно избавиться от состояния q6, если объединить его с состоянием q2, предусмотрев в q2 возврат влево как до пустой клетки, так и до символов A и B: a b = A B Λ... q2,l,l,l, a,r,q3 b,r,q3,r,q3 налево до Λ, A или B Задачи для самостоятельного решения Замечания: 1) В задачах рассматриваются только целые неотрицательные числа, если не сказано иное. 2) Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек должно быть выписано столько палочек, какова величина числа; например: 2, 5, 0 <пустое слово>. 1.1 A={a,b,c}. Приписать слева к слову P символ b (P bp). 1.2 A={a,b,c}. Приписать справа к слову P символы bc (P Pbc). 1.3 A={a,b,c}. Заменить на a каждый второй символ в слове P. 15
16 1.4 A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять). 1.5 A={a,b,c}. Оставить в слове P только последний символ (пустое слово не менять). 1.6 A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе. 1.7 A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет). 1.8 A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a. 1.9 A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет) A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8,) в двоичной системе счисления. Ответ: слово 1 (является) или слово A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например:) A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например:) A={a,b,c}. Если P слово чётной длины (0, 2, 4,), то выдать ответ a, иначе пустое слово A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.) 1.18 A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только средний символ A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём только левую половину A={a,b,c}. Приписать слева к непустому слову P его первый символ. 16
17 1.21 A={a,b}. Для непустого слова P определить, входит ли в него ещё раз его первый символ. Ответ: a (да) или пустое слово A={a,b}. В непустом слове P поменять местами его первый и последний символы A={a,b}. Определить, является P палиндромом (перевёртышем, симметричным словом) или нет. Ответ: a (да) или пустое слово A={a,b}. Заменить в P каждое вхождение a на bb A={a,b,c}. Заменить в P каждое вхождение ab на c A={a,b}. Удвоить слово P (например: abb abbabb) A={a,b}. Удвоить каждый символ слова P (например: bab bbaabb) A={a,b}. Перевернуть слово P (например: abb bba) A={0,1}. Считая непустое слово P записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.) 1.30 A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе A={0,1,2}. Считая непустое слово P записью положительного числа в троичной системе счисления, уменьшить это число на A={ }. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.) 1.33 A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, получить запись этого числа в единичной системе Пусть слово P имеет следующий вид: {... {... n m где один из знаков +, /, или, слева от которого указано n палочек, а справа m палочек. Реализовать соответствующую операцию в единичной системе счисления (в качестве ответа выдать слово, указанное справа от стрелки): а) сложение: {... + {... {... (n 0, m 0) n m n+ m б) вычитание: {... {... {... (n m 0) n m n m в) умножение: {... {... {... (n 0, m 0) n m n m г) деление нацело: {{... /... {... (n 0, m>0, k=n div m) n m k д) взятие остатка: {... {... {... (n 0, m>0, k=n mod m) n m k 17
18 е) максимум: {... {... {... (n 0, m 0, k=max(n,m)) n m k ж) минимум: {... {... {... (n 0, m 0, k=min(n,m)) k n m 1.35 A={ }. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27,). Ответ: пустое слово, если является, или слово из одной палочки иначе A={ }. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2 n A={ }. Пусть слово P является записью числа 2 n (n=0, 1, 2,) в единичной системе. Получить в этой же системе число n Пусть P имеет вид Q+R, где Q и R непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями), выдать в качестве ответа запись суммы этих чисел в той же троичной системе Пусть P имеет вид Q R, где Q и R непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями) и считая, что Q R, выдать в качестве ответа запись разности этих чисел в той же троичной системе Пусть P имеет вид Q=R, где Q и R любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе Пусть P имеет вид Q=R, где Q и R непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе Пусть P имеет вид Q>R, где Q и R непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе A={(,)}. Определить, сбалансировано ли слово P по круглым скобкам. Ответ: Д (да) или Н (нет) A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово. 2. Нормальные алгоритмы Маркова В разделе рассматриваются задачи на составление нормальных алгоритмов Маркова. Приводится краткое описание этих алгоритмов, на примерах объясняются основные приёмы их составления и предлагаются задачи для самостоятельного решения. 18
19 2.1 Краткое описание нормальных алгоритмов Маркова Подстановки Интересной особенностью нормальных алгоритмов Маркова (НАМ) является то, что в них используется лишь одно элементарное действие так называемая подстановка, которая определяется следующим образом. Формулой подстановки называется запись вида α β (читается «α заменить на β»), где α и β любые слова (возможно, и пустые). При этом α называется левой частью формулы, а β правой частью. Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Условно это можно изобразить так: P x α y R x β y Необходимые уточнения: 1. Если левая часть формулы подстановки входит в слово Р, то говорят, что эта формула применима к Р. Но если α не входит в Р, то формула считается неприменимой к Р, и подстановка не выполняется. 2. Если левая часть α входит в Р несколько раз, то на правую часть β, по определению, заменяется только первое вхождение α в Р: P x α y α z R x β y α z 3. Если правая часть формулы подстановки пустое слово, то подстановка α сводится к вычеркиванию части α из Р (отметим попутно, что в формулах подстановки не принято как-либо обозначать пустое слово): P x α y R x y 4. Если в левой части формулы подстановки указано пустое слово, то подстановка β сводится, по определению, к приписыванию β слева к слову P: P x R β x Из этого правила вытекает очень важный факт: формула с пустой левой частью применима к любому слову. Отметим также, что формула с пустыми левой и правой частями не меняет слово. Определение НАМ Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки: 19
20 α1 β1 α 2 β 2... (k 1) α k β k В этих формулах могут использоваться два вида стрелок: обычная стрелка () и стрелка «с хвостиком» (a). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» заключительной формулой. Разница между ними объясняется чуть ниже. Записать алгоритм в виде НАМ значит предъявить такой набор формул. Правила выполнения НАМ Прежде всего, задается некоторое входное слово Р. Где именно оно записано не важно, в НАМ этот вопрос не оговаривается. Работа НАМ сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р, т.е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р. На следующем шаге это слово Р берется за исходное и к нему применяется та же самая процедура, т.е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р, после чего выполняется соответствующая подстановка и получается новое слово Р. И так далее: Р Р Р Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой. Необходимые уточнения: 1. Если на очередном шаге была применена обычная формула (α β), то работа НАМ продолжается. 2. Если же на очередном шаге была применена заключительная формула (α a β), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ к входному слову. Как видно, разница между обычной и заключительной формулами подстановки проявляется лишь в том, что после применения обычной формулы работа НАМ продолжается, а после заключительной формулы прекращается. 3. Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово. Таким образом, НАМ останавливается по двум причинам: либо была применена заключительная формула, либо ни одна из формул не подошла. То и другое считается «хорошим» окончанием работы НАМ. В обоих случаях говорят, что НАМ применúм к входному слову. 20
Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая Машина Тьюринга и алгоритмы Маркова.
МАШИНА ТЬЮРИНГА В ИЗУЧЕНИИ ТЕОРИИ АЛГОРИТМОВ Лебедева Н.Ю. Шуйский филиал Ивановского государственного университета TURING MACHINE IN THE STUDY OF THE THEORY OF ALGORITHMS Lebedeva N. Yu. Shuya branch
СЛОЖЕНИЕ Прибавить 1 к числу означает получить число, следующее за данным: 4+1=5, 1+1=14 и т.д. Сложить числа 5 и значит прибавить к 5 три раза единицу: 5+1+1+1=5+=8. ВЫЧИТАНИЕ Вычесть 1 из числа означает
Задачи и решения отборочного тура олимпиады ДМиТИ 2014-2015 Все задачи, манипуляторы и решения доступны участникам на сайте олимпиады. Все предложенные задачи оценивались одинаковым числом баллов. Графы.
Машина Тьюринга 1 Машина Тьюринга математическое понятие, а не реальная вычислительная машина. MT является математической моделью вычислительного устройства. MT была предложена Аланом Тьюрингом в 1936
Решение задач по машине тьюринга онлайн >>> Решение задач по машине тьюринга онлайн Решение задач по машине тьюринга онлайн Содержимое клетки может меняться в неё можно записать другой символ или стереть
Системы счисления В наше время человек всё время сталкивается с числами. Все мы с детства знакомы с общепринятой записью чисел при помощи арабских цифр. Однако этот способ записи использовался далеко не
Реализуемый алгоритм Мы используем следующую вариацию алгоритма Евклида для вычисления НОД чисел M и N:. a M, b N; 2. t a-b, если t = 0, останов; 3. a t, b min{a,b}, переход на шаг 2. После останова НОД(M,N)
Задачи отборочного тура Олимпиады по дискретной математике и теоретической информатике с решениями (при решении конструктивных задач участник работает с эмуляторами, в решениях приведены картинки их интерфейсов)
Глава B. Компьютерная арифметика Урок B3. Двоичная арифметика Посмотрим, как вы справились с упражнениями из Урока B2. Вот их решения. Упражнения B2-2 a) Таблица размещения гирь выглядит так: в нумерации
Занятие 23 В условиях задач M, x означают соответственно описание машины Тьюринга и входного слова в том формате, который был введён на лекции (и написан в черновике учебника). Задача 23.1. Докажите, что
Раздел 6. Теория алгоритмов. Неформальное понятие алгоритма, его основные черты и свойства. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные алгоритмы. Определение нормального алгоритма (алгоритма
ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ Известно множество способов представления чисел. В любом случае число изображается символом или группой символов (словом) некоторого алфавита. Будем называть такие символы
Задания для 11 класса Отборочный этап. Первый тур 1. Кодирование информации. Системы счисления (2 балла) [Перестановки] Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно
Решение задач на тему «Представление чисел в компьютере» Типы задач: 1. Целые числа. Представление чисел в формате с фиксированной запятой. 2. Дробные числа. Представление чисел в формате с плавающей запятой.
1. Рыцари и лжецы. Логическая схема - 1. Задачи и решения очного тура Олимпиады ДмиТИ-2017-2018 За круглым столом сидят четыре человека. Каждый из них либо рыцарь, либо лжец. Рыцари всегда говорят только
Системы счисления Система счисления способ записи чисел с помощью заданного набора специальных символов (цифр). В вычислительной технике применяются позиционные системы счисления, в которых значение цифры
ЛЕКЦИЯ 3. Алгоритмы обработки одномерных массивов. Цель лекции: Знакомство с понятием массива. Приобретение навыков построения алгоритмов предназначенных для обработки одномерных массивов. 6. Алгоритмы
Демонстрационный вариант ЕГЭ 2019 г. задание 6 На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи
Введение в системы счисления А.А. Вылиток Система счисления это способ записи чисел с помощью заданного набора специальных знаков (цифр). Существуют позиционные и непозиционные системы счисления. В непозиционных
Часть III Языки, грамматики, автоматы 137 Глава 10 Языки и конечные автоматы 10.1 Язык Дика Как мы знаем, правильные скобочные структуры перечисляются числами Каталана. Выпишем все правильные скобочные
Муниципальный этап всероссийской олимпиады школьников по информатике Москва, декабря 0 г. Задания для 7 8 классов Каждая задача оценивается в 0 баллов. Итоговый балл выставляется как сумма баллов за задачи
Виртуальные машины Введение Свыше сорока лот назад выдающийся американский математик Эмиль Л. Пост опубликовал в «Журнале символической логики» статью «Финитные комбинаторные процессы, формулировка!» (ее
Югорский физико-математический лицей ВП Чуваков Задача С6 (Теория чисел на ЕГЭ) Учебно-методическое пособие Ханты-Мансийск 0 ВП Чуваков Задача С6 (Теория чисел на ЕГЭ): Учебнометодическое пособие, - Ханты-Мансийск,
9 КЛАСС 1. В одной из клеток бесконечной клетчатой бумаги находится робот, которому могут быть отданы следующие команды: вверх (робот перемещается на соседнюю клетку сверху); вниз (робот перемещается на
Системы счисления Система счисления это способ записи чисел с помощью заданного набора специальных знаков (цифр). Существуют позиционные и непозиционные системы счисления. В непозиционных системах вес
Системы счисления Система счисления способ описания чисел с помощью знаков определенного алфавита по известным правилам. Позиционные системы счисления В позиционной системе счисления значение цифры зависит
К. Поляков, 009-06 6- (базовый уровень, время 4 мин) Тема: Поиск алгоритма минимальной длины для исполнителя. Что нужно знать: исполнитель это человек, группа людей, животное, машина или другой объект,
Лекция 5 Основы представления информации в цифровых автоматах Позиционные системы счисления Системой счисления называется совокупность приемов и правил для записи чисел цифровыми знаками. Любая предназначенная
Элементы теории сложности Машина Тьюринга Алан Тьюринг (23.06.1912-7.06.1954) (Alan Mathison Turing) Английский математик, логик, криптограф. В 1936 году предложил абстрактную вычислительную «Машина Тьюринга»,
Министерство образования и науки Российской Федерации Государственное образовательное учреждение профессионального образования Российской Федерации «Ростовский государственный университет» М. Э. Абрамян
10 КЛАСС 1. Действительные числа удовлетворяют соотношениям: Найдите все возможные тройки чисел, где Решение. Заметим, что Обозначим и Вычитая друг из друга эти равенства, получим Предположим, что все
Приложение к статье Горбунов К.Ю., Любецкий В.А. «Линейный алгоритм минимальной перестройки структур» Доказательство леммы 3. Жестким назовём блок, ограниченный с обеих сторон общими генами, полужёстким
Приложение 1 Практикум к главе 2 «Представление информации в компьютере» Практическая работа к п. 2.1 Пример 2.1. Представьте в виде разложения по степеням основания числа 2466,675 10, 1011,11 2. Для десятичного
Заочный физико-математический лицей «Авангард» Е. Н. Филатов АЛГЕБРА 8 Экспериментальный учебник Часть 1 МОСКВА 2016 СОДЕРЖАНИЕ 1. Делимость. 2. Чёт нечет 3. Множества. 4. Забавные задачи. 5. Комбинаторика
Задачник по информатике ученика (цы) 11 физико-математического класса средней школы 36 г.владимира Часть II 2016-2017 г. 2 1. Алгоритмизация. 1.1 Предлагается некоторая операция над двумя произвольными
Тема 7. Представление информации в ЭВМ.. Единицы информации. Бит - (bit-biry digit - двоичный разряд) наименьшая единица информации - количество её, необходимое для различения двух равновероятных событий.
И. В. Яковлев Материалы по математике MathUs.ru Содержание Десятичная запись 1 Всероссийская олимпиада школьников по математике................ 1 2 Московская математическая олимпиада........................
Тема 1: Системы линейных уравнений А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для физиков-инженеров
Глава 5 Элементы теории алгоритмов 31 Уточнение понятия алгоритма Ключевые слова: алгоритм теория алгоритмов универсальный исполнитель машина Тьюринга машина Поста нормальный алгорифм Маркова Зачем нужно
Решение задач на тему «Представление чисел в компьютере». Типы задач. 1. Целые числа. Представление чисел в формате с фиксированной запятой. 2. Дробные числа. Представление чисел в формате с плавающей
А. Шень Игры и стратегии с точки зрения математики, МЦНМО Простые игры и классификация позиций На столе лежит 12 спичек. Играющие по очереди могут взять от одной до трёх спичек. Кто не может сделать ход
Теория алгоритмов 79 3.2. Нормальные алгоритмы j Пусть A алфавит, не содержащий символов. и. Обыкновенной формулой подстановок называется запись вида P Q, где P и Q некоторые слова в алфавите A. Заключительной
ЛЕКЦИЯ 2. Алгоритмы циклической структуры. Цель лекции: Знакомство с понятием алгоритма циклической струк туры. Приобретение навыков построения алгоритмов циклической с трук т уры. 5. Алгоритмы циклической
Лекции по Математике. Вып. ТММ-1 Ю. В. Чебраков ТЕОРИЯ МАГИЧЕСКИХ МАТРИЦ Санкт-Петербург, 2010 УДК 511+512 ББК 22 Ч345 Р е ц е н з е н т ы: Доктор физико-математических наук, профессор С.-Петерб. техн.
Практическая работа. Формы представления числовой информации на компьютере. Часть I. Системы счисления. Под системой счисления понимается способ представления любого числа с помощью некоторого алфавита
Московский физико-технический институт Факультет инноваций и высоких технологий Математическая логика и теория алгоритмов, осень 2018 Семинар 1: язык записи формальных утверждений, с решениями некоторых
Лекция 16. Универсальная машина Тьюринга Дискретная математика, ВШЭ, факультет компьютерных наук (Осень 2014 весна 2015) Важнейшим свойством вычислимых функций является существование универсальной вычислимой
16 (повышенный уровень, время мин) Тема: Кодирование чисел. Системы счисления. Что нужно знать: принципы кодирования чисел в позиционных системах счисления чтобы перевести число, скажем, 15, из системы
2015 Регулярные выражения Решения задач отборочного тура (два варианта) Вариант 1 Постройте регулярное выражение, описывающее множество слов из букв a и b, из которого удалены все слова, задаваемые регулярным
В логике с помощью понятия машины Тьюринга строится теория неразрешимых проблем, однако в вычислительной практике чаще приходится иметь дело с разрешимыми, но “трудно решаемыми” проблемами. Выбирая и здесь в качестве вычислительной модели машину Тьюринга, мы руководствуемся тем, что она проста и допускает те же языки, что и компьютер, причем сложность вычислений на машине Тьюринга полиномиальна от числа шагов компьютера.
Машина Тьюринга представляет собой абстрактную вычислительную машину, состоящую из управления с конечным числом состояний и бесконечной ленты, разделенной на ячейки, в каждой из которых хранится один ленточный символ, и одна из ячеек является текущей позицией ленточной головки. Формальная запись машины Тьюринга - это упорядоченный набор M = (X, Q, q 0 , F, I), где
X – внешний алфавит символов (букв на ленте), включающий символ L;
Q – конечный алфавит внутренних состояний;
q 0 – инициальное состояние (начало работы), q 0 Î Q;
F– множество заключительных состояний, FÌ Q;
I - множество инструкций, или машинных команд, каждая из которых принадлежит множеству (Q \ F) ´ X ´ {®} ´ Q ´ X ´ {R,L,S}.
Переходы осуществляются на основе текущего состояния и обозреваемого считывающей головкой символа к следующему состоянию, переписыванию символа и сдвигу головки (вправо R, влево L, на месте S).
Можно определить функцию переходов
d: (Q \ F) ´ X* ® Q ´ X* ´ {R,L,S}, где X* -слова в алфавите X.
В случае однозначной функции d машина Тьюринга называется детерминированной машиной Тьюринга.
Текущей конфигурацией машины Тьюринга называют цепочку значащих (отличных от L) символов, записанных на ленте в данный момент времени, вместе с символом состояния, помещенным в цепочку перед обозреваемым символом.
Останов (завершение работы) происходит в заключительном состоянии или когда левая часть (до ®) ни одной из машинных команд не содержится в полученной конфигурации. Говорят, что машина допускает вход, если она останавливается на нем в заключительном состоянии.
В качестве примера рассмотрим работу детерминированной машины Тьюринга, вычисляющей функцию ïm - nï. Упорядоченную пару натуральных чисел (m,n) представляем как слово 0 m 10 n в алфавите X \ {L} = {0,1}, ячейки слева и справа от которого содержат символ L.
Q 0 0 ® LRq 1 Состояния Символ
Q 1 0 ® 0Rq 1 0 1 L
q 1 1 ® 1Rq 2 q 0 LRq 1 1Sq 5 0Sq 5
q 2 0 ® 1Lq 3 q 1 0Rq 1 1Rq 2 ¾
q 2 1 ® 1Rq 2 q 2 1Lq 3 1Rq 2 LLq 4
q 3 1 ® 1Lq 3 q 3 0Lq 3 1Lq 3 LRq 0
q 3 0 ® 0Lq 3 q 4 0Lq 4 LLq 4 0Sq 5
q 3 L ® LRq 0 q 5 ¾ LRq 5 ¾
q 2 L ® LLq 4 *
q 4 1 ® LLq 4 Таблица 1. Программа вычисления функции ôm - nô,
q 4 0 ® 0Lq 4 где функция переходов задается таблицей
q 0 1 ® 1Sq 5 *
Машина Тьюринга M допускает (отвергает) слово wÎ X * , если она останавливается на нем, придя в допускающее (заключительное) состояние. Машина допускает язык LÍ X * , если она допускает все слова языка L. Машина M распознает язык LÍ X * , если она допускает все слова из L и останавливается на словах из X * \ L, не находясь в заключитель ном состоянии. Языки, допускаемые машиной Тьюринга, назовем рекурсивно перечислимым.
Язык L допускается (распознается) за полиномиальное время , если существует машина M, которая допускает (распознает) язык L, причем всякое слово wÎ L допускается (распознается) за время O(n k), где n – длина слова w, а k – не зависящее от w число.
Теперь можно определить класс P, как множество языков LÍ {0,1} * , распознаваемых за полиномиальное время.
Теорема. Класс P есть множество языков, допускаемых за полиномиальное время.
Доказательство. В одну сторону тривиально, если машина M распознает язык L, то она и допускает язык L. Обратно, пусть язык L допускается машиной M за время O(n k), т.е. существует константа c, что любое слово из L длины n допускается не более, чем за T = c×n k шагов. С другой стороны, слова, не принадлежащие L, не допускаются ни за какое время. Построим машину M * , которая на слове w моделирует не более Т = c×n k шагов машины M и останавливается, выдавая 1, если M(w)=1, в противном случае - останавливается, сделав Т = c×n k шагов, выдавая на выход 0. Таким образом, машина M * распознает язык L и сложностной класс P можно рассматривать, как множество языков, допускаемых за полиномиальное время.
Многоленточная машина Тьюринга.
Для имитации работы компьютера используются многоленточные машины Тьюринга. В начальной конфигурации многоленточной машины на первой ленте размещается вход (конечная последовательность символов, куда не входит L), все клетки остальных лент содержат символ L, считывающие головки всех лент находятся в начальном состоянии.
За один переход осуществляются следующие действия:
Управление переходит в новое состояние,
На каждой ленте записывается новый (или тот же) символ;
Считывающие головки каждой из лент независимо сдвигаются на одну ячейку (R,L,S).
Языки, допускаемые одноленточными машинами Тьюринга, рекурсивно перечислимы. Допустимы ли многоленточными машинами не рекурсивно перечислимые языки? Ответ в следующей теореме.
Теорема. Каждый язык L, допускаемый многоленточной машиной Тьюринга, рекурсивно перечислим.
Доказательство. Одноленточную машину Тьюринга можно представить, как многодорожечную , задавая ее аргументы в виде кортежей. При этом одна дорожка хранит данные, а другая отметку. Смоделируем k - ленточную машину M как многодорожечную машину N, содержащую 2k дорожек, где каждая вторая содержит маркер, указывающий позицию головки соответствующей ленты. Машина N должна посетить каждый из маркеров головок k лент и изменить соответствующим образом символ, представляющий соответствующую ленту, перемещая маркер в том направлении, как это происходило на соответствующей ленте. Наконец, N изменяет состояние М, записанное в конечном управлении N. В качестве допускающих состояний N выбираются все те состояния, в которых запоминалось допускающее состояние M. Таким образом, машина M и N одновременно допускают язык L. Но все языки, допускаемые одноленточной машиной N, рекурсивно перечислимы, поэтому рекурсивно перечислимы все языки, допускаемые многоленточной машиной M.
Теорема. Время, необходимое одноленточной машине N для имитации n переходов k-ленточной машины M, есть O(n 2).
Доказательство. После n переходов машины M маркеры головок разделены не более, чем 2n клетками, так что и машине N надо сдвинуться не более, чем на 2n клеток вправо, чтобы найти все маркеры головок. Теперь ей надо совершить проход влево, изменяя содержимое M лент и сдвигая головочные маркеры, что потребует не более 2n сдвигов влево плюс не более 2k переходов для изменения направления движения и записи маркера в клетку. Таким образом, число переходов N для имитации одного из переходов машины M не более 4n+2k, т.е. O(n). Для n переходов требуется времени в n раз больше, т.е. O(n 2).
Различие во времени вычисления на машинах с разным числом лент сохраняет полиномиальную сложность и для одноленточной машины ограничено с×T(n) 2 , а емкость - с×S(n) (для входа длины n), где T(n), S(n) – параметры k-ленточных машин. Зависимость между емкостью и временем для k-ленточных машин линейная: S £ kT; для входа w длины n
Недетерминированные машины Тьюринга.
По причинам, которые вскоре будут понятны, недетерминированные машины Тьюринга являются ключевым понятием в теории NP-полных задач. Недетерминированная машина Тьюринга отличается от обычной (детерминированной) машины Тьюринга тем, что может иметь более одного перехода от текущей конфигурации к следующей. Недетерминированная машина допускает слово w, если существует хотя бы одна цепочка конфигураций, ведущая от начальной конфигурации в заключительную. Существование других последовательностей конфигураций, не ведущих в заключительное (допускающее) состояние не имеет значение. Работу недетерминированной машины на входе w можно представить в виде дерева, где каждый путь из корня w в лист представляет некоторую последовательность возможных шагов машины. Если s w кратчайшая последовательность возможных шагов работы машины, которая оканчивается допускающей конфигурацией, то ½s w ½ есть время, затраченное машиной на обработку входа w. Если на входе w никакая последовательность не приводит к допускающей конфигурации, то время, затраченное на обработку w не определено. Считается, что недетерминированная машина Тьюринга на входе w параллельно выполняет все возможные последовательности шагов, пока не достигнет допускающего состояния или окажется, что ее программа не применима к полученной конфигурации.
Остается открытым вопрос, существуют ли языки, допускаемые недетерминированной машиной Тьюринга с данной временной и емкостной сложностью и не допускаемые никакой детерминированной машиной с той же сложностью.
Недетерминированные машины Тьюринга допускают те же языки, что и детерминированные. Однако, надо заметить, что последним приходится за это расплачиваться сильным увеличением временной сложности.
Обозначим через L(M) множество всех слов wÎX*, допускаемых машиной M, L(M) называют языком машины M.
Теорема. Если M недетерминированная машина с полиномиальной временной сложностью T(n), то существует детерминированная машина M ’ , с L(M ’ ) = L(M) и временной сложностью O(c T(n)).
Доказательство. Доказательство основывается на том, что для любой недетерминированной машины Тьюринга M строится детерминированная машина M ’ , которая исследует последовательности конфигураций (пути в дереве недетерминированной машины) и если находит хотя бы одну с допускаемым состоянием, то сама переходит в допускаемое состояние. Обследованные конфигурации помещаются в очередь, длины k (k=1,2…) Построим детерминированную многоленточную машину M ’ , моделирующую недетерминированную машину M. Первая лента машины M ’ хранит последовательность конфигураций машины M и метку на текущее состояние последней. Записи слева от метки предполагаются исследованными и их в дальнейшем игнорируют. Конфигурации справа рассматриваются в порядке очереди. Программа машины M хранится в конечном управлении M ’ . Обработка текущей конфигурации на первой ленте состоит в следующем:
Машина M ’ проверяет состояние и обозреваемый символ и, если состояние допускающее, также переходит в допускающее состояние.
Если состояние не допускающее и из данной конфигурации есть k переходов, то M ’ использует вторую ленту для создания k копий, которые записываются в конце очереди на ленте 1.
M ’ изменяет k конфигураций в соответствии с программой машины M.
M ’ перемещает отметку текущей конфигурации на следующую справа и цикл повторяется с шага 1.
Допустим, что m есть максимальное число выборов машины M в любой конфигурации. Тогда существует одно начальное состояние M, не более m конфигураций, достижимых за 1 шаг, не более m 2 конфигураций, достижимых за 2 шага и т.д. Таким образом, после n переходов машина M может достичь не более 1+ m +m 2 +…+m n £ n×m n конфигураций. Порядок, в котором машина M ’ исследует конфигурации, называется “поиском в ширину”, т.е. M ’ исследует все достижимые конфигурации машины M за 0 шагов, достижимые за 1 шаг и т.д.
Допускающая конфигурация машины M будет рассмотрена машиной M ’ в числе первых n×m n конфигураций. Таким образом, если машина M допускает, то машина M ’ также допускает, т.е. L(M) = L(M ’ ).
Отметим, что работа построенной детерминированной машины M ’ может потребовать экспоненциально большего времени, чем время работы недетерминированной машины M, которую она моделирует. Разница между полиномиальным и экспоненциальным временем - это граница того, что можно решить с помощью компьютера, а что практически нерешаемо.
Теорема. Если M недетерминированная машина Тьюринга с емкостной сложностью S(n), то найдется детерминированная машина Тьюринга M ’ с емкостной сложностью O(S 2 (n)) и L(M ’ ) = L(M).
Доказательство. Пусть M недетерминированная машина Тьюринга (возможно k-ленточная) с емкостной сложностью S(n). Тогда число различных конфигураций, в которые машина M может попасть из начальной с входом длины n, не превосходит некоторого числа c S (n) , точнее ½Q½(½X½+1) k S(n) (S(n)) k , где k – число лент. Тогда число переходов от конфигурации C 1 к конфигурации C 2 (С 1 ├ С 2) на любой из лент не превосходит c S (n) . Можно выяснить, существует ли переход С 1 ├ С 2 за 2i шагов, проверив для всех C 3 существует ли переход С 1 ├ С 3 и С 3 ├ С 2 за i шагов. После каждого обращения к процедуре число i уменьшается вдвое.
Идея моделирования машиной M ’ работы машины M приведена в доказательстве предыдущей теоремы. Стратегия работы машины M ’ -
установить приведет ли начальная конфигурация C 0 к какой-нибудь допускающей конфигурации C f . Чтобы найти верхнюю емкостную границу для машины M ’ , расположим конфигурации (длины O(S(n))) на стеках того же размера. В каждый момент времени число фрагментов стека не превосходит 1+ log éc S (n) ù , т.е. O(S(n)). Для всего стека машины M потребуется O(S 2 (n)) ячеек.
Теорема. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга M = (X, Q, q 0 , F, I) с временной сложностью T(n), то он допускается одноленточной недетерминированной машиной с временной сложностью O(T 2 (n)).
Доказательство. Пусть M 1 одноленточная недетерминированная машина Тьюринга, имеющая на ленте 2k дорожек, т.е. ленточные символы машины M 1 представляются 2k-членными кортежами, в которых на нечетных местах стоят символы алфавита X, а на четных – либо символ L, либо маркер #. Дорожки с нечетными номерами соответствуют k лентам машины M, а каждая дорожка с четным номером 2j содержит символ L во всех ячейках, кроме одной, где стоит маркер #, отмечающий положение головки машины M на ленте j, которой соответствует дорожка 2j-1. Машина M 1 моделирует один шаг работы машины M следующим образом. Допустим, что вначале головка машины M 1 обозревает клетку, содержащую самую левую головку машины M.
Головка машины M 1 движется вправо, пока не минует все k маркеров положений головок на дорожках с четными номерами. При этом M 1 запоминает в своем состоянии символы, обозреваемые каждой из головок машины M. Теперь M 1 делает недетерминированное развлетвление, исходя из состояния машины M, которое машина M 1 запомнила в своем состоянии, и обозреваемых машиной M на лентах символов, которые машина M 1 также нашла.
Выбрав для моделирования шаг машины M, машина M 1 изменяет в соответствии с ним состояние машины M, которое она помнит в своем состоянии. Затем M 1 сдвигает свою головку влево и проходит все маркеры, изменяя ленточный символ на дорожке над маркером и сдвигая маркер не более чем на одну клетку (L,R,S).
Машина M 1 промоделировала один шаг работы машмны M. Действия машины M 1 на этом шаге детерминированы. Ее головка находится правее левого маркера не более чем на две ячейки. Начиная с этого маркера цикл можно повторить.
Если машина M допускает цепочку w длины n, то совершает при этом не более T(n) переходов. Очевидно, что в последовательности из T(n) шагов головки мащины M могут разойтись не более чем на T(n) клеток, и, значит, M 1 может смоделировать один шаг этой последовательности не более чем за O(T(n)) своих шагов. Таким образом, M 1 допускает цепочку w, выполняя не более чем O(T 2 (n)) переходов. Отсюда следует, что M 1 допускает язык L и имеет временную сложность O(T 2 (n)).
Следствие 1. Если язык допускается k-ленточной детерминированной машиной Тьюринга с временной сложностью T(n), то он допускается одноленточной детерминированной машиной Тьюринга с временной сложностью O(T 2 (n)).
Следствие 2 . Если язык L допускается k-ленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n).
Следствие 3. Если язык допускается k-ленточной детерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной детерминированной машиной Тьюринга с емкостной сложностью S(n).
Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.
К основным компонентам вычислительной машины относятся оперативная память и процессор. Программы и данные, представленные в двоичном алфавите, помещаются в память. При выполнении программы отдельные ее команды и нужные данные извлекаются из памяти в процессор и наоборот – значения, получаемые при выполнении команд, записываются в ячейки памяти.
Память состоит из некоторого числа запоминающих ячеек (регистров), предназначенных для промежуточного хранения значений операндов и для хранения другой информации, необходимой для выполнения команд, регистров для управления запоминающими ячейками, адресов ячеек и полей самих ячеек.
Процессор состоит из устройства управления (УУ) и арифметического устройство (АУ). Устройство управления содержит счетчик тактов, команд и т.д., вырабатывает управляющие сигналы для выполнения команд, передачи данных и т.д. Процессор содержит регистры операндов, линии связи и линии задержки для непосредственной реализации процессов вычислений.
Наряду с процессором и памятью компьютеру необходимы еще устройства ввода/вывода.
Имитация машины Тьюринга на компьютере. Пусть M - машина Тьюринга, одним из составляющих которой является ее конечное управление. Поскольку M имеет конечное число состояний и конечное число правил перехода, программа компьютера может закодировать состояния в виде цепочек символов, как и символы ее внешнего алфавита, и использовать таблицу переходов машины M для преобразования цепочек. Бесконечную ленту машины Тьюринга можно имитировать сменными дисками, размещаемыми в двух магазинах, соответственно для данных, расположенных слева и справа от считывающей головки на ленте. Чем дальше в магазине расположены данные, тем дальше они от головки на ленте.
Для имитации компьютера на машине Тьюринга существенны две вещи:
Существуют ли инструкции, выполняемые компьютером, и недоступные для машины Тьюринга;
Работает ли компьютер быстрее машины Тьюринга, т.е. более, чем полиномиальная зависимость разделяет время работы компьютера и машины Тьюринга при решении какой-то проблемы.
Неформальная модель реального компьютера :
Память, состоящая из последовательности слов и их адресов. В качестве адресов будут использоваться натуральные числа 0,1, …;
Программа компьютера, записанная в слова памяти, каждое из которых представляет простую инструкцию. Допускается “непрямая адресация” по указателям;
Каждая инструкция использует конечное число слов и изменяет значение не более одного слова;
Имеются слова памяти с быстрым доступом (регистры), но скорость доступа к различным словам влияет лишь на константный сомножитель, что не искажает полиномиальную зависимость.
Возможная конструкция машины Тьюринга для имитации компьютера
представлена на рис.
Рис стр 369
Машина имеет несколько лент. Первая лента представляет всю память компьютера – адреса и значения (в двоичной системе). Адреса заканчиваются маркером *, значения – маркером #. Начало и конец записей 1-й ленты обозначаются маркером $. Вторая лента – “счетчик инструкций”, содержит одно двоичное целое, представляющее одну из позиций считываюшей головки на первой ленте, адрес инструкции, которая должна быть выполнена следующей. Третья лента содержит адрес и значение по нему после того, как этот адрес устанавливается на первой ленте. Для выполнения инструкции машина Тьюринга должна найти значение по одному или нескольким адресам памяти, где хранятся данные, участвующие в вычислении. Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения. Значение по этому адресу копируется на третью ленту и перемещается на нужное место, как правило, по одному из начальных адресов, представляющих регистры компьютера. Четвертая лента имитирует входной файл. Пятая лента - рабочая память, служит для выполнения вычислений. Допускающая инструкция машины Тьюринга соответствует выводу на печать в выходном файле.
Функционирование такой имитирующей машины:
1.Найдя на 1-й ленте адрес, совпадающий с номером инструкции на 2-й ленте, исследуем значение по нему и копируем на 3-ю ленту. Первые биты инструкции задают действие (копировать, вставить, ветвиться и т.д.), оставщиеся биты – адрес или адреса, используемые в этом действии.
2. Если в инструкции содержится значение по некоторому адресу, то этот адрес копируется на 3-ю ленту, а позиция инструкции на 2-ю дорожку 1-й ленты.
a) скопировать по другому адресу;
Второй адрес извлекается из инструкции, помещается на 3-ю ленту, находится на 1-й ленте и значение по нему копируется в зарезервированное для него пространство. Если для нового значения надо больше (меньше) памяти, чем для старого, пространство изменяется путем сдвига, а именно,
(1) на рабочую ленту копируется часть ленты справа от того места, куда надо поместить новое значение;
(2) новое значение записывается на 1-ю ленту;
(3) рабочая часть копируется обратно на 1-ю ленту справа от нового значения.
b) прибавить найденное значение по другому адресу;
Ищем второй адрес на первой ленте, выполняем сложение значения по этому адресу и записанному на 3-й ленте.
c) перейти к выполнению инструкции по адресу, записанному на 3-й ленте, для чего лента 3 копируется на ленту 2, и цикл инструкций начинается снова.
4. Выполнив инструкцию (не являющуюся переходом), прибавляем 1 к счетчику на ленте 2 и вновь начинаем цикл инструкции.
Теперь надо убедиться, что если проблему можно решить за полиномиальное время на компьютере, то ее можно решить за полиномиальное время на машине Тьюринга и наоборот. Как следует из доказанных выше теорем, достаточно использовать многоленточную машину Тьюринга, так как различие во времени работы одноленточной и многоленточной машин Тьюринга полиномиально.
Время работы машины Тьюринга, имитирующей компьютер
Введем следующие ограничения на модель компьютера:
Ни одна компьютерная инструкция не должна порождать слово, длиннее, чем на 1 бит, своих операндов.
Инструкция, применяемая к словам длины m должна выполняться не более, чем за 0(m 2) шагов на многоленточной машине Тьюринга.
Назовем такие операции допустимыми.
Этим условиям удовлетворяют сложение, сдвиг на 1 бит, сравнение значений, которые выполняются на многоленточной машине Тьюринга за 0(m) шагов. А также умножение m-битовых целых, если его имитировать с помощью m последовательных сложений со сдвигами на 1 бит влево. Время выполнения операции умножения будет пропорционально квадрату длины сомножителей. .
Теорема. Для компьютера, обладающего указанными свойствами, описанная выше модель машины Тьюринга может имитировать m шагов компьютера не более, чем за 0(m 3)шагов.
Доказательство. Вначале первая лента содержит только программу компьютера, длина которой не зависит от n (числа шагов выполнения инструкций). Наибольшее из компьютерных слов или адресов, встречающихся в программе, обозначим через c, а через d - число слов программы.
После выполнения n шагов компьютер не может породить слово, длиннее c+n, и не может создать или использовать адрес, занимающий больше c+n битов. Каждая инструкция порождает не более одного нового адреса, получающего значение, поэтому после выполнения n инструкций имеем d+n адресов. Каждый адрес-значение занимает не более 2(c+n) +2 разрядов, а после выполнения n инструкций не больше 2(d+n)(c+n+1), или 0(n 2)
Для просмотра адресов одной инструкции компьютера требуется времени 0(n 2), слова имеют длину 0(n), а инструкции выполняются машиной Тьюринга за время 0(n 2), сдвиг для создания пространства для нового слова включает копирование данных объемом 0(n 2) с ленты 1 на рабочую ленту и обратно. Таким образом, машина Тьюринга имитирует один шаг компьютера за 0(n 2) своих шагов, а n шагов можно проимитировать за 0(n 3) шагов машины Тьюринга.
Теорема. Выполнение n шагов работы компьютера можно проимитировать на одноленточной машине Тьюринга не более чем за 0(n 6) шагов.
Таким образом, машина Тьюринга может имитировать память и управление реального компьютера, используя только одну ленту для записи всех элементов памяти и их содержимого – регистров, основной памяти, дисков и других запомиинающих устройств. Отсюда можно быть уверенным, что все, не выполнимое машиной Тьюринга, не может быть вычислено и компьютером.
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель
. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга
.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Что собой представляет машина Тьюринга?
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
- Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а 0) должна представлять собой пустой символ.
- Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q 1) должно быть начальным (запускающим программу). Еще одно из состояний (q 0) должно быть конечным (завершающим программу) – состояние останова.
- Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Передвигаться на одну ячейку влево или вправо.
- Менять свое внутреннее состояние.
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Пример работы машины Тьюринга
Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.
Примечание:
длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).
Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):
Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние q 2 (команды которого совпадают с командами q 1 предыдущей программы).
Машина Тьюринга - одно из самых интригующих и захватывающих интеллектуальных открытий 20-го века. Это простая и полезная абстрактная модель вычислений (компьютерных и цифровых), которая является достаточно общей для воплощения любой компьютерной задачи. Благодаря простому описанию и проведению математического анализа она образует фундамент теоретической информатики. Это исследование привело к более глубокому познанию цифровых компьютеров и исчислений, включая понимание того, что существуют некоторые вычислительные проблемы, не решаемые на общих пользовательских ЭВМ.
Алан Тьюринг стремился описать наиболее примитивную модель механического устройства, которая имела бы те же основные возможности, что и компьютер. Тьюринг впервые описал машину в 1936 году в статье "О вычислимых числах с приложением к проблеме разрешимости", которая появилась в Трудах Лондонского математического общества.
Машина Тьюринга является вычислительным устройством, состоящим из головки чтения/записи (или «сканера») с бумажной лентой, проходящей через него. Лента разделена на квадраты, каждый из которых несет одиночный символ - "0" или "1". Назначение механизма состоит в том, что он выступает и как средство для входа и выхода, и как рабочая память для хранения результатов промежуточных этапов вычислений. Из чего состоит устройство Каждая такая машина состоит из двух составляющих: Неограниченная лента. Она является бесконечной в обе стороны и разделена на ячейки. Автомат – управляемая программа, головка-сканер для считывания и записи данных. Она может находиться в каждый момент в одном из множества состояний.
Каждая машина связывает два конечных ряда данных: алфавит входящих символов A = {a0, a1, ..., am} и алфавит состояний Q = {q0, q1, ..., qp}. Состояние q0 называют пассивным. Считается, что устройство заканчивает свою работу, когда попадает именно на него. Состояние q1 называют начальным - машина начинает свои вычисления, находясь на старте в нем. Входное слово располагается на ленте по одной букве подряд в каждой позиции. С обеих сторон от него располагаются только пустые ячейки.
Как работает механизм
Машина Тьюринга имеет принципиальное отличие от вычислительных устройств – ее запоминающее приспособление имеет бесконечную ленту, тогда как у цифровых аппаратов такое устройство имеет полосу определенной длины. Каждый класс заданий решает только одна построенная машина Тьюринга. Задачи иного вида предполагают написание нового алгоритма. Управляющее устройство, находясь в одном состоянии, может передвигаться в любую сторону по ленте. Оно записывает в ячейки и считывает с них символы конечного алфавита. В процессе перемещения выделяется пустой элемент, который заполняет позиции, не содержащие входные данные. Алгоритм для машины Тьюринга определяет правила перехода для управляющего устройства. Они задают головке записи-чтения такие параметры: запись в ячейку нового символа, переход в новое состояние, перемещение влево или вправо по ленте.
Свойства механизма
Машина Тьюринга, как и другие вычислительные системы, имеет присущие ей особенности, и они сходны со свойствами алгоритмов: Дискретность. Цифровая машина переходит к следующему шагу n+1 только после того, как будет выполнен предыдущий. Каждый выполненный этап назначает, каким будет n+1. Понятность. Устройство выполняет только одно действие для одной же ячейки. Оно вписывает символ из алфавита и делает одно движение: влево или вправо. Детерминированность. Каждой позиции в механизме соответствует единственный вариант выполнения заданной схемы, и на каждом этапе действия и последовательность их выполнения однозначны. Результативность. Точный результат для каждого этапа определяет машина Тьюринга. Программа выполняет алгоритм и за конечное число шагов переходит в состояние q0. Массовость. Каждое устройство определено над допустимыми словами, входящими в алфавит. Функции машины Тьюринга В решении алгоритмов часто требуется реализация функции. В зависимости от возможности написания цепочки для вычисления, функцию называют алгоритмически разрешимой или неразрешимой. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В – слова в рамках двоичного кодового алфавита В={0.1}. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.-
Программа для устройства
Программы для механизма Тьюринга оформляются таблицами, в которых первые строка и столбец содержат символы внешнего алфавита и значения возможных внутренних состояний автомата - внутренний алфавит. Табличные данные являются командами, которые воспринимает машина Тьюринга. Решение задач происходит таким образом: буква, считываемая головкой в ячейке, над которой она в данный момент находится, и внутреннее состояние головки автомата обусловливают, какую из команд необходимо выполнять. Конкретно такая команда находится на пересечении символов внешнего алфавита и внутреннего, находящихся в таблице.
Составляющие для вычислений
Чтобы построить машину Тьюринга для решения одной определенной задачи, необходимо определить для нее следующие параметры. Внешний алфавит. Это некоторое конечное множество символов, обозначающихся знаком А, составляющие элементы которого именуются буквами. Один из них - а0 - должен быть пустым. Для примера, алфавит устройства Тьюринга, работающего с двоичными числами, выглядит так: A = {0, 1, а0}. Непрерывная цепочка букв-символов, записываемая на ленту, именуется словом. Автоматом называется устройство, которое работает без вмешательства людей. В машине Тьюринга он имеет для решения задач несколько различных состояний и при определенно возникающих условиях перемещается из одного положения в другое. Совокупность таких состояний каретки есть внутренний алфавит. Он имеет буквенное обозначение вида Q={q1, q2...}. Одно из таких положений - q1 - должно являться начальным, то есть тем, что запускает программу. Еще одним необходимым элементом является состояние q0, которое является конечным, то есть тем, что завершает программу и переводит устройство в позицию остановки.
Таблица переходов.
Эта составляющая представляет собой алгоритм поведения каретки устройства в зависимости от того, каковы в данный момент состояние автомата и значение считываемого символа.-
Алгоритм для автомата
Кареткой устройства Тьюринга во время работы управляет программа, которая во время каждого шага выполняет последовательность следующих действий: Запись символа внешнего алфавита в позицию, в том числе и пустого, осуществляя замену находившегося в ней, в том числе и пустого, элемента. Перемещение на один шаг-ячейку влево или же вправо. Изменение своего внутреннего состояния. Таким образом, при написании программ для каждой пары символов либо положений необходимо точно описать три параметра: ai – элемент из выбранного алфавита A, направление сдвига каретки ("←” влево, "→” вправо, "точка” - отсутствие перемещения) и qk - новое состояние устройства. К примеру, команда 1 "←” q2 имеет значение "заместить символ на 1, сдвинуть головку каретки влево на один шаг-ячейку и сделать переход в состояние q2”.
Загрузить клиент электронной почты The Bat!
Настройка вибрации в Android: подробное описание и видеоинструкция Приложение вибро
Простые варианты отключения вибрации на Айфоне