Тема 9 Элементы теории алгоритмов

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

9.2 Рекуррентные функции

9.3 Тезисы Тьюринга и Чёрча

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

Многочисленные и разнообразные алгоритмы окружают нас буквально во всех сферах жизни и деятельности.

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

В начале ХХ века у математиков начали возникать подозрения в том, что некоторые массовые задачи, по-видимому, не имеют алгоритмического решения. Для точного доказательства несуществования алгоритма необходимо иметь его точное математическое определение. Первые работы по уточнению понятия алгоритма и его изучению были выполнены в 1936–1937 гг. А. Тьюрингом, Э. Постом, К. Геделем, А. А. Марковым, А. Черчем. Было выработано несколько определений понятия алгоритма, но впоследствии выяснилось, что все они равносильны между собой, то есть определяют одно и то же понятие.

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

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

Лента разбита на ячейки. Во всякой ячейки в каждый момент времени находится в точности один символ из внешнего алфавита А={а0,а1,…аn-1 }, n2. Некоторый символ алфавита А называется пустым, любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой. В дальнейшем в качестве внешнего алфавита будем использовать А={0,1}, где в качестве пустого символа будем использовать 0(нуль). В каждый момент времени лента содержит конечное число ячеек, но в процессе работы машины можно пристраивать новые ячейки в пустом состоянии.

Управляющее устройство в каждый момент времени находит в некотором состоянии qi, принадлежащее множеству Q{q0,q1,…,qr-1}, r1. Множество Q называется внутренним алфавитом. В дальнейшем начальное состояние будем обозначать символом q1, а заключительное символом q0 .

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

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

1. qi aj →qk ae

2. qi aj →qk ae R

3. qi aj →qk ae L

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

Команда 2 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю справа ячейку.

Команда 3 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю слева ячейку.

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

Машинным словом или конфигурацией называется слово вида

Ai1,ai2,…,qkait,…, aik,

Где аijА, qkQ. Символ qk пишется перед символом обозреваемой ячейки. Причем символ qk может быть самым левым, но не может быть самым правым. В дальнейшем будем использовать следующие обозначение аin обозначает слово аi аi …аi =

Например, конфигурация 13q10212 на ленте выглядит следующим образом:

▼q1

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

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

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

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

Во втором случае говорят, что машина не применима к слову Р.

Пример 1: Выяснить, применима ли машина Тьюринга, задаваемая следующей программой

Q10→ q20 R, q11→ q11 R, q20→ q30 R, q21→ q11 L, q30→ q00 , q31→ q21 R, к слову
Р= q1 130212.

▼q1

q11→ q11 R 13 q10212

▼q2

q10→ q20 R 130 q2012

▼q3

q20→ q30 R 1302 q312

▼q2

q31→ q21 R 13021 q21

▼q1

q21→ q11 L 1302 q112

▼q1

q11→ q11 R 130212 q10

▼q2

q10→ q20 R 130212 0q20

▼q3

q20→ q30 R 130212 02q30

▼q0

q30→ q00 130212 02q00

Следовательно, данная машина Тьюринга применима к слову Р и заключительная конфигурация имеет вид: 13021202q00.

В дальнейшем запись МM , будет означать, что машина Тьюринга (Т) через конечное число циклов перерабатывает машинное слово М в машинное слово М1.

Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая её.

Во-первых, напомним, что речь идёт о частично-числовых функциях. Во-вторых, договоримся, что значения х1, х 2 … х аргументов функции f(х1, х2 … хn) на ленте будут записываться следующим образом:

Или .

Начинать переработку данного слова будем из стандартного положения, то есть из положения, при котором в состоянии q1 обозревается крайняя правая единица описанного слова. Если функция F(Х1, х 2 … хN) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд F(Х1, х 2 … хN) единиц, в противном случае, машина должна работать бесконечно. При выполнении всех перечисленных условий, будем говорить, что машина Тьюринг вычисляет данную функцию F.

Пример 2: Построить машину Тьюринга, вычисляющую функцию О(х)=0. Для этого надо сконструировать машину Тьюринга (Т), (т. е. составить программу) которая начинает работу со слова q101(х – любое натуральное число) останавливается, когда на ленте нет единиц. q101=>q0

Данная программа имеет вид:

Q10à q20R

Q20 à q0O

Q21à q20R

Пример 3: Построить машину Тьюринга, вычисляющую функцию: F(X,y)=X+y. Построим машину Тьюринга (Т), которая, начиная работу со слова q10101 останавливается когда на ленте Х+у единиц q0101=>q01

