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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

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 . 
        3. Построить машину Тьюринга, которая вычисляет функцию:

1) f ( x, y ) � x � y ;   2) f ( x) � x ;
                                       2



3) функцию выбора аргумента J 2( 3) � ( x1 , x 2 , x3 ) � x2 .

        4*. Реализовать на МТ алгоритм вычисления функции f (n) � n � 2 ,
где n � N .

Указание: Взять множество состояний Q = { q0 , q1 , q2 }. Число n на ленте
МТ записывается в десятичной системе счисления. Состояние q1 заменяет
последнюю цифру числа n, если эта цифра меньше 8, цифрой, на две еди-
ницы большей, и переходит в стоп-состояние. Если последняя цифра числа
n равна 8, то ее заменить на 0 и перейти влево в состояние q2 . Состояние
q2 добавляет к следующему разряду 1. Если же последняя цифра числа n
равна 9, то ее заменить на 1 и перейти влево в состояние q2 .




                                            24

Страницы