Математическая логика и теория алгоритмов. Анкудинов Г.И - 73 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

• машина M по слову x *x *x выдает x ;
3 1 2 3 3
по слову x *x *x выдает h(x , x
• машина M
).
4 1 2 3 2 3
M
3
∨ (M
1
* M
2
* M
4
)
X
σ=и
σ=л
x
3
A
x*0*a=x
1
*x
2
*x
3
B
*M
0
σ*x
1
*x
2
*x
3
x
1
¬1*x
2
+1*h(x
2
,x
3
)
Рис. 4.7.
Программирование операции минимизации. Рассмотрим эту
операцию на упрощенном примере:
f(x)= μ
y
(h(x, y)=0).
Операция минимизации реализуется на машине Тьюринга
циклической программой на рис. 4.8.
На этом рисунке
• машина A перерабатывает слово x в слово x*0;
• машина B получает слово x
1
*x
2
*x
3
и выдает σ=и, если x
1
=0, и
σ=л в противном случае;
• машина M
0
оставляет входное слово без изменения;
• машина M
1
по слову x
1
*x
2
вычисляет h(x
1
,x
2
);
• машина M
2
преобразует слово x
1
*x
2
*x
3
в слово x
2
*x
3
;
• машина M
3
по слову x
1
*i выдает i;
• машина M
4
преобразует слово x
1
*i в слово x
1
*i+1.
Рис. 4.8.
M
3
∨M
4
X
σ=и
i
σ=л
A
x*0=x*i
h(x,i)*x*i
σ*x*i
B
*M
2
M
M
*
1
0
x*i+1
157

Страницы