11. Методы задания машин Тьюринга.

Через Таблицу. Через Список команд. (правила ты знаешь).

12. Граф-схемы и их связь диаграммой состояний автоматов.

Поскольку таблица состояний и граф (диаграмма) состояний несут одну и ту же информацию, их можно преобразовать друг в друга. Каждое состояние представляется кружком, а каждый элемент таблицы преобразуется в отрезок ориентированной линии, соединяющей соответствующие кружки. Процедура обратного преобразования очевидна.

Рассмотрим графический способ задач МТ, для этого рассмотрим следующие правила:

aq₀ → bq₁L q₂-конечное состояние

bq₀ → aq₂L

a q₁ → bq₂L

bq₁ → aq₂L

13. Рекурсивные функции и их построение из простейших.

Как уже было сказано, наряду с определением алгоритма через машину Тьюринга, разрабатывался подход к определению вычислимости через построение функций из простейших (первичных) функций. Этот подход реализовывался С.Клини, А. Черчем и К.Геделем. Понятие рекурсивной функции введено из следующих соображений. Некоторые функции объявляются первичными. Первичную функцию нельзя заменить вычислением более простых функций. Из этих первичных функций строится с помощью определенных операций все множество известных нам вычислимых функций. Таких первичных функций над целыми положительными числами всего три.

А). Функция константа

Б) Функция непосредственного следования

В) Тождественная функция

14. Операторы подстановки, рекурсии и минимизации. Частично рекурсивные функции.

Для построения более сложных функций из первичных используют следующие операции.

• Операция подстановки. Эта операция заключается в том, что вместо каких-то переменных функции подставляют другие функции от тех же или иных переменных.

Пример. Пусть и . Тогда подставив вместо переменной х функцию g(у), получим новую функцию:

• Операция примитивной рекурсии. Эту операцию можно представить следующим образом

Пример 1. Пусть - известная вычислимая функция, т.е. известен алгоритм вычисления этой функции для произвольного х. Определим новую функцию f(x) следующим образом:

Это и есть определение функции с помощью операции примитивной рекурсии.

Например, пусть

Это есть определение целочисленного умножения. Так

f(3,3)=f(3,2)+3=f(3,1)+3+3=3+3+3=9.

Пример 2. и

Это определение позволяет находить значение . В самом деле, рассмотрим следующий пример вычисления 3² .

f(3,1+1)=h(3,f(3,1))=h(3,3)=h(2+1,3)=h(2,3)+3=h(1+1,3)+3=h(1,3)+3+3=3+3+3=9

Определение. Функция, определяемая из простейших с помощью операций подстановки и/или примитивной рекурсии, называется примитивно рекурсивной.

Имеется еще одна операция для построения рекурсивных функций. Правда, эта операция не всегда дает результат или, как говорят, не является полностью определенной (тотальной). Эта операция называется операцией минимизации (взятия минимального корня). Ее определение таково.

• 

Эту операции можно для простоты обозначить как _y f(x,y).

Пример 3. Пусть . Тогда _y f(3,y)=2.

Определение. Функция, определяемая из простейших с помощью операций подстановки примитивной рекурсии и минимизации, называется частично рекурсивной.