Q10 à q20R q20

Q0 à qOR q0

Q1à q1 q0

Q1 à q1R Q01

Q0 à Q1 Q1

Q1 à q1L q01

Q0 à q0R q1

Q5 1à q0 q01

Пример 4: Построить машину Тьюринга, вычисляющую функцию F(X)=2/X. Эта функция не всюду определена. Лишь при Х=1, Х=2, её значения являются натуральные числа 2 и 1 соответственно. Поэтому можно построить машину Тьюринга, которая начинает работу либо со слова q101, либо q1012останавливается, когда на ленте две единицы, одна единица соответственно. В остальных случаях машина начинает работу со слов q2 (Х ≠1, Х ≠2) работает бесконечно. Такая машина задаётся следующей программой:

Q0 à q0R q

Q0 à q0

Q1 à q1R 1 q1

Q0 à q1L q,

Q1 à q1R q1

Q1 à q1

Q40 à q50L 1 q51

Q51 à q00L q01,

9.2 Рекуррентные функции. В дальнейшем под множеством натуральных чисел N Будем понимать множество N={0,1,2,…,K,…}

Пусть Y= F(X1, X2,…, Xn) – функция от N Переменных. Обозначим D(Y) – область определения функции Y= F(X1, X2,…, Xn) E(Y) – область значений функции Y= F(X1, X2,…, Xn)

Функция Y=F(X1, X2,…, Xn) Называется числовой функцией, если:

1) D(Y)=N ×∙ N ∙× …×∙ N =;

2) E(Y) N

Функция Y=F(X1, X2,…, Xn) Называется частично числовой функцией, если: 1) D(Y)N ×∙ N∙×…×∙N =;

2) E(Y)N

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

1) O(X)=0 – нуль-функция

2) (X1, X2,…, Xn)=Xm , 1≤ M≤ N – Функция повторяющая значение своих аргументов;

3) S(X)=X+1 – функция следования.

Определим следующие три операции: суперпозиции, примитивной рекурсии и минимизации.

Операция суперпозиции

Будем говорить, что N – местная функция φ Получается из M – местной функции ψ и N – местных функций F1,F2,…,Fm с помощью операции суперпозиции, если для всех X1,X2,…,Xn Справедливо равенство:

φ (X1,X2,…,Xn)=ψ( F1(X1, X2,…, Xn),…, Fm(X1, X2,…, Xn))

Операция примитивной рекурсии

Будем говорить, что (N+1) – местная функция F Получается из N – местной функции g и (N+2) – местной функции H с помощью операции примитивной рекурсии, если при любых значениях X1, X2,…, Xn Выполняется равенства:

F(x1, x2,…, xn, 0)=g (x1, x2,…, xn)

F(x1, x2,…, xn, 1)= h(x1, x2,…, xn, 0, f(x1, x2,…, xn, 0))

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

F(x1, x2,…, xn, y+1)=h(x1, x2,…, xn, y,f(x1, x2,…, xn, y))

Эти равенства называют схемой примитивной рекурсии. И тот факт, что функция F Получается из функций G, H C помощью операции примитивной рекурсии, записывается следующим образом: F=R(G,H).

Определение 1. Функция F называется примитивно рекурсивной функцией, если она получается из простейших функций с помощью операций суперпозиции и примитивной рекурсии, взятых конечное число раз в любой последовательности.

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

Множество всех примитивно рекурсивных функций обозначим через Pn.P.

Пример 1.

Доказать, что функция F(X,Y)= X+Y примитивно рекурсивна.

Действительно. Справедливы следующие тождества

F(X,0)=X+0=X=G( X)

F(x, y+1)=x+(y+1)=(x+y)+1 =f(x, y)+1

Отсюда следует, что

X+Y=R(G(X)=X, H(X,Y,Z)=Z+1)

Так как функции G, H – Простейшие функции, то X + Y Pn.P.

Пример 2.

Доказать, что функция F(X,Y)=X∙Y Примитивно рекурсивна.

Действительно. Справедливы следующие тождества:

F(X,0)=X∙0=0=G(X)

F(X,Y+1)=X(Y+1)=Xy+X=F(X, Y) +X

Отсюда следует, что

X+Y=R(G(X)=0, H(X,Y ,Z)=Z+X)

Как следует из примера 1 функция H(X,Y,Z)=X+Z Pn.P. А это значит, что Xy Pn.P.

Рассмотрим функцию

XY=

