Математическая логика и теория алгоритмов. Сергиевская И.М. - 50 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

55
Поскольку команда вида Dqq
i
α
0
2
в программе отсутствует, то последняя
конфигурация является заключительной. Следовательно, машина
T
к слову
P
применима, и 1)( =
P
T
. (Нули слева и справа от слова не записываются).
б) Получаем конфигурации:
1)
6
1
1q .
6)
1
2
q
.
2)
5
2
1q .
7)
0
1
q .
3)
4
1
1q .
8) 0
1
q .
4)
3
2
1q .
9)
0
1
q
.
5)
2
1
1q .
. . . . . .
Процесс продолжается неограниченно, головка смещается по ленте вправо до
бесконечности, следовательно, машина
T
к слову
6
1
=
P
неприменима.
Вид конфигурации 8) обусловлен тем, что символ 0 (пустой символ)
находится справа от последней единицы слова по умолчанию.
Машины Тьюринга
1
T и
2
T называются эквивалентными, если:
•
1
T и
2
T либо обе применимы, либо обе неприменимы к каждому исходному слову
P
;
•
если обе машины применимы к слову
P
, то
=
)(
1
PT )(
2
PT .
Программу для машины Тьюринга можно задать не только с помощью
последовательности команд, но и в виде таблицы. Так, в последнем примере
программа может быть задана в виде:
1
q
2
q
0
Rq 0
1
-
1
Rq 0
2
Rq 0
1
При табличной записи командой иногда называют выражение
ijijij
Daq .
Имеет место следующий тезис.
Тезис Тьюринга. Всякий алгоритм может быть реализован соответствующей
машиной Тьюринга.
Тезис является недоказуемым, так как он связывает нестрогое понятие
алгоритма и строгое понятие машины Тьюринга.
Тезис может быть опровергнут построением примера алгоритма, который не
может быть реализован машиной Тьюринга.
В
Содержание. 
     Поскольку команда вида q 2 0qiαD в программе отсутствует, то последняя
конфигурация является заключительной. Следовательно, машина T к слову P
применима, и T ( P ) = 1 . (Нули слева и справа от слова не записываются).

     б) Получаем конфигурации:
 1) q116 .              6) q21 .
 2) q215 .              7) q1 0 .
 3) q114 .              8) q1 0 .
 4) q213 .                9) q1 0 .
  5) q112 .               . . . . . .
      Процесс продолжается неограниченно, головка смещается по ленте вправо до
бесконечности, следовательно, машина T к слову P = 16 неприменима.
      Вид конфигурации 8) обусловлен тем, что символ 0 (пустой символ)
находится справа от последней единицы слова по умолчанию.

     Машины Тьюринга T1 и T2 называются эквивалентными, если:
• T1 и T2 либо обе применимы, либо обе неприменимы к каждому исходному слову
  P;
• если обе машины применимы к слову P , то T1 ( P) = T2 ( P) .

     Программу для машины Тьюринга можно задать не только с помощью
последовательности команд, но и в виде таблицы. Так, в последнем примере
программа может быть задана в виде:

                                        q1          q2
                           0          q1 0 R          -
                           1          q2 0 R       q1 0 R

     При табличной записи командой иногда называют выражение qij aij Dij .
     Имеет место следующий тезис.

    Тезис Тьюринга. Всякий алгоритм может быть реализован соответствующей
машиной Тьюринга.

     Тезис является недоказуемым, так как он связывает нестрогое понятие
алгоритма и строгое понятие машины Тьюринга.
     Тезис может быть опровергнут построением примера алгоритма, который не
может быть реализован машиной Тьюринга.

В Содержание.



                                        55

Страницы