Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 81 стр.

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
127
Λ
1 1 1 1 1
Λ
1
q
Программа МТ выглядит следующим образом:
,qНq
,qПq
01
11
1
11
→Λ
согласно которой для любой начальной конфигурации, когда считывающая
головка обозревает одну из единиц, в каждый момент эта единица остается
на месте, и головка сдвигается вправо на одну ячейку . Этот процесс
продолжается до тех пор, пока головка не выйдет на пустую ячейку . Тогда
в пустую ячейку записывается единица , головка остается на месте. Маши-
на перейдет в состояние
0
q .
Можно показать, что все арифметические функции натурального ар-
гумента вычислимы по Тьюрингу . Например, работа МТ в алфавите
{
}
1,
Λ
при вычислении числовой функции
(
)
yxy,xf
+
=
можно описать сле-
дующей программой
1
q
2
q
3
q
4
q
Λ
2
1 qП
3
qЛ
Λ
1
1
1 qП
2
1 qП
4
qЛ
Λ
0
q
Л
где любое натуральное число
m
кодируется набором из
1
+
m
единиц; этот
набор обозначается через
1
1
+m
. Так ,
43
1111131111211110 == ~,~,~,~ и
т . д .
Числовая функция
(
)
n
x...,,x,xf
21
называется вычислимой по Тью -
рингу , если существует МТ такая, что для любых
n
m...,,m,m
21
если при
nn
mx...,,mx,mx
=
=
=
2211
имеем
(
)
mm...,,m,mf
n
=
21
, эта машина при -
менима к слову
111
121
1
1
1
+++ mmm
&...&& (**)
и в заключительной конфигурации на некотором участке ленты будет за -
писано слово
1
1
+m
, а остальные ячейки окажутся пустыми. Если значение
функции
(
)
n
m...,,m,mf
21
не определено, эта МТ не применима к слову
(**).