ВУЗ:
Составители:
Рубрика:
Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
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
не определено, эта МТ не применима к слову
(**).
127
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
↓
Λ 1 1 1 … 1 1 Λ
q1
Программа МТ выглядит следующим образом:
q1 1 → 1 П q1 ,
q1 Λ → 1 Н q0 ,
согласно которой для любой начальной конфигурации, когда считывающая
головка обозревает одну из единиц, в каждый момент эта единица остается
на месте, и головка сдвигается вправо на одну ячейку. Этот процесс
продолжается до тех пор, пока головка не выйдет на пустую ячейку. Тогда
в пустую ячейку записывается единица, головка остается на месте. Маши-
на перейдет в состояние q0 .
Можно показать, что все арифметические функции натурального ар-
гумента вычислимы по Тьюрингу. Например, работа МТ в алфавите {Λ , 1}
при вычислении числовой функции f ( x , y ) =x + y можно описать сле-
дующей программой
q1 q2 q3 q4
Λ 1 П q2 Λ Л q3
1 1 П q1 1 П q2 Λ Л q4 Λ Л q0
где любое натуральное число m кодируется набором из m +1 единиц; этот
набор обозначается через 1m +1 . Так , 0 ~ 1, 1 ~ 11, 2 ~ 111 =13 , 3 ~ 1111 =14 и
т.д.
Числовая функция f ( x1 , x 2 , ..., x n ) называется вычислимой по Тью-
рингу, если существует МТ такая, что для любых m1 , m 2 , ..., m n если при
x1 =m1 , x 2 =m2 , ..., x n =mn имеем f (m1 , m 2 , ..., mn ) =m , эта машина при-
менима к слову
1m1 +1 & 1m2 +1 & ... & 1m1 +1 (**)
и в заключительной конфигурации на некотором участке ленты будет за-
писано слово 1m +1 , а остальные ячейки окажутся пустыми. Если значение
функции f (m1 , m 2 , ..., m n ) не определено, эта МТ не применима к слову
(**).
