Введение в теорию алгоритмов


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

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

Вплоть до 30-х годов ХХ века понятие алгоритма оставалось интуитивно понятным, имело скорее методологическое, а не математическое значение. Известно много ярких алгоритмов, таких, например, как алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или многочленов, алгоритм Гаусса решения системы линейных уравнений и др. Эти проблемы были решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма.

Алгоритм – это точное и понятное предписание исполнителю о том, какие действия и в каком порядке нужно выполнить, чтобы решить любую задачу из класса однотипных задач.

Понятие алгоритма является фундаментальным, приведенная выше формулировка не является строгим определением и требует некоторого уточнения, конкретизирующего, в частности, что означают слова «точное», «понятное». Формулируются требования, которым должны удовлетворять алгоритмы (свойства алгоритмов).

Свойства алгоритмов

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

2. Понятность. Алгоритм должен быть сформулирован на языке, понятном исполнителю, т. е. не должен содержать действий, не входящих в систему команд исполнителя (СКИ – совокупность всех команд, которые может выполнять данный исполнитель).

3. Массовость. Алгоритм должен представлять собой единый метод решения бесконечной серии однотипных задач.

4. Результативность. Исполнение алгоритма за конечное число шагов должно приводить к искомому ответу – решению задачи либо к информации о том, что задача решения не имеет.

5. Дискретность. Шаги алгоритма должны быть дискретны, т. е. каждый шаг должен быть четко отделен от другого, за исполнением каждого шага, кроме последнего, должен однозначно определяться следующий и между этими шагами не должно быть других действий.

Предпосылки возникновения необходимости уточнения (формализации) понятия алгоритма и возникновения теории алгоритмов

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

Но к началу ХХ века стали усложняться объекты, с которыми оперировали алгоритмы. Появилась необходимость выполнять операции над векторами, матрицами, множествами, функциями и т. п. Возникла масса вопросов: одни из них были связаны с трактовкой элементарности тех или иных шагов (например, можно ли считать взятие интеграла таким шагом?), другие – с оценкой конечности и однозначности алгоритма.

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

Структура современной теории алгоритмов

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

Поиск теоретических моделей алгоритмов происходил в трех направлениях, которые определили три основных класса таких моделей, три способа уточнения (формализации) понятия алгоритма:

1. Теория рекурсивных функций – основана на арифметизации алгоритма. Это направление является исторически первым уточнением понятия алгоритма, т. е. первой универсальной алгоритмической моделью. Используя эту модель, австрийский математик К. Гедель доказал свою знаменитую теорему о принципиальной неполноте формальных теорий.

2. Абстрактные машины (например, машина Поста и машина Тьюринга). Идея проста. Для того чтобы алгоритм понимался однозначно, а каждый его шаг можно было считать элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина. Чем проще структура машины и ее действия, тем убедительнее выглядит утверждение, что ее работа и есть выполнение некоторого алгоритма. При этом структура машины должна быть универсальной, такой, чтобы на ней можно было выполнить любой алгоритм.

3. Нормальные алгоритмы Маркова. Это направление близко к абстрактным машинам, но не использует машинных механизмов.

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

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

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

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

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

Установить нижнюю оценку – значит доказать, что никакой алгоритм вычисления не имеет сложности меньшей, чем заданная граница. Для получения результатов такого типа необходима точная фиксация рассматриваемой алгоритмической модели, и такие результаты получены только в очень жестких вычислительных моделях. В связи с этим получила развитие проблематика получения «относительных» нижних оценок, так называемая теория NP-полноты, связанная с труднорешаемостью переборных задач.

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

Абстрактные машины

Чтобы формализовать понятие алгоритма, надо:

1) формализовать понятие объекта;

2) формализовать действия над этим объектом.

Формализация объекта

Объекты могут быть различными: числа, слова, фигуры и так далее, но во всех случаях можно считать, что алгоритм имеет дело не с объектами реального мира, а с их изображениями. Например, когда алгоритм сложения работает с числами 23 и 56, можно считать, что алгоритм работает с объектом, который изображен пятью знаками: 23+56. Результат работы этого алгоритма тоже изображение, состоящее из двух знаков: 79. При этом мы исходим из того, что у нас в распоряжении имеется набор из 11 различных знаков: {0,1,2,3,4,5,6,7,8,9,+}. Эти знаки мы будем называть буквами, а весь набор – алфавитом.