Данную функцию называют усечённой разностью.

Пример 3.

Показать, что функция F(X,Y)=XY Примитивно рекурсивна.

В начале заметим, что функция X1 Примитивно рекурсивна. Действительно:

01=0=G(X)

(X+1) 1=X=H(X,Y)

Следовательно,

X1=R(G(X)=0,H(X,Y)=X).

Итак, X1Pn.P.

Далее, нетрудно показать, исходя из определения усечённой разности, что эти функции удовлетворяют также равенствам:

X0=x=g(x)

x(y+1)=(xY) 1=h(x, y,xY)

Для любых X И Y. Данные тождества показывают, что

XY=R(g(x)=0, h(x, y,z)=z α)

Так как функция H(X,Y,Z)=Z α Pn.P., То XY Pn.P.

Так как любая примитивно рекурсивная функция является числовой функцией, то, очевидно, что X–Y Pn.P.

Пример 4.

Покажем, что – примитивно рекурсивная функция.

Действительно. Нетрудно показать, что =(XY)+(Y X)

Теперь полученный результат следует из примера 1 и примера 3.

Операция минимизации. Будем говорить, что n-местная функция G(x1,x2,…,xn) полученная из (n+1)-местной функции F(x1,x2,…,xn, y) с помощью операции минимизации или оператора наименьшего числа, если для любых x1,x2,…,xn, y равенство g(x1,x2,…,xn)=y выполняется тогда и только тогда, когда:

1) F(x1,x2,…,xn, t) определено и F(x1,x2,…,xn, t)>0 для любых 0≤t<y;

2) F(x1,x2,…,xn, y)=0.

Если какое-либо из условий 1), 2) будет невыполнено, то функция G(x1,x2,…,xn) не определена при наборе x1,x2,…,xn. Короче говоря, величина G(x1,x2,…,xn) равна наименьшему значению аргумента y, при котором выполняется последнее равенство.

Используется следующее обозначение: G(x1,x2,…,xn) = My[F(x1,x2,…,xn, y)=0].

Про функцию g говорят, что она получена из функции F при помощи операции минимизации.

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

Класс частично рекурсивных функций обозначим Prp.

Обозначим через Pp - класс рекурсивных функций, т. е. всех числовых функций из Prp.

Пример 5: Доказать, что частично числовая функция частично рекурсивна.

Вначале заметим, что данная функция получается из функции С помощью операции минимизации, т. е. = My.

Согласно примерам 2 и 4 функция примитивно рекурсивна. А это значит, что - частично рекурсивная функция.

Данный пример показывает, что класс Prp существенно шире, чем класс Pp. Можно сказать, что и класс Pp существенно шире, чем класс Pnp, т. е. Pnp С Pp С Prp

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

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

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

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

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

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

Подобно тезису Тьюринга в теории рекурсивной функции выдвигается соответствующая гипотеза, носящая название тезиса Чёрча.

Тезис Чёрча. Числовая функция тогда и только тогда алгоритмически вычислима, когда она рекурсивна.

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

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

Теорема. Следующие классы функций (заданные на натуральных числах и принимающие натуральное значение) совпадают.

1) Класс всех функций вычислимых по Тьюрингу;

2) Класс всех рекурсивных функций.

Это уже не гипотеза и не тезис, а математическая теорема, которая строго доказывается.

Можно отметить, что существуют ещё и другие теории алгоритмов, и для всех них также доказана их равнозначность с рассматриваемыми теориями.

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

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

Диофантово уравнение есть уравнение вида где – многочлен с целыми показателями степеней и целыми коэффициентами. В общем случае эта проблема долго оставалась нерешенной и только в 1970 году советский математик Ю. В.Матиясевич доказал её неразрешимость.

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

Хорошо известно, что все его целые корни следует искать среди делителей свободного члена

Вопросы для самоконтроля

1. Что Вы понимаете под машиной Тьюринга?

2. Из каких частей состоит машина Тьюринга?

3. Дайте определение машинного слова.

4. Какая функция называется числовой?

5. Какая функция называется частично-числовой?

6. Дайте определение функции, вычислимой по Тьюрингу.

7. Какие функции называются простейшими?

8. Дайте определение операции суперпозиции.

9. Дайте определение операции примитивной рекурсии.

10. Дайте определение операции минимизации.

11. Сформулируйте тезис Черча.

12. Сформулируйте тезис Тьюринга.

13. Какая связь между функциями вычислимых по Тьюрингу и частично рекурсивными функциями?

< Предыдущая