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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

20
Например, функциями выбора аргументов являются:
221
)2(
2
),( xxxI = ,
11
)1(
1
)( xxI = , .),,(
3321
)3(
1
xxxxI =
Для построения более сложных функций используют различные операции.
Важнейшие из них – это операции суперпозиции и примитивной рекурсии.
Эти операции рассмотрим в разделе 3.
При вычислении числовых функций на машинах Тьюринга часто
пользуются специальным кодированием чисел. Например, натуральное
число
m
будем задавать набором из
1
+
m
единиц, который будем обозна-
чать через
1
1
+
m
. Итак, 0 будем задавать 1, 1 – 11, 2 – 111 и т. д.
Числовая функция ),...,(
1 n
xxf называется вычислимой по Тьюрингу,
если существует машина Тьюринга
f
T , удовлетворяющая следующим
двум условиям:
1) для любого набора
n
n
NDfmm ÌÎ) ..., ,(
1
и такого, что mmmf
n
=
),...,(
1
,
машина Тьюринга применима к слову
1
11
1
1
1
21
+
++
L
L
L
n
m
mm
, (2)
и в заключительной конфигурации на некотором участке ленты будет за-
писано слово
1
1
+
m
, а остальные участки ленты, если такие будут, окажутся
пустыми.
2) если Dfmm
n
Ï
),...,(
1
машина Тьюринга
f
T не применима к слову (2).
Если функция
f
вычислима по Тьюрингу с помощью машины Т
f
, то
будем говорить, что машина Т
f
вычисляет функцию
f
.
§ 2. Примеры функций, вычислимых по Тьюрингу
Пример 5. Построить машину Тьюринга
3
T с внешним алфавитом
}
1
,
{
L
, которая вычисляет функцию
.
1
)
(
+
=
x
x
f
Например, функциями выбора аргументов являются:

               I 2( 2) ( x1 , x2 ) � x2 , I1(1) ( x1 ) � x1 , I1(3) ( x1 , x2 , x3 ) � x3 .

Для построения более сложных функций используют различные операции.
Важнейшие из них – это операции суперпозиции и примитивной рекурсии.
Эти операции рассмотрим в разделе 3.
      При вычислении числовых функций на машинах Тьюринга часто
пользуются специальным кодированием чисел. Например, натуральное
число m будем задавать набором из m � 1 единиц, который будем обозна-
чать через 1m�1 . Итак, 0 будем задавать 1, 1 – 11, 2 – 111 и т. д.
      Числовая функция f ( x1 ,..., xn ) называется вычислимой по Тьюрингу,
если существует машина Тьюринга T f , удовлетворяющая следующим

двум условиям:
1) для любого набора (m1 , ..., mn ) � Df � N n и такого, что f (m1 ,..., mn ) � m ,
машина Тьюринга применима к слову

                                1m1 �1 � 1m2 �1 �...� 1mn �1 ,                                (2)

и в заключительной конфигурации на некотором участке ленты будет за-
писано слово 1m�1 , а остальные участки ленты, если такие будут, окажутся
пустыми.
2) если (m1 ,..., mn ) � Df машина Тьюринга T f не применима к слову (2).

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


               § 2. Примеры функций, вычислимых по Тьюрингу


      Пример 5. Построить машину Тьюринга T3 с внешним алфавитом
{�,1} , которая вычисляет функцию f ( x) � x � 1.
                                                   20

Страницы