1. Определение алгоритма

Слово алгоритм содержит в своем составе преобразованное географическое название Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока – Муххамад ибн Муса ал-Хорезми (Магомет, сын Моисея, из Хорезма). Он жил приблизительно с 783 по 850 годы, и в 1983 году отмечалось 1200-летие со дня его рождения в городе Ургенче – областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово «алгоритм» – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

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

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

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

Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову.

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

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

Следует отметить, что различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований:

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

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

алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

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

Вплоть до 30-х годов прошлого столетия понятие алгоритма оставалось интуитивно понятным и имело скорее методологическое, а не математическое значение. К началу ХХ века много ярких примеров дала алгебра и теория чисел. Среди них можно упомянуть алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами. К ним также можно отнести алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Очевидно, что для получения результатов такого типа достаточно понятия алгоритма в интуитивной интерпретации, т.е. в суждениях не алгоритмизированных, а основанных на особой проницательности, позволяющей угадывать правду. Достаточно подробно об этом пишет Р. Пенроуз в своих работах «Новый ум короля» и «Тени разума».

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

Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя (1931 год – теорема о неполноте символических логик), в которой было показано, что некоторые математические проблемы не могут быть решены алгоритмами из некоторого класса. Общность результата Гёделя связана с тем, совпадает ли использованный им класс алгоритмов с классом всех (в интуитивном смысле) алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма.

Задача точного определения понятия алгоритма была решена в 30-х годах в работах Д. Гильберта, А. Чёрча, С. Клини, Э. Поста, А. Тьюринга в двух формах: на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Рекурсивная функция – это функция, для которой существует алгоритм вычисления ее значений по произвольному значению аргумента. Класс рекурсивных функций был определен строго как конкретный класс функций в некоторой формальной системе. Был сформулирован тезис (называемый «тезис Чёрча»), утверждающий, что данный класс функций совпадает с множеством функций, для которых имеется алгоритм вычисления значений по значению аргументов. Другой подход заключался в том, что алгоритмический процесс определяется как процесс, осуществимый на конкретно устроенной машине (называемой «машиной Тьюринга»). Был сформулирован тезис («тезис Тьюринга»), утверждающий, что любой алгоритм может быть реализован на подходящей машине Тьюринга. Оба данных подхода, а также другие подходы (А.А. Марков, Э. Пост) привели к одному и тому же классу алгоритмически вычислимых функций и подтвердили целесообразность использования тезиса Чёрча или тезиса Тьюринга для решения алгоритмических проблем.

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

В данном направлении получен ряд фундаментальных результатов. Среди них – отрицательное решение в 1952 году П.С. Новиковым классической проблемы тождества для конечно определенных групп, сформулированной Деном в 1912 году. Алгоритмическая неразрешимость знаменитой десятой проблемы Гильберта, сформулированной им среди других 23 проблем в 1900 году. Задача о разрешимости диофантова уравнения. Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах»), была доказана в 1970 году Ю.В. Мятиясевичем.

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

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

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

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

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

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

Алгоритм состоит из отдельных элементарных шагов, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных шагов – система команд ЭВМ.

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

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

Алгоритм предполагает наличие механизма реализации, который по описанию алгоритма порождает процесс вычисления на основе исходных данных. Предполагается, что описание алгоритма и механизм его реализации конечны.

Можно заметить аналогию с вычислительными машинами. Требование 1 соответствует цифровой природе ЭВМ, требование 2 – памяти ЭВМ, требование 3 – программе машины, требование 4 – её логической природе, требования 5, 6 – вычислительному устройству и его возможностям.

Имеются также некоторые черты неформального понятия алгоритма, относительно которых не достигнуто окончательного соглашения. Эти черты можно сформулировать в виде вопросов и ответов.

Следует ли фиксировать конечную границу для размера входных данных?

Следует ли фиксировать конечную границу для числа элементарных шагов?

Следует ли фиксировать конечную границу для размера памяти?

Следует ли ограничить число шагов вычисления?

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

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

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

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

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

Первые доказательства алгоритмической неразрешимости касались некоторых вопросов логики и самой теории алгоритмов. Оказалось, например, что неразрешима задача установления истинности произвольной формулы исчисления предикатов – эта теорема была доказана в 1936 г. Чёрчем.

