Кацаран Т.К., Строева Л.Н. Машина Тьюринга и рекурсивные функции
Подождите немного. Документ загружается.
21
Решение. Будем предполагать, что перед началом работы на ленте
машины записаны исходные значения аргумента и считывающая головка
обозревает первый слева значащий символ (см. рис. 1). Кроме того, после
выполнения вычислений считывающая головка останавливается в заклю-
чительной конфигурации.
Прежде чем приступить к написанию программы работы машины
Тьюринга, следует определить порядок ее работы для получения результата.
В нашем случае после окончания работы машины на ленте должно быть за-
нято на одну ячейку больше, чем на ней занято ячеек перед началом работы.
Команды этой машины могут быть определены следующим образом:
,11
11
Пqq
®
.1
01
Hqq
®
L
Работа машины
3
T
при вычислении
)
1
(
f
состоит из конфигураций:
¯
1 1
1
q
Рис. 1
¯
1 1
1
q
Рис. 2
¯
1 1
L
1
q
Рис. 3
¯
1 1 1
0
q
Рис. 4
22
Очевидно, что наилучший способ выполнить это требование состоит в
следующем. После начала работы считывающая головка машины должна пе-
реместиться на одну ячейку влево, записать в пустую ячейку 1 и остановиться.
Первая команда имеет вид:
11
11 Пqq
®
(см. рис. 2).
Согласно этой команде, машина, находясь в состоянии
1
q , читает сим-
вол 1, записанный в обозреваемой ячейке, оставляет этот символ в ячейке,
остается в прежнем состоянии
1
q и сдвигается на одну ячейку ленты вправо.
Вторая команда имеет вид:
01
1Hqq
®
L
(см. рис. 3).
Таким образом, согласно этой команде, машина, находясь в состоя-
нии
1
q , читает пустой символ, записанный в обозреваемой ячейке, записы-
вает на его место символ 1, переходит в состояние
0
q и останавливается.
Программа работы машины Тьюринга также может быть записана в
виде таблицы. Столбцам таблицы соответствуют символы внешнего алфа-
вита, а строкам – состояние машины.
В рассматриваемом примере таблицы работы машины Тьюринга
имеет вид:
L
1
1
q 1 Н
0
q 1П
1
q
Пример 6. Построить машину
4
T , вычисляющую числовую функ-
цию
.
)
,
(
y
x
y
x
f
+
=
Решение. Пусть внешним алфавитом данной машины является алфа-
вит
}
1
,
{
L
. Работа машины состоит из конфигураций:
,11
11
Пqq
®
,1
21
Пqq
®
L
,11
22
Пqq
®
,
32
Лqq
L
®
L
,1
43
Лqq
L
®
.1
04
Лqq
L
®
Следует отметить, что для данной машины
4
T выписаны все коман-
ды, осуществляющие вычисление функции
.
)
,
(
y
x
y
x
f
+
=
23
Замечание. Все арифметические операции представляют собой вы-
числимые по Тьюрингу функции.
§ 3. Задачи и упражнения для самостоятельного решения
1. Построить машину Тьюринга, вычисляющую нуль-функцию 0 (x) = 0
в алфавите {L, 1}.
Указание: Взять множество
Q
= {
0
q ,
1
q }, подставить вместо всех
единиц L, а когда встретиться символ L, то подставить символ 1.
2. Вычисляет ли МТ в алфавите {L,1 }
1) с программой
q
1
q
2
q
3
L
1 Л
2
q
L П
0
q
L Н
0
q
1
1 Н
3
q
L Л
3
q
функцию
î
í
ì
¹
=
=
.0 если ,0
,0 если ,1
x
x
xsign
2) с программой
q
1
q
2
q
3
q
4
L
L Л
2
q
L П
0
q
L П
4
q L П
4
q
1
1 Л
3
q
L Л
3
q 1 Н
0
q
функцию
î
í
ì
¹
=
=
.0 если ,1
,0 если ,0
x
x
xsign
24
3. Построить машину Тьюринга, которая вычисляет функцию:
1)
y
x
y
x
f
×
=
)
,
(
; 2)
2
)( xxf = ;
3) функцию выбора аргумента
2321
)3(
2
),,( xxxxJ == .
4*. Реализовать на МТ алгоритм вычисления функции
2
)
(
+
=
n
n
f
,
где
N
n
Î
.
Указание: Взять множество состояний
Q
= {
0
q ,
1
q ,
2
q }. Число n на ленте
МТ записывается в десятичной системе счисления. Состояние
1
q заменяет
последнюю цифру числа n, если эта цифра меньше 8, цифрой, на две еди-
ницы большей, и переходит в стоп-состояние. Если последняя цифра числа
n равна 8, то ее заменить на 0 и перейти влево в состояние
2
q . Состояние
2
q добавляет к следующему разряду 1. Если же последняя цифра числа n
равна 9, то ее заменить на 1 и перейти влево в состояние
2
q .
25
3. РЕКУРСИВНЫЕ ФУНКЦИИ
§ 1. Элементарные функции.
Правила подстановки и примитивная рекурсия
Всякий алгоритм однозначно ставит в соответствие исходным дан-
ным (в случае если, он определен на них) результат. Поэтому с каждым ал-
горитмом однозначно связана функция, которую он вычисляет. Исследо-
вание проблемы остановки машины Тьюринга показывает, что не для вся-
кой функции существует вычисляющий ее алгоритм. Поэтому в 30-х годах
ХХ века была создана теория рекурсивных функций. В этой теории, как и
вообще в теории алгоритмов, принят конструктивный, финитный подход,
основной чертой которого является то, что все множество исследуемых
объектов (в нашем случае функции) строится из конечного числа исход-
ных объектов – базиса – с помощью простых операций, эффективная вы-
полнимость которых достаточно очевидна. Операции над функциями в
дальнейшем будем называть операторами.
Пусть имеется некоторый алгоритм α. Областью применимости ал-
горитма α называют совокупность тех объектов, к которым он применим.
Говорят, что алгоритм α вычисляет функцию
f
, если его область при-
менимости совпадает с областью определения функции
f
, и алгоритм α пе-
рерабатывает всякий элемент x из своей области применимости в
)
(
x
f
.
Американскими математиками Клини, а впоследствии Черчем были
строго определены математические функции, называемые примитивно-
рекурсивными. Черч высказал гипотезу о том, что множество всех рекурсив-
ных функций совпадает с множеством всех вычислимых функций. Это пред-
положение получило название тезиса Черча. Гипотеза Черча не может быть
доказана, поскольку использует нестрогое понятие вычислимой функции.
26
Позже американские математики Пост и впоследствии Тьюринг вве-
ли понятие математической машины, которую называют машиной Поста
или машиной Тьюринга (см. главу 1 «Машина Тьюринга»). Тьюринг вы-
сказал гипотезу (известную также как тезис Тьюринга) о том, что для вся-
кой вычислимой функции может быть построена машина Тьюринга. Этот
тезис также не может быть доказан, так как включает нестрогое понятие
вычислимой функции.
Доказано, что для всякой рекурсивной функции может быть по-
строена машина Тьюринга и, обратно, всякая машина Тьюринга вычисляет
рекурсивную функцию.
Известны также другие способы уточнения понятия алгоритма, на-
пример, нормальный алгоритм Маркова.
Практический опыт показывает, что тезисы Черча и Тьюринга явля-
ются верными, не имеется ни одного опровержения этих утверждений.
Дадим элементарное определение рекурсивных функций.
Рекурсивные функции – это функции, определенные некоторым спе-
циальным образом. Из названия следует, что их вычисление содержит об-
ращение к самим себе (при меньших значениях аргументов). Подразумева-
ется, что рекурсивные функции являются арифметическими функциями,
т. е. область их определения и область значений является подмножеством
множества
0
N или совпадает с ним.
Введем следующие правила для получения новых функций из уже
имеющихся, которые упоминались в разделе 2:
1) нуль функция:
x
x
o
=
)
(
при каждом
0
Nx
Î
;
2) функция следования:
1
)
(
+
=
x
x
s
при каждом
0
Nx
Î
; (3)
3) функция выбора аргумента:
mn
n
m
xxxxI =),...,,(
21
)(
при всех
n
n
Nxx
01
)..., ,( Î , nm ,1= ,
...
3
,
2
,
1
=
n
27
Операция суперпозиции (подстановка) заключается в подстановке
одних рекурсивных функций вместо аргументов в другие рекурсивные
функции.
Пусть даны числовые функции ),...,(
1 m
xxf , ),...,(
11 n
xxg , ),...,(
12 n
xxg ,
…, ),...,(
1 nm
xxg и пусть
)),...,(),...,,...,((),...,(
1111 nmnn
xxgxxgfxxh
=
.
Тогда будем говорить, что функция
h
получена с помощью подстановки
из функций ),...,(
1 m
xxf , ),...,(
11 n
xxg , ),...,(
12 n
xxg , …, ),...,(
1 nm
xxg .
Например, функция 0),...,(
1
=
n
xxo получается с помощью подстановки
из функций
)
(
x
o
и
mn
n
m
xxxxI =),...,,(
21
)(
: )),...,,((),...,(
21
)(
1 n
n
mn
xxxIoxxo = . А
функция 1),...,,(
21
)(
+=
mn
n
m
xxxxs – из функций
)
(
x
s
и
mn
n
m
xxxxI =),...,,(
21
)(
:
)).,...,,((),...,,(
21
)(
21
)(
n
n
mn
n
m
xxxIsxxxs =
Рассмотрим операцию примитивной рекурсии. Эта операция строит
функцию от n+1 аргументов, если имеются две числовые функции
),...,(
1 n
xxg и функция ),,,...,(
211 ++ nnn
xxxxh (функция от n+2 аргументов,
1
³
n
). Таким образом, если требуется построить функцию от некоторого
числа аргументов, необходимо иметь две функции: одна из них g зависит
от числа аргументов, которое на единицу меньше, чем число аргументов в
строящейся функции
f
, а вторая функция
h
зависит от числа аргументов
на единицу большего числа аргументов функции
f
.
Операция примитивной рекурсии определяется следующим образом:
11
111
(,...,,0)(,...,)
.
(,...,,1)(,...,,,(,...,,))
nn
nnn
fxxgxx
fxxyhxxyfxxy
ì
=
ï
ï
í
ï
+=
ï
î
В развернутом виде имеем, когда y = 0:
),...,()0,,...,(
11 nn
xxgxxf
=
.
Если y = 1, то
111
(,...,,1)(,...,,0,(,...,,0)).
nnn
fxxhxxfxx
=
Если y = 2, то ))1,,...,(,1,,...,()2,,...,(
111 nnn
xxfxxhxxf
=
и т. д.
28
Иногда операцию примитивной рекурсии обозначают
)
,
(
h
g
R
f
=
.
Заметим, что операция примитивной рекурсии фактически строит таблицу
значений новой функции f.
Определение. Функция называется примитивно-рекурсивной, если
она может быть получена из исходных функций (3) с помощью конечного
числа подстановок и примитивных рекурсий.
Определение. Функция называется примитивно-рекурсивной, если
она может быть записана с помощью элементарных рекурсивных функ-
ций с использованием конечного числа операций суперпозиции и примитив-
ной рекурсии.
Определение. Функция называется частичной, если она определена
не для всех значений аргументов.
Пример 7. Доказать, что функция
y
x
y
x
f
+
=
)
,
(
является прими-
тивно-рекурсивной.
Решение. Так как заданная функция является функцией двух аргу-
ментов, то для использования операции примитивной рекурсии мы долж-
ны иметь функцию
g
, зависящую от одного аргумента, и функцию
h
, за-
висящую от трех аргументов. Определим эти функции.
В функции
y
x
y
x
f
+
=
)
,
(
положим
0
=
y
. Тогда имеем
x
x
f
=
)
0
,
(
–
это тоже тождественная функция. Полагая
1
=
y
, получим
1
)
1
,
(
+
=
x
x
f
–
это функция следования.
Таким образом, выбираем следующие элементарные функции: тож-
дественную
x
x
g
=
)
(
и функцию следования
1
)
,
,
(
+
=
z
z
y
x
h
. Заметим, что
здесь ))(,,(),,(
3
3
xsyxIzyxh = .
Используя схему примитивной рекурсии:
,
)
(
)
0
,
(
x
x
g
x
f
=
=
,
1
1
)
0
,
(
))
0
,
(
,
0
,
(
)
1
,
(
+
=
+
=
=
x
x
f
x
f
x
h
x
f
29
,
2
1
)
1
,
(
))
1
,
(
,
1
,
(
)
2
,
(
+
=
+
=
=
x
x
f
x
f
x
h
x
f
.
1
1
))
1
,
(
,
1
,
(
)
,
(
y
x
y
x
y
x
f
y
x
h
y
x
f
+
=
+
-
+
=
-
-
=
Таким образом, построена функция (таблица ее значений), которая
равна сумме двух слагаемых.
В дальнейшем, если нужно доказать примитивную рекурсивность
некоторой функции, можно использовать не только элементарные ре-
курсивные функции, но и те функции, примитивная рекурсивность кото-
рых уже доказана. Например, можно использовать функцию из выше
рассмотренного примера.
Так как исходные функции являются всюду определенными и опе-
рации подстановки и примитивной рекурсии сохраняют всюду опреде-
ленность, то из определения примитивно-рекурсивной функции следует,
что каждая примитивно рекурсивная функция является всюду опреде-
ленной.
§ 2. Правило взятия μ-оператора. Классы функций
Рассмотрим еще одну операцию, называемую
m
-оператором. Пусть
),,...,(
1
yxxg
n
– произвольная числовая функция. Зафиксируем значения
n
xxx ,...,,
21
и через ]0),,...,([
1
=
yxxgy
n
m
обозначим наименьшее число
y
такое, что:
1) для всех
t
,
y
t
<
£
0
, ),,...,(
1
txxg
n
определено и больше нуля;
2) ),,...,(
1
yxxg
n
определено и равно нулю.
Если же одно из этих условий не выполнено, т. е. для некоторого
t
),,...,(
1
txxg
n
не определено или же не для всех
z
),,...,(
1
zxxg
n
определено и
больше нуля, будем считать, что выражение ]0),,...,([
1
=
yxxgy
n
m
не опре-
делено.
30
Пример 8. Пусть дана функция
3
)
,
(
-
-
=
y
x
y
x
g
. Тогда
1
]
0
3
4
[
=
=
-
-
y
y
m
, так как
0
1
3
0
4
¹
=
-
-
,
0
3
1
4
=
-
-
.
0
]
0
3
3
[
=
=
-
-
y
y
m
, а
]
0
)
,
0
(
[
=
y
g
y
m
,
]
0
)
,
1
(
[
=
y
g
y
m
и
]
0
)
,
2
(
[
=
y
g
y
m
не определены, потому что
3
0
-
-
k
, где
2
,
1
,
0
=
k
в области натуральных чисел не определено.
Пусть ]0),,...,([),...,(
11
=
=
yxxgyxxf
nn
m
. В этом случае говорят, что
функция
f
получена из функции
g
с помощью
m
-оператора.
Пример 9. Пусть ]034[)(
1
=
-
-
=
yyxf
m
, тогда )(
1
xf получается из
3
)
,
(
-
-
=
y
x
y
x
g
с помощью
m
-оператора. Так функция
3
)
,
(
-
-
=
y
x
y
x
g
не
является всюду определенной, то и значения )0(
1
f , )1(
1
f и )2(
1
f не опре-
делены.
Пример 10. Функция ]034[)(
2
=
-
-
=
yyyf
m
является нигде не оп-
ределенной, так как для любого натурального числа
m
в области нату-
ральных чисел
3
0
-
-
m
не определено. Значит с помощью
m
-оператора
получена нигде не определенная функция.
Пример 11. Функция
y
x
-
не является всюду определенной (на-
пример,
m
-
0
не определено), но функция ]0[)(
3
=
-
=
yxyxf
m
, получен-
ная из нее с помощью
m
-оператора, всюду определенная, причем для лю-
бого
m
: mmf
=
)(
3
(все разности
0
-
m
,
1
-
m
, …,
)
1
(
-
-
m
m
определены
и отличны от нуля, а
0
=
-
m
m
). Таким образом, с помощью
m
-оператора
получена всюду определенная функция.
Пример 12. Константная функция 5),(
1
=
yxg всюду определена, а
функция ]0),([)(
14
=
=
yxgyxf
m
нигде не определена.
Определение. Функция называется частично рекурсивной, если она
может быть получена из исходных с помощью применения конечного чис-
ла раз подстановок, примитивных рекурсий и
m
-оператора. Всюду опреде-
ленная частично рекурсивная функция называется общерекурсивной.