Буквами могут быть любые знаки, но алфавит должен быть конечным и все буквы в нем должны быть различны. Любая конечная последовательность букв алфавита называется словом. Количество букв в слове – длина слова.

Таким образом, можно дать следующее уточненное (но не окончательно) понятие алгоритма: алгоритм – это четкая, конечная система правил для преобразования слов из некоторого алфавита в слова из этого же алфавита.

Слово, к которому применяется алгоритм, называется входным словом. Слово, которое получается в результате, – выходным словом.

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

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

Поиск способов формализации действий над объектами происходил в трех направлениях, которые и определили три основных класса универсальных алгоритмических моделей:

1-е направление – рекурсивные функции;

2-е направление – абстрактные машины;

3-е направление – нормальные алгоритмы Маркова.

Определение. Универсальной алгоритмической моделью называется такая модель, позволяющая реализовать любой алгоритм.

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

Из истории...

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

Эта идея привела к концепции абстрактной машины как универсальной алгоритмической модели. Она была выдвинута Аланом Тьюрингом и Эмилем Постом практически одновременно (в 1936–1937 годах).

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

Свыше пятидесяти лет назад, в 1935 году, Э. Пост опубликовал в «Журнале символической логики» статью «Финитные комбинаторные процессы, формулировка 1». В этой статье и появившейся одновременно в «Трудах Лондонского математического общества» статье английского математика А. М. Тьюринга «О вычислимых числах с приложением к проблеме решения» были даны первые уточнения понятия «алгоритм» – одного из центральных понятий математической логики и кибернетики, играющего важную роль в вопросах автоматизации, а поэтому и во всей жизни общества.

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

Ее суть:

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

• Вся информация должна обрабатываться побуквенно.

При этом Пост доказал, что его система обладает алгоритмической полнотой. Его идеи были настолько фундаментальны, что к ним вернулись через 30 лет. В 1967 году профессор Успенский пересказывает их с новых позиций. Он вводит термин машины Поста. Машина Поста – абстрактная машина, которая работает по алгоритмам, разработанным человеком.

Алан Тьюринг – математик и программист, предложивший стек.

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

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

Сами конструкции, предложенные Постом и Тьюрингом, сформулированы в виде «абстрактных машин»; это сделано в явной форме Тьюрингом и в неявной – Постом, у которого термин «машина» отсутствует. Изложение построений Тьюринга часто приводится в литературе по теории алгоритмов, а построения Поста, несмотря на их даже большую, чем тьюринговскую, простоту, долгое время вообще не издавались.

В 1970 году машина Поста была разработана в металле в Симферопольском университете. А машина Тьюринга была построена в металле в 1973 году в Малой Крымской Академии наук.

Машина Поста

Машина Поста – абстрактная машина, обрабатывающая слова в алфавите А={_, V}. Один из символов двоичного алфавита – метка «V», другой – пустота «_» (отсутствие метки).

Устройство машины Поста

Машина Поста состоит из бесконечной в оба конца ленты, разделенной на ячейки одинакового размера. В каждую ячейку ленты заносится один из символов внешнего алфавита.

Вдоль ленты движется каретка (считывающая и записывающая головка).

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает эту ячейку. А такая ячейка называется текущей или обозреваемой.

За единицу времени, которая называется тактом, каретка может сдвинуться на одну ячейку влево или вправо. Кроме того, каретка может также распознать, стоит или нет метка в обозреваемой ею ячейке, может заносить метку в пустую ячейку и может удалять метку из отмеченной ячейки.

Команды, по которым каретка должна занести метку в отмеченную секцию или удалить метку из пустой секции, являются недопустимыми.

Команды машины Поста

Формат команды: n K m, где

n – номер текущей команды,

K – команда из системы команд машины Поста,

m – отсылка – номер команды, которая будет выполняться следующей.

Система команд машины Поста:

1) ab

Сдвиг каретки вправо, содержимое ленты не меняется.

