Алгоритмическая машина Тьюринга

1.

Алгоритмическая машина
Тьюринга

2.

Математическое понятие машина
Тьюринга
Английский математик Алан Тьюринг провел уточнение понятия
алгоритма с помощью абстрактной математической машины.
Основные свойства машины Тьюринга, отличающие её от
исполнителя – человека, заключаются в следующим:
– машина Тьюринг не может ошибаться, т.е. она строго без всяких
отклонений выполняет программу, определяющую ее работу;
– машина Тьюринг имеет потенциально бесконечную память.

3.

Машину Тьюринга на неформальном уровне
можно представить следующим образом:
… … … … aj1 aj2 … … … … ajk … … … … ajr … … … …
Q

4.

Программа имеет вид:
a0
a1
……
aj
q1
q2
…
qi
…
qn
ajRqi
……
ap
……

5.

Машина Тьюринг

6.

Понятие конфигураций машины Тьюринга

7.

Операции над машинами Тьюринга
1.операция композиции;
2.операция ветвления;
3.операция зацикливания.

8.

Операция композиции

9.

КОМПОЗИЦИЯ

10.

Основные свойства операции композиция
10. Операция композиции не обладает свойством
коммутативности, т.е.
М1 М2 М2 М1
20.
Она обладает свойством ассоциативности.
М1( М2 М3)= (М1 М2) М3
30. Операция композиции обладает свойством
повторения (итерационное свойство).
М М … М=Мn, если M1=M2=…= Mn=M.

11.

Операция ветвления

12.

ВЕТВЛЕНИЕ

13.

Операция зацикливания

14.

ВЫЧИСЛИМОСТИ ФУНКЦИИ ПО ТЬЮРИНГУ

15.

Некоторые обозначения

16.

Разновидности конфигурации

17.

Элементарные машины Тьюринга

18.

Элементарные машины Тьюринга

19.

Элементарные машины Тьюринга

20.

Элементарные машины Тьюринга

21.

Элементарные машины Тьюринга

22.

Элементарные машины Тьюринга

23.

Элементарные машины Тьюринга

24.

Элементарные машины Тьюринга

25.

Элементарные машины Тьюринга

26.

Элементарные машины Тьюринга

27.

Элементарные машины Тьюринга

28.

Элементарные машины Тьюринга

29.

Элементарные машины Тьюринга

30.

Примеры вычислимых функций по Тьюрингу

31.

32.

33.

34.

Программа для функция