ВУЗ:
Составители:
Рис. 2.2.
На рис. 2.3,а,б показаны диаграммы еще двух элементарных МТ R и L,
выполняющих соответственно действия ∼АВ∼⇒∼
↑
ВА ∼ и
↑
ВВА ⇒∼ АВВ
↑
∼.
Рис. 2.3.
Изображение диаграмм можно упростить следующим образом.
Заменим все стрелки для всех
nj ...,1,0
=
одной стрелкой без букв. Если среди
всевозможных стрелок для всех
nj ...,1,0
=
отсутствует лишь некоторая,
взвешенная буквой x
j
, то заменяем все стрелки одной, указав над ней
j
x
≠
.
Опустим точку, если она соединена всеми стрелками только с одним
символом. Опустим ненадписанные стрелки между двумя символами и будем
писать М
А
вместо
4434421
разn
МММ
−
−− ... . Тогда первая из приведенных выше
диаграмм примет вид r
3
х
6
, вторая , а третья .
Из приведенного способа построения ДТ следует, что переход от
таблицы Тьюринга к ДТ осуществляется однозначно. Легко показать, что и
обратный переход однозначен. Для этого необходимо выполнить следующее.
Заменить символ каждой элементарной машины соответствующей ей
таблицей. Определенным образом ввести переобозначение состояний в
командах всех элементарных машин. Ввести сквозную
нумерацию в
полученной общей таблице.
2.4. Машины Тьюринга и вычислимые функции
•
•
•
х
n
х
0
•
•
•
х
n
х
0
r
•
•
•
х
n
r
•
•
•
х
n
r
х
0
х
0
х
0
•
•
•
х
n
х
0
r
х
0
M
х
n
а)
•
•
•
х
n
х
0
l
х
0
M
х
n
б)
r
l
Страницы
- « первая
- ‹ предыдущая
- …
- 31
- 32
- 33
- 34
- 35
- …
- следующая ›
- последняя »