2) ab

Сдвиг каретки влево, содержимое ленты не меняется.

3) a V b

В обозреваемую ячейку ставится метка «V». Выполнение этой команды возможно только в том случае, если обозреваемая ячейка пустая, в противном случае команда считается невыполнимой.

4) ab

Каретка стирает метку в обозреваемой ячейке. Выполнение этой команды возможно только в том случае, если обозреваемая ячейка содержит метку, в противном случае команда считается невыполнимой.

5) a ? b1, b2

Команда передачи. Проверяется содержимое текущей ячейки, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть, – команде с номером b2. Содержимое ленты не меняется.

6) a ! [а]

Команда останова машины. Содержимое ленты не меняется. У команды остановки отсылка не обязательна.

Последовательность команд из системы команд – программа, если

1) на n-ом месте этой программы будет стоять команда с номером n,

2) отсылке m соответствует реальная команда в программе.

Порядок работы машины Поста

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

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

Будем считать, что в начальном и в конечном состояниях каретка находится над крайней левой меткой.

Если в ходе выполнения программы машина дойдет до выполнения команды остановки, то программа в этом случае считается выполненной, и машина является применимой к входному слову.

Если в ходе выполнения программы машина не дойдет до выполнения ни одной из команд останова, то выполнение программы при этом никогда не прекращается, машина никогда не останавливается – процесс работы машины происходит бесконечно. В этом случае говорят, что машина не применима к входному слову.

Пример. Составить программу машины Поста сложения двух чисел, разделенных одним или более пробелами.

Начальная конфигурация:

Заключительная конфигурация:

Для решения задачи необходимо «сдвинуть» числа так, чтобы между ними не было пустых ячеек. Для этого можно сделать следующее. Удалить первую метку, переместиться вправо и поставить метку в первую справа ячейку без метки. Если справа ячейка пустая, то разрыв не ликвидирован, поэтому каретка возвращается в начало первого числа и действия повторяются. Если справа от поставленной метки ячейка с меткой, то разрыв ликвидирован, каретка возвращается в начало числа, машина останавливается.

Программа

Комментарии

1 ↕ 2

удалить первую метку

2 → 3

цикл сдвига вправо до первой ячейки без метки

3 ? 4, 2

4 V 5

постановка метки в свободную ячейку

5 → 6

если справа ячейка пуста, то переход к 7-ой команде, в противном случае к – 10-ой

6 ? 7, 10

7 ← 8

цикл сдвига влево до первой ячейки без метки

8 ? 9, 7

9 → 1

переход на крайнюю левую метку

10 ← 11

сумма найдена, перевод каретки в начало выходного слова

11 ? 12, 10

12 → 13

13 ! 13

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

Машина Тьюринга

Машина Тьюринга – абстрактная машина, обрабатывающая слова в произвольном внешнем алфавите А={а0, а1, …, an}. Внешний алфавит для каждой задачи выбирается свой, но один символ присутствует в любом алфавите – это пустой символ («пробел»), а0= «_».

Устройство машины Тьюринга

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

Вдоль ленты движется каретка (считывающая и записывающая головка).

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает эту ячейку. А такая ячейка называется текущей или обозреваемой.

В каждый конкретный момент времени машина находится в одном из внутренних состояний и обозревает ровно одну ячейку. Множество всех внутренних состояний образует алфавит внутренних состояний машины Тьюринга Q={q0, q1, …,qm}. Состояние q1 – начальное состояние, а состояние q0 – конечное состояние; присутствуют в любой машине Тьюринга. В начальном и конечном состояниях каретка находится над крайним левым значащим символом.

Команды машины Тьюринга

Формат команды: ai qj ai΄ K qj΄, где

ai, ai΄ – символы внешнего алфавита А,

qj, qj΄– символы алфавита внутренних состояний Q,

K – команда сдвига каретки: L – сдвиг каретки влево, R – сдвиг каретки вправо, E – отсутствие сдвига каретки.

Последовательность команд – программа машины Тьюринга.

Порядок работы машины Тьюринга

