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

UptoLike

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

72
Решение. Пусть внешним алфавитом данной МТ является множест-
во
{
}
1,A
L
=
. Число
N
x
Î
на ленте машины записывать в виде набора из
x
единиц:
¯
L
1 1 1 1 1
L
1
q
Программа МТ выглядит следующим образом:
,qНq
,qПq
01
11
1
11
®L
согласно которой для любой начальной конфигурации, когда считывающая
головка обозревает одну из единиц, в каждый момент эта единица остается
на месте, и головка сдвигается вправо на одну ячейку. Этот процесс про-
должается до тех пор, пока головка не выйдет на пустую ячейку. Тогда в
пустую ячейку записывается единица, головка остается на месте. Машина
перейдет в состояние
0
q .
Можно показать, что все арифметические функции натурального ар-
гумента вычислимы по Тьюрингу. Например, работа МТ в алфавите
{
}
1,
L
при вычислении числовой функции
(
)
yxy,xf
+
=
можно описать сле-
дующей программой
1
q
2
q
3
q
4
q
L
2
1 qП
3
qЛ
L
1
1
1 qП
2
1 qП
4
qЛ
L
0
qЛ
L
Любое натуральное число
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
&...&& , (2)
и в заключительной конфигурации на некотором участке ленты будет за-
писано слово
1
1
+m
, а остальные ячейки окажутся пустыми. Если значение
функции
(
)
n
m...,,m,mf
21
не определено, эта МТ не применима к слову
(2).