close

Вход

Забыли?

вход по аккаунту

?

djakova 0C86603109

код для вставкиСкачать
Федеральное агенТство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Санкт-Петербургский государственный университет
аэрокосмического приборостроения
Г. Н. Дьякова, В. М. Лагодинский
Элементы
теории алгоритмов
Учебное пособие
Санкт-Петербург
2009
УДК 004421(075.8)
ББК 2212я73
Д93
Рецензенты:
кандидат технических наук, доцент С. Л. Козенко
кандидат физико-математических наук, доцент В. А. Вешев
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
Дьякова, Г. Н., Лагодинский, В. М.
Д93 Элементы теории алгоритмов: учеб. пособие / Г. Н. Дьякова,
В. М. Лагодинский. – СПб.: ГУАП, 2009. – 24 с.
ISBN 978-5-8088-0493-7
В учебном пособии приводятся необходимые сведения о теории
алгоритмов, требования, предъявляемые к алгоритмам, и методы
уточнения понятия алгоритма. Рассмотрены основные понятия теории рекурсивных функций и функционирование машин Тьюринга.
Пособие предназначено для самостоятельного изучения основных положений теории алгоритмов студентами очной, вечерней
и заочной форм обучения направления «Информатика и вычислительная техника». Они могут быть полезны также студентам других
специальностей при изучении дисциплин со схожей тематикой.
УДК 004421(075.8)
ББК 2212я73
Учебное издание
Дьякова Галина Николаевна
Лагодинский Владимир Меерович
Элементы
теории алгоритмов
Учебное пособие
Редактор А. А. Гранаткина
Верстальщик С. Б. Мацапура
Сдано в набор 18.06.09. Подписано к печати 23.11.09.
Формат 60×84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,5.
Уч.-изд. л. 1,47. Тираж 300 экз. Заказ № 751.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
ISBN 978-5-8088-0493-7
© ГУАП, 2009
© Г. Н. Дьякова,
В. М. Лагодинский, 2009
1. Понятие алгоритма
В своей профессиональной деятельности выпускники ГУАП решают самые разные задачи. Среди этих задач встречаются такие,
методы решения которых известны, и требуется лишь правильно
их использовать. Однако развитие науки и техники приводит к необходимости создавать новые методы решения новых задач.
Что же такое метод? Известно определение (конечно, шуточное):
метод – это искусственный прием, примененный дважды. Но тогда разработка методов – это не наука, а искусство, и не существует
правил, зная которые, можно найти решение для любой задачи.
А если такие правила все-таки существуют? Существуют, естественно, правила решения многих задач. Еще в средней школе мы
узнали, как сложить или перемножить два любых рациональных
числа, как поделить их друг на друга с любой точностью, как найти
наибольший общий делитель двух целых чисел. Эти правила известны с давних времен. Курс математического анализа знакомит
нас с правилами дифференцирования элементарных функций и интегрирования некоторых элементарных функций.
Очевидно, что множество этих задач делится на классы однотипных: задачи одного класса различаются лишь параметрами и
решаются единообразно. Каждый такой класс называют массовой
проблемой.
Определение. Общий, единообразный, точно определенный способ решения любой задачи из данного класса называется алгоритмом.
Это определение, безусловно, не является математически строгим и носит интуитивный характер, поскольку включает в себя
слово «способ», смысл которого не определен ранее.
Слово «алгоритм» происходит от имени персидского математика и астронома IX в. Абу Джафара аль-Хорезми, написавшего
трактат по математике «Китаб аль-джебр валь-мукабала» («Книга
о восстановлении и противопоставлении»). В XII в. трактат переведен с арабского на латинский язык. Слово «алгебра» происходит от
названия математической операции «аль-джебр».
3
Очевидно, что очень важно знать, для каких классов задач существуют алгоритмы решения, а для каких не существуют. Вопрос
этот приобрел особую значимость в минувшем веке, когда появилась кибернетика, стали разрабатывать и применять вычислительные машины. Поскольку в то время вычисления являлись привелегией людей и считались наиболее сложным видом мыслительной
деятельности, интерес представлял философский вопрос: может
ли машина мыслить? Если это возможно, то перед человечеством
открываются невиданные перспективы, но одновременно появляются и серьезные опасности. Если это невозможно, то хорошо бы
знать, что может машина, и научить ее мыслить.
Однако когда мы говорим о задачах, требующих решения, то
имеем в виду не только задачи, возникающие на практике. На рубеже XIX–XX вв. математика достигла той ступени развития, на
которой остро стал вопрос о ее основаниях. Была разработана теория множеств, ставшая основой всей математики. Немецкий математик Д. Гильберт в 1900 г. выдвинул программу, в которой были
сформулированы важнейшие проблемы математики. Одна из этих
проблем состоит в следующем: для каждого раздела математики
необходимо построить непротиворечивую и полную систему аксиом и правил вывода, с помощью которых из них могли бы быть получены и доказаны все истинные утверждения, т. е. теоремы. Это к
тому же означает, что и ложность всех ложных утверждений могла
бы быть доказанной как истинность противоположных утверждений.
Итак, в начале XX в. была осознана необходимость построения
нового раздела математики, в рамках которого можно было бы решать вопросы принципиальной возможности разработки правил
решения разного типа задач. Этот раздел математики, названный
теорией алгоритмов, был создан в основном трудами А. М. Тьюринга, А. Черча, Э. Поста и других математиков и логиков. Большую
роль сыграли также идеи Д. Гильберта и Б. Рассела.
Сформулируем требования, которым должны удовлетворять алгоритмы.
Свойства алгоритмов:
1) дискретность: процесс обработки данных протекает в «дискретном времени», т. е. состоит из конечного числа операций, последовательно производимых в отдельные моменты времени;
2) детерминированность: в начальный момент времени задается исходная система с конечным числом элементов, а в каждый
последующий эту систему получают по определенному закону (про4
грамме) из системы величин, имевшихся в предыдущий момент
времени;
3) элементарность: закон получения последующей системы величин из предшествующей должен быть простым;
4) направленность: если способ получения последующей величины из предыдущей не дает результата, должно быть определено,
что следует считать результатом алгоритма;
5) массовость: алгоритм должен быть пригоден для решения
всех задач из данного класса.
Хотя интуитивное определение алгоритма не обладает математической строгостью, оно позволяет практически однозначно установить, является ли данный процесс алгоритмическим. Сложности
появляются, если возникает предположение об алгоритмической
неразрешимости задачи, т. е. о невозможности решить ее алгоритмическими методами. Доказать отсутствие алгоритма, решающего
данную задачу, имея лишь интуитивное определение алгоритма,
невозможно. Поэтому очень важно иметь математически строгое
его определение.
В 20–30-е годы XX в. предпринимались попытки формализовать понятие алгоритма. Было предложено несколько математически строго определенных моделей алгоритмов (рекурсивные функции, машины Поста и Тьюринга, нормальные алгоритмы Маркова
и др.). Было установлено, что классы задач, решаемых в этих моделях, совпадают.
В пособии будут рассмотрены две модели алгоритмов: рекурсивные функции и машины Тьюринга. Список рекомендуемой литературы приведен в конце пособия.
2. Рекурсивные функции
2.1. Вычислимые функции.
Примитивно рекурсивные функции
Исторически первой формализацией понятия алгоритма считается теория рекурсивных функций (от латинского recursio – возвращение). Это одно из уточнений общего понятия алгоритма, в
котором исходные данные представляют собой системы натуральных чисел, и возможные результаты применения алгоритма также являются натуральными числами. При этом возникает вопрос
о существовании алгоритма для вычисления значений числовых
функций, зависящих от целочисленных аргументов. В теории ре5
курсивных функций типичным является вызов функции внутри
нее самой.
Определение. Функция называется вычислимой, если существует алгоритм, позволяющий вычислить ее значения.
Определение. Функция называется полувычислимой, если при
задании исходного набора переменных, принадлежащих области
определения функции, алгоритм не заканчивает работу (зацикливается).
Построение класса вычислимых функций было произведено
А. Черчем в 1936 г. Оно осуществляется следующим образом:
выделяются элементарные вычислимые функции (те функции,
которые являются интуитивно вычислимыми) и задается способ
получения из этих функций других функций за конечное число
шагов.
Выбираются следующие всюду определенные простейшие функции:
1. S(x) = x+1 – функция следования.
2. O(x) = 0 – нуль-функция.
3. Inm (x1, ..., xn ) = xm – проектирующая функция.
Для получения новых функций из простейших за конечное число шагов вводят следующие операции.
СУПЕРПОЗИЦИЯ ФУНКЦИЙ
Определение. Будем говорить, что функцию ψ(x1, …, xn), определяемую равенством
ψ(x1, …, xn) = j(f1(x1, …, xn), …, fm(x1, …, xn)),
получают с помощью оператора суперпозиции из функций j, f1, …,
fm.
Оператор суперпозиции обладает следующими свойствами. При
условии, что функции j, f1, …, fm всюду определены, функция ψ
также всюду определена. Если функции j, f1, …, fm вычислимы, то
и ψ вычислима.
Заметим, что в определении суперпозиции функций все функции f1, …, fm зависят от всех n аргументов. В случае если это условие не выполнено, можно использовать фиктивные аргументы и
проектирующую функцию. Например, функция
ψ(x1, x2, x3) = j(F1(x1, x2), x1, x3)
6
является суперпозицией функций
j, f1 (x1, x2 , x3 ) = F1 (x1, x2 ), f2 (x1, x2 , x3 ) =
= I13 (x1, x2 , x3 ), f3 (x1, x2 , x3 ) = I33 (x1, x2 , x3 ).
СХЕМА ПРИМИТИВНОЙ РЕКУРСИИ
Определение. Будем говорить, что функцию f(x1, …, xn, y) получают из функций j(x1, …, xn) и ψ(x1, …, xn, y, z) с помощью оператора примитивной рекурсии, если она может быть задана схемой
примитивной рекурсии
ìïï
f (x1, ..., xn , 0) = j(x1, ..., xn ),
í
ïïîf (x1, ..., xn , y + 1) = ψ (x1, ..., xn , y, f (x1, ..., xn , y)).
В случае когда функция f одноместна (n = 0), схема примитивной рекурсии принимает вид
ìïï
f (0) = a,
í
ïïîf (y + 1) = ψ (y, f (y)),
где a – заданное число.
Определение. Функция f называется примитивно рекурсивной,
если ее можно получить с помощью конечного числа операций подстановки и примитивной рекурсии, исходя из простейших функций S, O, Im
n.
Рассмотрим примеры, показывающие примитивную рекурсивность основных арифметических операций.
Пример 1 (примитивная рекурсивность операции сложения).
Двухместная операция сложения f(x,y) = x+y удовлетворяет следующей схеме примитивной рекурсии:
ìï
f (x, 0) = x + 0 = x = I11 (x),
ï
í
ïïf (x, y + 1) = (x + y) + 1 = f (x, y) + 1 = S(x + y).
î
Здесь j(x) = I11 (x); ψ (x, y, f (x, y)) = S(x + y).
Итак, рассматриваемую функцию получают из простейших
функций по схеме примитивной рекурсии. Следовательно, она является примитивно рекурсивной.
7
Пример 2 (примитивная рекурсивность операции умножения).
Двухместная операция умножения f(x,y) = xy удовлетворяет схеме
примитивной рекурсии
ìïï
f (x, 0) = x × 0 = O(x),
í
ïïîf (x, y + 1) = x × y + x = f (x, xy)
с начальными примитивно рекурсивными функциями j(x) = O(x),
ψ(x, y, z) = x+z (примитивная рекурсивность операции сложения
показана в примере 1).
Пример 3. Покажем примитивную рекурсивность степенной
функции.
Функция xy удовлетворяет схеме примитивной рекурсии
ìï
f (x, 0) = x0 = 1,
ï
í
ïïf (x, y + 1) = x y+1 = x y x
ïî
с начальными примитивно рекурсивными функциями j(x) = 1,
ψ(x, y, z) = zx.
Пример 4. Рассмотрим разность натуральных чисел x – y. В области натуральных чисел она является полувычислимой двухместной функцией от x и y, определенной при x≥y. Однако примитивные
рекурсивные функции должны быть всюду определены. Поэтому в
теории рекурсивных функций вводится понятие усеченной разно.
сти, обозначаемой знаком « » и определяемой следующим образом:
ïìx - y ïðè x ³ y,
.
x y = ïí
ïïî 0 ïðè x < y.
Примитивная рекурсивность этой функции доказывается в два
этапа.
.
Вначале рассмотрим функцию x 1, удовлетворяющую примитивно рекурсивной схеме
ìï
.
ïï f (0) = 0 1 = Î(x),
ï
í
ïï
.
ïïf (x + 1) = (x + 1) 1 = x
ïî
с примитивно рекурсивными начальными функциями j(x) = Î(x),
j(x) = Î(x), ψ (x, y) = I12 (x, y) и, таким образом, являющуюся примитивно рекурсивной.
8
.
Исходная функция x y удовлетворяет примитивно рекурсивной схеме
ìï
.
ïï
f (x, 0) = x 0 = x = I11 (x),
ï
í
ïï
.
. .
ïïf (x, y + 1) = x (y + 1) = (x y) 1
ïî
с простейшей начальной функцией j(x) = I11 (x) и по доказанному
.
на первом этапе – с простейшей функцией ψ (x, y, z) = z 1.
Пример 5. Рассмотрим функцию f(x, y) = |x–y|. Примитивная рекурсивность этой функции следует из примитивной рекурсивности
функций сложения и усеченной разности в соответствии с формулой
.
.
x - y = (x y) + (y x).
2.2. Частично рекурсивные функции.
Тезис Черча
Определение частично рекурсивной функции опирается на понятие оператора минимизации. Рассмотрим еще одну операцию
над примитивно рекурсивными функциями.
ОПЕРАЦИЯ МИНИМИЗАЦИИ
Изучим n-местную примитивно рекурсивную функцию f(x1, …,
xn). Ставится задача нахождения для фиксированного набора переменных x1, …, xn–1 наименьшего натурального значения y, такого,
что выполняется равенство
f(x1, …, xn–1, y) = xn.
Полученное минимальное значение обозначим m. Величина m
будет функцией набора переменных x1, …, xn–1. Для этой величины принято обозначение
μy(f(x1, …, xn–1, y) = xn).
Последняя запись читается следующим образом: наименьшее y
такое, что f(x1, …, xn–1, y) = xn.
Результат процесса нахождения значения μy(f(x1, …, xn–1, y) =
xn) считается неопределенным в следующих случаях:
а) значение f(x1, …, xn–1, 0) не определено;
9
б) значения f(x1, …, xn–1, y) определены для y = 0, 1, m–1 и отличны от xn, но значение f(x1, …, xn–1, m) не определено;
в) значения f(x1, …, xn–1, y) определены для всех y и отличны
от xn.
Определение. Говорят, что функцию f(x1, …, xn) получают
из функций j(x1, …, xn, y) с помощью оператора минимизации
(μ-оператора) и обозначают f(x1, …, xn) = μy(j(x1, …, xn–1, y) = 0),
если выполнено условие: f(x1, …, xn) определена и равна y тогда и
только тогда, когда j(x1, …, xn–1, 0), …, j(x1, …, xn–1, y–1) определены и не равны нулю, а j(x1, …, xn, y) = 0.
Рассмотрим процесс вычисления m на примере функции f(x, y) =
x–y. Эта функция может быть получена с помощью оператора минимизации:
f (x, y) = µ z (y + z = x) = µ z (I23 (x, y, z) + I33 (x, y, z) = I13 (x, y, z)).
Вычислим, например, f(4,1). Положим y = 1 и будем придавать
x последовательно значения:
z = 0: 2 + 0 = 2 ¹ 4,
z = 1: 2 + 1 = 3 ¹ 4,
z = 2: 2 + 2 = 4 = 4.
Следовательно, f(4,1) = 4.
Определение. Функция f называется частично рекурсивной,
если она может быть получена из простейших функций путем применения конечного числа операторов суперпозиции, примитивной
рекурсии и минимизации.
Определение. Функция f называется общерекурсивной, если она
частично рекурсивна и всюду определена.
Приведем пример общерекурсивных функций: f(x, y) = x+y,
f(x, y) = xy, простейшие функции.
Для всякой частично рекурсивной функции f существует механический процесс, перерабатывающий любое натуральное число x
в значение f(x). Он продолжается бесконечно тогда и только тогда,
когда значение функции f в точке x не определено, т. е. в тех точках, в которых значение функции f определено. Для вычисления
этого значения существует алгоритм, обрывающийся через конечное число шагов.
Понятие рекурсивной функции – одно из основных понятий теории алгоритмов. Алгоритмическое истолкование частично рекурсивных функций определяется тезисом Черча.
10
Тезис Черча. Класс алгоритмически (или машинно) вычислимых функций совпадает с классом всех частично рекурсивных
функций.
Тезис Черча является гипотезой, доказать которую невозможно
из-за отсутствия строгого определения вычислимой функции, но в
соответствии с этим вычислимость функции равносильна ее рекурсивности.
3. Машины Тьюринга
Определение. Машина Тьюринга представляет собой систему,
работающую в дискретные моменты времени t = 0, 1, 2,... и состоящую из следующих трех частей:
1. Бесконечная лента, разбитая на ячейки, в каждой из которых могут быть записаны символы из конечного алфавита A = {a0,
a1, …, am}, называемого внешним алфавитом машины. Ячейка, в
которой записан символ a0, называется пустой. В любой момент
времени не пусто лишь конечное число ячеек. В процессе работы
машины каждая ячейка может менять свое состояние путем замены приписанного к ней символа ak на другой – al Î A. Словом называется непустой конечный набор символов {ai1 ai2 …air } Ì A, где
ai1 – символ в первой непустой ячейке слева; ai2 – символ во второй ячейке, ...; air – символ в самой правой непустой ячейке.
2. Управляющая головка, представляющая собой устройство,
которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и обладает некоторым состоянием из конечного множества внутренних состояний Q = {q0, q1, …, qn}, Q Ç A = Æ. Состояние q0 называется заключительным и означает завершение работы
машины, а состояние q1 – начальным и означает начало ее работы.
3. Программа Π, т. е. совокупность выражений T(i,j) (i = 0, ...,
m, j = 1, ..., n), каждое из которых имеет вид qiaj → qkalA, где вместо
A расположены символы L, R или P, и означает замену буквы aj на
букву al, состояния головки qi на состояние qk и сдвиг ее на одну
ячейку влево, если A = L, вправо, если A = R, и сохранение положения головки, если A = P.
Выражения T(i,j) называются командами. При этом команды
не могут начинаться со слов q0ai. Символы L и R не принадлежат
множеству A È Q.
Программу обычно представляют в виде двумерной таблицы и
называют тьюринговой функциональной схемой:
11
a0
a1
...
an
q1
T(1,0)
T(1,1)
...
T(1,n)
q2
T(2,0)
T(2,1)
...
T(2,n)
...
...
...
...
...
qm
T(m,0)
T(m,1)
...
T(m,n)
Работа машины состоит в изменении ее конфигурации, определяемой состоянием ленты, управляющей головки и положением
текущей ячейки. Дискретным моментам времени t = 0, 1, 2,... соответствуют конфигурации K0, K1, K2,... Конфигурацию машины
можно записывать в виде слова, причем слева от символа, соответствующего ячейке, которую обозревает головка, помещается символ состояния головки (он будет выделяться полужирным шрифтом).
Начальная информация записывается в начальной конфигурации K0. В моменты времени t = 0, 1, 2,... происходит преобразование информации, и конфигурация, соответствующая предыдущему
моменту времени, заменяется на конфигурацию, соответствующую
новому моменту времени. Если новая конфигурация содержит состояние головки q0, машина останавливается (новая конфигурация является окончательной). Тогда результатом работы машины
является слово, соответствующее состоянию ленты, – набор символов в ячейках, расположенных справа от головки. Если начальная конфигурация такова, что перехода к состоянию головки q0 не
происходит, то машина никогда не остановится, и результат ее действия на эту начальную конфигурацию не определен. В этом случае
говорят, что данная машина (с данной функциональной схемой) не
применима к данной начальной конфигурации.
Пусть, например, начальная конфигурация машины имеет вид
K0 = {a0a2q1a2a0},
а ее функциональная схема такова:
12
a0
a1
a2
q1
q3a2L
q2a1R
q1a2L
q2
q2a0P
q1a2P
q2a1P
q3
q0a0R
q4a1R
q1a2P
q4
q3a1P
q4a0R
q4a2R
Так как управляющая головка обозревает букву a2, а ее состояние – букву q1, машина вырабатывает команду q1a2L, и конфигурация машины приобретает вид
K1 = {a0q1a2a2a0}.
Тогда
K2 = {q1a0a2a2a0},
K3 = {q3a0a2a2a0},
K4 = {a0q0a2a2a0}.
Поскольку теперь машина находится в состоянии q0, она останавливается, и слово a2a2 является результатом.
Пусть начальная конфигурация имеет вид
K0 = {a0a1a1a2q1a2a0}.
Машина с той же функциональной схемой приводит к следующим конфигурациям:
K1 = {a0a1a1q1a2a2a0},
K2 = {a0a1q1a1a2a2a0},
K3 = {a0a1a1q2a2a2a0},
K4 = {a0a1a1q2a1a2a0},
K5 = {a0a1a1q1a1a2a0}.
Поскольку конфигурация K5 тождественна конфигурации K1,
машина никогда не остановится, значит, она не применима к начальной конфигурации K0.
Рассмотрим несколько примеров реализации алгоритмов в машине Тьюринга.
Пример 1 (реализация в машине Тьюринга алгоритма перехода
от n к n+1 в десятичной системе счисления). Число n записывается в десятичной системе счисления на ленте, причем цифры помещаются по одной в каждой ячейке подряд без пропусков. Внешний
алфавит содержит цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и символ пустой
ячейки a0.
Начальная конфигурация имеет вид
K0 = {a0a1a2…am–1q1ama0},
где ai (i = 1, 2, ..., m) – одна из цифр, при этом a1≠0. В первом такте
работы машина стирает последнюю цифру, а ее дальнейшая работа
зависит от этой цифры am: если она была am < 9, машина на ее место записывает цифру am+1 и переходит в состояние q0 (останавливается); если am = 9, машина на это место записывает 0, переходит
влево на одну ячейку, и если она не пуста, стирает находящуюся в
ней цифру am–1, вместо нее записывает цифру am–1+1 и переходит
13
в состояние q0, если пуста, то вписывает в нее единицу и переходит
в состояние q0. Таким образом, машина может пребывать лишь в
состояниях q1 и q0, ее функциональная схема должна иметь вид
q1
a0
0
1
2
…
9
q01P
q01P
q02P
q03P
…
q10L
Пусть, например, n = 183. Тогда
K0 = {a018q13},
K1 = {a018q04}.
Для n = 399
K0 = {a039q19},
K1 = {a03q190},
K2 = {a0q0400}.
Пример 2 (алгоритм сложения двух натуральных чисел). На
ленту подаются два числа, заданных наборами палочек. Требуется
сложить эти числа.
Внешний алфавит состоит из трех символов: символ пустой
ячейки a0, символ единицы « ‫( » ׀‬палочка) и символ умножения «*»
(звездочка). Пусть, например, требуется сложить числа 2 и 3. Тогда
сначала на ленте машины записывается слово a0‫׀׀׀*׀׀‬a0. В результате работы машины на ленте должно оказаться записанным слово
a0‫׀׀׀׀׀‬a0. Работа машины заключается в следующем.
В начальный момент обозревается самая левая палочка. Она
сдвигается вправо до первой (правой) пустой ячейки, минуя все
палочки и звездочку. В эту пустую ячейку вписывается палочка.
Затем управляющая головка возвращается за второй палочкой, которая переносится вправо так же, как первая. Потом управляющая
головка возвращается к звездочке, стирает ее и останавливается.
Такты работы машины изображают конфигурациями
1) a0 q1‫׀׀׀*׀׀‬a0;
5) a0‫׀*׀‬q2‫׀׀׀‬a0;
9) a0‫ ׀׀*׀‬q3‫׀׀‬a0;
13) a0q3‫׀׀׀׀*׀‬a0;
17) a0*q2‫׀׀׀׀‬a0;
21) a0*‫׀׀׀׀‬q2a0;
25) a0*‫׀‬q3‫׀׀׀׀‬a0;
29) a0q3*‫׀׀׀׀׀‬a0;
14
2) a0q2‫׀׀׀׀*׀‬a0;
6) a0‫ ׀׀׀*׀‬q2‫׀‬a0;
10)a0‫׀*׀‬q3‫׀׀׀‬a0;
14) q3a0‫׀׀׀׀*׀‬a0;
18) a0*‫׀‬q2‫׀׀׀‬a0;
22) a0*‫׀׀׀׀‬q3 ‫׀‬a0;
26) a0*q2‫׀׀׀׀׀‬a0;
30) a0a0q0‫׀׀׀׀׀‬a0.
3) a0‫׀‬q2*‫׀׀׀‬a0;
7) a0‫ ׀׀׀׀*׀‬q2a0;
11) a0‫*׀‬q3‫׀׀׀׀‬a0;
15) a0q3‫׀׀׀׀*׀‬a0;
19) a0*‫׀׀‬q2‫׀׀‬a0;
23) a0*‫׀׀׀‬q3‫׀׀‬a0;
27) a0q3*‫׀׀׀׀׀‬a0;
4) a0‫*׀‬q2‫׀׀׀׀‬a0;
8) a0‫ ׀׀׀*׀‬q3‫ ׀‬a0;
12) a0‫׀‬q2*‫׀׀׀׀‬a0;
16) a0q2*‫׀׀׀׀‬a0;
20) a0*‫׀׀׀‬q3‫׀‬a0;
24) a0*‫׀׀‬q3‫׀׀׀‬a0;
28) q3a0*‫׀׀׀׀׀‬a0;
Функциональная схема, соответствующая этому процессу, имеет вид
a0
*
‫׀‬
q0a0P
q2a0R
q2
q3‫׀‬P
q2*R
q2‫׀‬R
q3
q1a0R
q3*L
q3‫׀‬L
q1
Здесь использованы внешний алфавит {a0,*,‫ }׀‬и состояния машины q0, q1, q2, q3.
Пример 3 (алгоритм Евклида). Алгоритм Евклида решает следующую задачу: для двух данных натуральных чисел найти их
наибольший общий делитель (НОД). Он состоит в построении убывающей последовательности чисел, из которых первое является
большим из данных двух, второе – меньшим, третье получается
как остаток от деления первого на второе, четвертое – как остаток
от деления второго на третье, и т. д., пока не будет выполнено деление без остатка. Машина Тьюринга, реализующая этот алгоритм,
должна чередовать циклы сравнения и вычитания чисел.
Внешний алфавит состоит из четырех букв: a0, *, α, β. Пусть,
например, даны числа 4 и 6. Требуется найти их НОД. Начальная
конфигурация имеет вид
a0****q1******a0.
Для того чтобы сравнить два числа, следует все звездочки, изображающие первое число, заменить на α, а все звездочки, изображающие второе, заменить на β. Получаем следующие конфигурации:
1) a0***q1*******a0;
3) a0***αq2******a0;
2) a0***q2α******a0;
4) a0***αq1β*****a0.
После этого головка должна двигаться влево до ближайшей
звездочки, которая заменяется на α, а дальше вправо до первой
звездочки, которая заменяется на β. Эта процедура повторяется до
тех пор, пока с одной из сторон (в данном случае слева) не останется
ни одной звездочки. В результате появляется следующая конфигурация:
q1a0ααααββββ**a0.
15
Этим заканчивается цикл сравнения и начинается цикл вычитания, в результате которого меньшее число должно быть стерто целиком, звездочки второго числа, помеченные буквой β, заменяются на обычные звездочки, и, следовательно, большее число 6 будет
разбито на два: 4 и 2:
a0a0a0a0a0****q2** a0.
Этим заканчивается первый цикл вычитания. После сравнения
чисел 4 и 2 получаем конфигурацию
a0**ααββq4 a0.
После этого начинается новый цикл вычитания, который приводит к конфигурации
a0**q1** a0.
Теперь сравниваются числа 2 и 2, после чего получаем конфигурацию
q3a0ααββa0.
Следующий цикл вычитания приводит к заключительной конфигурации
a0**q0a0,
которая означает, что НОД чисел 4 и 6 равен 2.
Соответствующая функциональная схема Тьюринга имеет вид
α
β
a0
*
q1
q3a0R
q2αP
q1αL
q1βL
q2
q4a0L
q1βP
q2αR
q2βR
q3
q0a0P
q2*P
q3a0R
q3*R
q4
q0a0P
q1*P
q4*L
q4a0L
Из рассмотренных примеров видно, что можно «построить»
машины Тьюринга, складывающие и вычитающие целые числа,
а значит, перемножающие их и делящие одно целое число на другое с остатком, следовательно, возможно построить и такую машину Тьюринга, действие которой сводится к композиции этих
действий. Все те действия, для которых можно «построить» машины Тьюринга, удовлетворяют приведенному ранее интуитивному определению алгоритма, кроме того, множество этих действий
определяется математически строго. Возникает вопрос: всякий ли
16
процесс, удовлетворяющий этому определению алгоритма, может
быть реализован с помощью некоторой машины Тьюринга?
До настоящего времени нет доказательства ни положительного,
ни отрицательного ответа на этот вопрос. Доказано лишь, что множества вычислительных процессов, реализуемых машинами Тьюринга, рекурсивными функциями и нормальными алгоритмами
Маркова, совпадают. Это дало основание А. М. Тьюрингу выдвинуть гипотезу, которая называется тезисом Тьюринга.
Тезис Тьюринга. Любой алгоритм может быть задан некоторой
тьюринговой функциональной схемой и реализован в виде соответствующей машины Тьюринга.
Данная гипотеза не является аксиомой теории алгоритмов, так
как в самой этой теории она не используется для доказательства.
В то же время принятие этой гипотезы заменяет интуитивное определение алгоритма на математически строгое определение процессов, реализуемых машинами Тьюринга. При этом появляется возможность строго математически решить вопрос: любая ли массовая
проблема может быть решена с помощью некоторого алгоритма,
т. е. машины Тьюринга?
Вместе с тем понятие машины Тьюринга можно несколько обобщить. Ранее предполагалось, что функциональная схема машины
Тьюринга задана однозначно. Однако можно «построить» такую
машину Тьюринга, которая будет считывать с ленты свою функциональную схему и работать в соответствии с этой схемой. Для этого,
естественно, необходим определенный алфавит. Покажем, как это
можно сделать, используя функциональную схему, реализующую
алгоритм Евклида.
Очевидно, что программу машины Тьюринга можно записывать
не только в виде двумерной таблицы, как это делалось раньше, но и
в виде одномерной строки, состоящей из пятерок символов: первый
символ пятерки указывает столбец таблицы, второй – ее строку, а
три последующих символа – символы той тройки, которая находится в соответствующей клетке таблицы. Для схемы алгоритма
Евклида получаем следующую строку:
a0q1q3a0R*q1q2αPαq1q1αLβq1q1βLa0q2q4a0L...
(1)
Каждую букву этой строки можно переименовать. Примем следующие условия:
1) строка должна однозначно разбиваться на отдельные кодовые
группы;
2) кодовые группы должны быть трех видов:
17
а) для букв L, R, P;
б) для букв внешнего алфавита;
в) для букв, изображающих состояния машины.
Возможна следующая таблица кодирования:
Алфавит
Буква
Буквы
адресов
L
101
1 нуль между 1
P
1001
2 нуля между 1
3 нуля между 1
Внешний
алфавит
Внутренний
алфавит
Кодовая группа
R
10001
a0
100001 4 нуля
a1
10000001 6 нулей
...
...
an
10...01 2(n+2) нулей
q1
1000001 5 нулей
q2
100000001 7 нулей
...
...
qn
10...01 2(n+1)+1 нулей
Примечания
Четное число нулей
больше двух
Нечетное число
нулей больше трех
Если в строке (1) считать *, α, β соответственно буквами a1, a2,
a3, то при такой системе кодирования строку (1) записывают так:
10000110000011000011000110000000001100000011000000001…
Такую строку из нулей и единиц, составленную для функциональной схемы или конфигурации, назовем шифром функциональной схемы, или шифром конфигурации. В частности, на ленте некоторой машины Тьюринга может оказаться ее же собственный
шифр. Тогда возможны два случая:
1) машина применима к своему шифру, т. е. она перерабатывает
свой шифр и после конечного числа шагов останавливается;
2) машина не применима к своему шифру, т. е. она никогда не
перейдет в стоп-состояние.
Таким образом, машины Тьюринга разбивают на два класса: самоприменимых и несамоприменимых машин Тьюринга. Возникает следующая массовая проблема – проблема распознавания самоприменимости: по любому заданному шифру установить, к какому
классу относится машина, зашифрованная им, – к классу самоприменимых или несамоприменимых машин?
Теорема. Проблема распознавания самоприменимости алгоритмически неразрешима.
18
Д о к а з а т е л ь с т в о . Допустим, что машина Тьюринга, решающая эту проблему, существует. Такая машина может преобразовывать шифр любой самоприменимой машины Тьюринга в символ s,
а шифр любой несамоприменимой машины – в символ t. Однако
тогда может существовать и машина Тьюринга, которая не применима к шифрам самоприменимых машин, но применима к шифрам
несамоприменимых. Действительно, для этого достаточно так изменить программу машины, чтобы, получив символ s, она не останавливалась, а бесконечно повторяла этот символ. Следовательно,
такая машина применима к шифрам несамоприменимых машин и
не применима к шифрам самоприменимых. Но она также должна
иметь шифр.
Попробуем ответить на вопрос: применима ли эта машина к своему шифру? Если машина применима к своему шифру, то она является самоприменимой, но эта машина не применима к шифрам
самоприменимых машин. Следовательно, она не может быть применима к своему шифру. Но тогда она является несамоприменимой
машиной, а этого тоже не может быть, потому что она применима
ко всем несамоприменимым машинам. Полученное противоречие и
доказывает теорему.
Обращает на себя внимание сходство этого доказательства с известным парадоксом Рассела: «В некотором селе живет парикмахермужчина, который бреет всех тех и только тех мужчин села, которые не бреются сами. Бреет ли этот парикмахер себя?».
Очевидно, что само определение такого парикмахера внутренне
противоречиво. Может быть, и определение той машины Тьюринга, которая решает, является ли данная машина (вообще говоря,
другая) самоприменимой, тоже противоречиво?
Обратим внимание и на то, что в теореме Тьюринга речь идет о
построении некоторого отображения множества машин Тьюринга в
множество, состоящее из двух элементов, и доказывается, что оно
не может быть реализовано с помощью машины Тьюринга. И это не
удивительно: множество машин Тьюринга счетно, поэтому множество отображений данного множества в любое другое должно иметь
мощность, строго большую мощности счетного множества, и обязательно включать в себя такие отображения, которые не могут быть
реализованы с помощью машины Тьюринга.
Причина парадокса Рассела та же самая: каждому парикмахеру соответствует некоторое отображение множества мужчин села в
двухэлементное множество, состоящее из элементов «брить» и «не
брить». Однако таких отображений 2n, где n – число мужчин села,
19
а 2n строго больше n. Поэтому среди этих отображений наверняка
имеются такие, которым нет соответствия во множестве мужчин
села.
Перейдем к следующему утверждению: не все задачи о построении алгоритмов могут быть алгоритмизированы, если понятие алгоритма определяется через определение машины Тьюринга.
Можно было бы высказать следующее предположение: существование алгоритма определяется наличием некоторых закономерностей, внешних по отношению к той системе понятий, в которой действует этот алгоритм, и неизвестных в этой системе. Построение алгоритма требует выяснения указанных закономерностей,
что очевидно невозможно в самой этой системе.
Этому предположению противоречат две теоремы Геделя.
Первая теорема Геделя (о неполноте). В любой непротиворечивой формальной системе, содержащей минимум арифметики, а
следовательно, и в теории натуральных чисел найдется формально
неразрешимое суждение, т. е. такая замкнутая формула A, что ни
A, ни A не являются выводимыми.
Вторая теорема Геделя (о неполноте) утверждает, что при выполнении естественных дополнительных условий в качестве A
можно взять утверждение о непротиворечивости рассматриваемой
системы.
Очевидно, что формальный вывод представляет собой некоторый алгоритм. Вместе с тем, казалось бы, в теории натуральных
чисел все основные закономерности известны. И все-таки в этой
теории существует такая замкнутая формула A, что ни A, ни A не
являются выводимыми. О каких же формулах здесь идет речь? Повидимому, это не теоремы типа теорем о признаках делимости или
теоремы Ферма о том, что уравнение
xn+yn = zn
не имеет решений в целых числах при любых натуральных n больше 2, т. е. не утверждения о самих натуральных числах. По второй
теореме Геделя таковым является утверждение, что аксиомы этой
теории обладают некоторым свойством – непротиворечивостью.
Иначе говоря, это есть предикат, предметным множеством которого являются аксиомы теории, т. е. также предикаты.
По-видимому, хотя бы некоторые из утверждений аксиом
теории не являются ее частью, а представляют собой элементы метатеории («надтеории») и из аксиом ее выведены быть не могут.
20
Аналогично операция над алгоритмами может не принадлежать
к множеству алгоритмов, т. е. не может быть реализуема никакой
машиной Тьюринга.
Возникает естественный вопрос: как человек решает задачу о
построении алгоритма? Этот вопрос выходит за рамки теории алгоритмов, им занимаются философы и психологи, а математик может лишь высказывать предположения, основываясь на личном
опыте.
Очевидно, что прежде всего осознается, анализируется проблема, которую должен решать алгоритм. Отыскиваются аналогичные
проблемы, алгоритмы решения которых известны. Проверяется,
не могут ли эти алгоритмы быть применены и к данной проблеме.
Если это возможно, то алгоритм найден, в противном случае, может быть, искомый алгоритм получают путем некоторого изменения какого-либо из известных. Какое же изменение необходимо?
Чаще всего приходится пользоваться универсальным методом проб
и ошибок. А когда алгоритм сформулирован, его необходимо проверить. Вместе с тем алгоритм – это метод решения массовой проблемы, т. е. он должен быть применим к множеству задач, обычно
бесконечному, проверить же его можно лишь на конечном подмножестве этих задач.
Все это не укладывается в рамки алгоритма.
Интересно сравнить, как человек и машина играют в шахматы.
Машина просматривает все свои возможные по правилам ходы, все
возможные ответы противника на каждый них, каждый из своих
возможных ответов и т. д., на столько ходов вперед, на сколько это
предусмотрено программой, а затем выбирает ту их последовательность, которая приводит к лучшей для нее позиции, причем оценка позиции производится в соответствии с четкими, однозначно
определенными критериями. Просматриваются даже те ходы, бесполезность или вредность которых очевидна для любого новичка.
Работа машины, конечно, абсолютно алгоритмична.
Человек играет совершенно иначе. В некоторых случаях и он делает вынужденные ходы, выбор которых однозначен. Существуют
стандартные позиции, способы (алгоритмы) достижения победы
или ничьей в которых хорошо известны. Но чаще всего есть выбор.
Если игрок играет белыми, первая задача, которую он решает, – выбор начального хода. При этом принимается во внимание, в каких
дебютах силен он, а в каких – противник, турнирное положение и
другие факторы. Эти факторы могут противоречить друг другу, а
роль их трудно оценить. Какое-то начало все-таки выбирается!
21
В процессе игры человек рассматривает обычно только те ходы,
которые согласуются с требованиями борьбы за центр, активизации
его фигур и, наоборот, уменьшения активности фигур противника,
укрепления собственной позиции. При этом он может пожертвовать фигуру. Если же игрок-человек замечает, что может провести
комбинацию, способствующую выигрышу фигуры или мату королю противника, он может даже проигнорировать эти требования и
очевидно не будет пользоваться при этом алгоритмами.
На чем же основан алгоритм, которым пользуется машина?
Прежде всего он строится на правилах игры, которые выполняют
роль аксиом. Вместе с тем при выборе хода используются заданные
критерии оценки позиции. Эти оценки выражаются числами. Кем
выражаются и как? Очевидно, программистами с помощью шахматистов, и данные оценки зависят от того, кто делает этот выбор.
Известно, что проводятся соревнования и между машинами. Таким
образом, алгоритмы, реализуемые в шахматных машинах, разрабатываются неалгоритмически. Можно думать, что это пример интуиции в том смысле, который придавал этому слову философ Бенедикт Спиноза.
По Спинозе, существуют три способа познания: чувственный,
логический и интуитивный. Обычно под интуицией понимают угадывание истины, озарение, при этом предполагается, что логический процесс происходит, но не осознается. Однако интуиция, по
Спинозе, – совсем другое, это целостное восприятие истины, которое в принципе не может опираться на точные логические выводы.
Это не мгновенное озарение (иначе не было бы цейтнотов): человек,
делая интуитивный вывод, основывается на совокупности всех своих знаний, опыте, мировоззрении.
Алгоритм строится согласно интуиции. Можно ли построить
компьютер, обладающий интуицией? Совершенно очевидно, что
машина Тьюринга обладать интуицией не может. Из этого следует,
что только компьютер, принципиально отличающийся от машины
Тьюринга, может руководствоваться интуицией. Однако возможно
ли существование такого компьютера? Это, по-видимому, пока еще
не известно.
22
ЛИТЕРАТУРА
1. Мальцев, А. И. Алгоритмы и рекурсивные функции /
А. И. Мальцев. М.: Наука, 1986. 368 с.
2. Гиндикин, С. Г. Алгебра логики в задачах / С. Г. Гиндикин.
М.: Наука, 1972. 288 с.
3. Лихтарников, Л. М. Математическая логика: курс лекций.
Задачник-практикум и решения / Л. М. Лихтарников, Т. Г. Сукачева. СПб.: Лань, 1999. 285 с.
4. Шапорев, С. Д. Математическая логика: курс лекций и практических занятий / С. Д. Шапорев. СПб.: БХВ-Петербург, 2007.
410 с.
5. Судоплатов, С. В. Математическая логика и теория алгоритмов / С. В. Судоплатов, Е. В. Овчинникова. М.; Новосибирск:
НГТУ, 2004. 224 с.
23
Содержание
1. Понятие алгоритма..................................................... 2. Рекурсивные функции................................................ 2.1. Вычислимые функции. Примитивно рекурсивные
функции .................................................................. 2.2. Частично рекурсивные функции. Тезис Черча ......... 3. Машины Тьюринга..................................................... Литература................................................................... 3
5
5
9
11
23
Документ
Категория
Без категории
Просмотров
0
Размер файла
273 Кб
Теги
0c86603109, djakova
1/--страниц
Пожаловаться на содержимое документа