В 1946-47 гг. А.А. Марков и Э. Пост независимо друг от друга доказали отсутствие алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении.

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

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

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

2. Алгоритм как абстрактная машина

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

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

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

Точное описание класса частично рекурсивных функций вместе с тезисом Чёрча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Спрашивается, нельзя ли уточнить непосредственно само понятие алгоритма и уже затем при его помощи определить точно и класс вычислимых функций? Такое направление поиска привело к построению иного, нежели рекурсивные функции, класса моделей алгоритма. Основная его идея состоит в том, что алгоритмические процессы – это процессы, которые может осуществлять определенным образом устроенная машина, моделирующая тем самым выполнение отдельных операций человеком. Функционирование такой машины и есть выполнение некоторого алгоритма.

Исходя из свойств алгоритма, можно сформулировать общие требования к таким машинам:

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

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

перед началом работы машине предоставляются исходные данные из области определения алгоритма;

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

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

Чем проще структура (устройство) описанной машины и чем элементарнее ее шаги, тем больше оснований считать, что ее работа и есть выполнение алгоритма. Чтобы ответить на вопрос, какие шаги работы машины следует отнести к элементарным, вернемся к тому обстоятельству, что нас интересует преобразование информации, представленной с помощью некоторого конечного алфавита. Требование конечности алфавита является очевидным следствием того обстоятельства, что решение должно быть получено за конечное число шагов. Если информация не представлена в дискретной форме, например вещественное число, то его обработка в общем случае может содержать бесконечное число шагов, например нахождение цифр числа π или извлечение квадратного корня из числа 2. Таким образом, алгоритм оказывается конечной последовательностью действий, производимых над данными, представленными с помощью конечного алфавита. С учетом сказанного становится понятным определение алгоритма, которое дает В.М. Глушков: «Алгоритм – это любая конечная система правил преобразования информации (данных) над любым конечным алфавитом».

Пусть исходные данные из области определения алгоритма представлены посредством алфавита A и образуют при этом конечную последовательность знаков {a1…an} – такая последовательность называется словом. В результате выполнения алгоритма сформируется новое слово {b1…bm}, представленное, в общем случае, в другом алфавите B. На первый взгляд для проведения такого преобразования в качестве элементарных выделяются следующие операции (шаги):

замена одного знака исходного слова ai знаком bj из алфавита B;

удаление знака исходного слова;

добавление к исходному слову знака из алфавита B.

Однако если в алфавиты включен знак, имеющий смысл пустого знака, добавление которого к слову слева или справа не изменяет этого слова, по аналогии добавления слева числового нуля к числу, то легко видеть, что: операция (2) есть ни что иное, как замена ai пустым знаком, а операция (3) есть замена пустого знака знаком bj. Таким образом, все возможные алфавитные преобразования сводятся к операции (1) – замене одного знака другим. Именно по этой причине функционирование абстрактной машины сводится к тому, что она считывает и распознает символы, записанные в памяти, в качестве которой выступает бесконечная лента, и, в зависимости от своего состояния, и того, каков обозреваемый символ, она заменяет его другим символом. После этого она переходит в новое состояние, читает следующий символ и т.д. до команды о прекращении работы. Поскольку подобные машины являются чисто модельным, теоретическим построением, они получили название абстрактных машин и рассматриваются в качестве одной из возможных универсальных алгоритмических систем.

3. Алгоритмическая машина Поста

На самом деле, Пост, в отличие от Тьюринга, не пользовался термином «машина», а называл свою модель алгоритмической системой. Однако, подчеркивая единство подходов обоих авторов, принято говорить о машине Поста.

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

Условимся обозначать головку знаком «» над обозреваемой секцией, а метку – знаком «M» внутри секции. Пустая секция никакого знака не содержит. За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку. Работа машины Поста заключается в переходе от одного состояния машины к другому в соответствии с заданной программой, которая строится из отдельных команд. Каждая команда имеет структуру xKy, где:

x – номер исполняемой команды;

K – указание о выполняемом действии;

y – номер следующей команды (наследника).

Система команд машины, включающая шесть действий, представлена в таблице 1.

Таблица 1 - Система команд машины Поста