Работа машины Тьюринга состоит из тактов. На каждом такте выполняется одна команда машины Тьюринга. Выбор команды определяется обозреваемым символом и тем внутренним состоянием, в котором находится машина в данный момент времени. Таким образом, если обозревается символ ai и машина находится во внутреннем состоянии qj, то машина выполняет команду ai qj ai΄ K qj΄, в ходе чего выполняются следующие действия:

1) символ ai в обозреваемой ячейке заменяется на символ ai΄;

2) каретка сдвигается в соответствии с командой К;

3) машина переводится во внутреннее состояние qj΄;

После выполнения команды происходит переход к следующему такту.

Действия машины прекращаются после выполнения команды останова.

Команда останова – это команда вида ai qj ai Е qj, т. е. команда, которая не меняет обозреваемого символа, не сдвигает каретку, не меняет внутреннего состояния машины.

Все команды останова содержатся в заключительном состоянии q0.

Если в ходе выполнения программы машина дойдет до выполнения команды останова, то программа в этом случае считается выполненной, и машина является применимой к входному слову.

Если в ходе выполнения программы машина не дойдет до выполнения ни одной из команд останова, то выполнение программы при этом никогда не прекращается, машина никогда не останавливается – процесс работы машины происходит бесконечно. В этом случае говорят, что машина не применима к входному слову.

Программу машины Тьюринга удобно отображать в виде таблицы. Например, команда ai qj ai΄ K qj΄ будет отображаться следующим образом:

А Q

q0

q1

qj

qm

a0

a1

ai

ai΄ K qj΄

an

Пример. Составить программу машины Тьюринга сложения двух чисел в десятичной системе счисления.

Внешний алфавит: А={_,0,1,2,3,4,5,6,7,8,9}.

Пример начальной конфигурации:

Заключительная конфигурация:

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

А Q

q0

q1

q2

q3

q4

q5

q6

q7

q8

_

_Eq0

_Rq2

_Lq3

_Rq6

_Lq5

1Rq1

_Lq7

_Lq7

_Rq0

0

0Eq0

0Rq1

0Rq2

9Lq3

0Lq4

1Rq1

0Lq8

0Lq8

1

1Eq0

1Rq1

1Rq2

0Lq4

1Lq4

2Rq1

1Lq8

1Lq8

2

2Eq0

2Rq1

2Rq2

1Lq4

2Lq4

3Rq1

2Lq8

2Lq8

3

3Eq0

3Rq1

3Rq2

2Lq4

3Lq4

4Rq1

3Lq8

3Lq8

4

4Eq0

4Rq1

4Rq2

3Lq4

4Lq4

5Rq1

4Lq8

4Lq8

5

5Eq0

5Rq1

5Rq2

4Lq4

5Lq4

6Rq1

5Lq8

5Lq8

6

6Eq0

6Rq1

6Rq2

5Lq4

6Lq4

7Rq1

6Lq8

6Lq8

7

7Eq0

7Rq1

7Rq2

6Lq4

7Lq4

8Rq1

7Lq8

7Lq8

8

8Eq0

8Rq1

8Rq2

7Lq4

8Lq4

9Rq1

8Lq8

8Lq8

9

9Eq0

9Rq1

9Rq2

8Lq4

9Lq4

0Lq5

_Rq6

9Lq8

9Lq8

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

стоп

Как видно из примера, каждое внутреннее состояние отвечает за определенный шаг алгоритма:

q1 – проход в конец первого числа;

q2 – проход слева направо в конец второго числа;

q3 – вычитание единицы из второго числа;

q4 – проход справа налево в конец первого числа;

q5 – прибавление единицы к первому числу;

q6 – удаление второго числа после окончания сложения;

q7 – проход справа налево по пустым ячейкам в конец первого числа;

q8 – проход справа налево в начало первого числа;

q0 – завершение работы алгоритма (содержит точки останова).

В таблице программы машины Тьюринга некоторые ячейки могут оставаться пустыми. В примере пустой остается ячейка, стоящая на пересечении строки символа «5» и столбца внутреннего состояния q6. Это означает, что во внутреннем состоянии q6 символ «5» обозреваться не может.

 
1-1 можно быстро Скачать WoW аддоны бесплатно для всех классов очень классно! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40