Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 28 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

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
)
,
,
(
+
=
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
        Иногда операцию примитивной рекурсии обозначают f � R ( g , h) .
Заметим, что операция примитивной рекурсии фактически строит таблицу
значений новой функции f.
        Определение. Функция называется примитивно-рекурсивной, если
она может быть получена из исходных функций (3) с помощью конечного
числа подстановок и примитивных рекурсий.
        Определение. Функция называется примитивно-рекурсивной, если
она может быть записана с помощью элементарных рекурсивных функ-
ций с использованием конечного числа операций суперпозиции и примитив-
ной рекурсии.
        Определение. Функция называется частичной, если она определена
не для всех значений аргументов.
        Пример 7. Доказать, что функция f ( x, y ) � x � y является прими-
тивно-рекурсивной.
        Решение. Так как заданная функция является функцией двух аргу-
ментов, то для использования операции примитивной рекурсии мы долж-
ны иметь функцию g , зависящую от одного аргумента, и функцию h , за-
висящую от трех аргументов. Определим эти функции.
        В функции f ( x, y ) � x � y положим y � 0 . Тогда имеем f ( x,0) � x –
это тоже тождественная функция. Полагая y � 1 , получим f ( x,1) � x � 1 –
это функция следования.
        Таким образом, выбираем следующие элементарные функции: тож-
дественную g ( x) � x и функцию следования h( x, y, z ) � z � 1 . Заметим, что

здесь h( x, y , z ) � I 33 ( x, y, s ( x)) .
        Используя схему примитивной рекурсии:
         f ( x,0) � g ( x) � x,
         f ( x,1) � h( x,0, f ( x,0)) � f ( x,0) � 1 � x � 1,

                                                 28

Страницы