№ п/п	Команда	Запись команды	Описание действий машины
1	Шаг вправо	x→y	Сдвиг головки на одну секцию вправо
2	Шаг влево	x←y	Сдвиг головки на одну секцию влево
3	Установить метку	xMy	В обозреваемую секцию ставится метка
4	Стереть метку	xCy	Из обозреваемой секции удаляется метка
5	Передача управления		При отсутствии метки в обозреваемой секции управление передается команде y1, при наличии – команде y2
6	Остановка	x стоп	Прекращение работы машины

Данный перечень должен быть дополнен следующими условиями:

команда xMy может быть выполнена только в пустой секции;

команда xCy может применяться только к заполненной секции;

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

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

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

Целое число k записывается на ленте машины Поста посредством k+1 следующих подряд отмеченных секций, т.е. применяется унарная система счисления. Соседние записи чисел на ленте разделяются одной или несколькими пустыми секциями.

Ниже приведен пример записи чисел 0, 2 и 3.

M

M

M

M

M

M

M

M

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

4. Алгоритмическая машина Тьюринга

Машина Тьюринга (Turing machine) получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины. Суть работы сводится к следующему. Имеется потенциально бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один символ из некоторого конечного алфавита. Машина Тьюринга имеет головку чтения/записи, которая позволяет прочитать символ в текущей ячейке, записать символ в ячейку, а также сдвинуть головку влево или вправо в соседнюю ячейку. Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. Для каждой пары (состояние, обозреваемый символ) определена тройка (записываемый символ, движение головки, новое состояние). До начала работы машина Тьюринга находится в начальном состоянии, а головка чтения-записи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, машина записывает новый символ (может быть, тот же самый), сдвигает головку влево, вправо или остается на месте и переходит в новое состояние или остается в прежнем.

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

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

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

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

Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите A = {Δ, a1…an} – этот алфавит называется внешним. В нем выделяется специальный символ – Δ, называемый пустым знаком – его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

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

j = i – означает, что в обозреваемой ячейке знак не изменился;

i ≠ 0, j = 0 – хранившийся в ячейке знак заменяется пустым, т.е. стирается;

i = 0, j ≠ 0 – пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;

i ≠ j ≠ 0 – соответствует замене одного знака другим.

Таким образом, в машине Тьюринга реализуется система предельно простых команд обработки информации. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. Однако, хотя фактически происходит перемещение ленты, обычно рассматривается сдвиг головки относительно обозреваемой секции. По этой причине команда сдвига ленты влево обозначается R (Right), сдвига вправо – L (Left), отсутствие сдвига – S (Stop). Мы будем говорить именно о сдвиге головки и считать R, L и S командами ее движения. Элементарность этих команд означает, что при необходимости обращения к содержимому некоторой ячейки, она отыскивается только посредством цепочки отдельных сдвигов на одну ячейку. Разумеется, это значительно удлиняет процесс обработки, зато позволяет обойтись без нумерации ячеек и использования команд перехода по адресу, т.е. сокращает количество истинно элементарных шагов, что важно в теоретическом отношении.

Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). ЛУ может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q ={q1…qm, z} , причем состояние z соответствует завершению работы, а q1 является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (ai, qi) и три выходных (ai+1, qi+1, Di+1) (см. рис. 2):

Рис. 2 - Схема логического устройства машины Тьюринга

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (ai,), а на другой вход – знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания знаков (ai, qi) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (ai+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на вызов следующего управляющего знака (qi+1). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние. Схема функционирования такой машины представлена на рисунке 3.

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

алгоритмический машина пост тьюринг

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

Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qi aj → qi’ aj’ Dk, т.е. после обзора символа aj головкой в состоянии qi в ячейку записывается символ aj’, головка переходит в состояние qi’, а лента совершает движение Dk. Для каждой комбинации qi aj имеется ровно одно правило преобразования (правил нет только для z, поскольку, попав в это состояние, машина останавливается). Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов qi aj одну и только одну тройку выходных qi’aj’Dk – она называется логической функцией машины и обычно представляется в виде таблицы (функциональной схемой машины), столбцы которой обозначаются символами состояний, а строки – знаками внешнего алфавита. Если знаков внешнего алфавита n, а число состояний ЛУ m, то, очевидно, общее число правил преобразования составит nЧm.

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

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

Записать конфигурацию можно следующим образом: Δa1 qi aj…ak Δ, которая означает, что в слове из k символов обозревается секция номер j и при этом управляющее устройство находится в состоянии qi. Ясно, что конфигурация машины может содержать любое количество символов внешнего алфавита и лишь один символ внутреннего. Часто конфигурацию записывают в виде a1 qi a2, где a1 – слово на ленте слева от головки, a2 – слово на ленте справа от головки, включая обозреваемый знак. Слева от a1 и справа от a2 лента пуста.

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

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

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

остановки не происходит.

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

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

Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы:

насколько общим является понятие машины Тьюринга?

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

может ли всякий алгоритм задаваться таким образом?

На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:

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

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

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

5. Универсальная машина Тьюринга

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

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

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

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

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

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

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

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

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

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

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

6. Нормальные алгоритмы Маркова

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

Вновь рассмотрим некоторый алфавит A, содержащий конечное число знаков (букв). Введем ряд определений:

Слово – это любая конечная последовательность знаков алфавита.

Число символов в слове называется его длиной.

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

Слово s называется подсловом слова q, если q можно представить в виде q= rst, где r и t – любые слова в том же алфавите (в том числе и пустые).

Теперь можно определить понятие алгоритма (не являющееся строгим):

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

В алгоритмах Маркова в качестве элементарного шага алгоритма принимается подстановка одного слова вместо другого. Пусть в алфавите A построено исходное слово P, которое содержит подслово Pr (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово Pk в том же алфавите.

Подстановкой называется замена первого по порядку подслова Pr исходного слова P на слово Pk. Обозначается подстановка Pr→Pk.

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

Библиографический список

Авдеев Р.Ф. Философия информационной цивилизации [Текст] / Р.Ф. Авдеев. – М.: ВЛАДОС, 2008.

Булгаков И.С. Счетные машины [Текст] / И.С. Булгаков. – М.: Машгиз, 2010.

Винер Н. Человек управляющий [Текст] / Н. Винер. – СПб.: Питер, 2009. – 288 с.

Гутер Р.С. От абака до компьютера [Текст] / Р.С. Гутер, Ю.Л. Полунов. – М.: Знание, 2009.

Ершов Ю.Л. Математическая логика [Текст] / Ю.Л. Ершов, Е.А. Палютин. – М.: Наука, 2008.

Клини С. Введение в метаматематику [Текст] / С. Клини. – М.: Изд-во иностр. лит., 2008.

Клини С. Машины Тьюринга и рекурсивные функции [Текст] / С. Клини. – М., 2010.

Клини С. Математическая логика [Текст] / С. Клини. – М., 2009.

Колин, К.К. Фундаментальные основы информатики: социальная информатика [Текст]: учеб. пособие для вузов / К.К. Колин. – М.: Академический Проект; Екатеринбург: Деловая книга, 2008.

Кондаков Н.И. Логический словарь-справочник [Текст] / Н.И. Кондаков. – М.: Наука, 2010.

Основы философии науки [Текст]: учеб. пособие для аспирантов / В.П. Кохановский [и др.]. – Ростов н/Д: Феникс, 2009.

Ларичев О.И. Наука и искусство принятия решений [Текст] / О.И. Ларичев. – М.: Наука, 2009.

Пенроуз Р. Новый ум короля: о компьютерах, мышлении и законах физики [Текст] / общ. ред. В.О. Малышенко; пер. с англ. – М.: Едиториал УРСС, 2008. – 384 с.

Петров Ю.П. История и философия науки. Математика, вычислительная техника, информатика [Текст] / Ю.П. Петров. – СПб.: БХВ-Петербург, 2010.

Поликарпов В.С. История науки и техники [Текст]: учеб. пособие / В.С. Поликарпов. – Ростов н/Д: Феникс, 2008.

Рязанкин В.Н. Вычислительные клавишные машины [Текст] / В.Н. Рязанкин, Г.П. Евстигнеев, Н.Н. Тресвятский. – М.: Машгиз, 2009.

Успенский В.А. Машина Поста [Текст] / В.А. Успенский. – М.: Наука, 2010. – 96 с.

Успенский В.А. Теория алгоритмов: основные открытия и приложения [Текст] / В.А. Успенский, А.Л. Семенов. – М.: Наука, 2010. – 288 с.

Чёрч А. Введение в математическую логику [Текст] / А. Чёрч. – М., 2008. Т.1.