С помощью диаграммы

Диаграмма представляет собой геометрический объект (ориентированный граф), состоящий из вершин и дуг. Каждой вершине приписывается состояние машины Тьюринга: таким образом, вершин в диаграмме ровно столько, сколько имеется состояний. Дуге, соединяющей две вершины q_i и q_j, приписывается некоторый символ a алфавита A и двойка b D так, что запись a q_i b q_j D образует команду программы машины Тьюринга.

Композиция машин Тьюринга

1. Последовательное соединение машин.

Для организации такой работы достаточно построить объединенную таблицу машины Тьюринга, приписав к первой таблице вторую (справа) и заполнив пустые клетки первой таблицы командой перехода к начальному состоянию второй программы.

f(x)=(x+1)*2

Итерация (повторение) машин Тьюринга

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

f(X)=X+L eeeeX*Leeeee

3) Формализация понятия алгоритма: нормальные алгорифмы Маркова, определение и выполнение. Примеры.

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

Отличие алгорифмов Маркова в том, что каждый шаг преобразования позволяет выполнить замену не одного символа, а целого слова в исходной цепочке.

Если применив алгоритм к строке , мы, за конечное число шагов, получили результат , то такой алгоритм будем называть применимым и обозначать

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

Расширим алфавит тремя символами «», «». «|». Предполагается, что в алфавит эти символы не входят. В расширенном алфавите можно записывать разные слова, но особенное внимание уделим сломам вида: , где - один из двух символов: стрелка или стрелка с точкой, - любая цепочка символов в алфавите .

Если такое правило срабатывает, то в исходной строке отыскивается подстрока и она целиком заменяется на .

Для определения алгоритма нужно задать не одно правило, не одну формулу подстановки, а множество, причем необходимо определить порядок их применения. Для этого вводится еще одно понятие схемы алгоритма. Схемой – называется слово в расширенном алфавите, имеющее вид , где - формулы подстановок. Чем меньше номер, тем выше приоритет. Это значит, что если в цепочке символов, которая преобразуется с помощью алгоритма, встречается несколько подстрок, то применяться будет формула, имеющая минимальный номер.

Если в строке, которая преобразуется алгорифмом встречается левая часть какой-то формулы , то это означает, что формула - действует на эту строку. В общем случае в схеме может быть несколько формул, которые действуют на строку, но выбираться будет с большим приоритетом.

Если какая-то подстановка действует на исходную строку, причем левая часть встречается в строчке многократно, то формула подстановки применяется один раз. Причем применяется к самому левому вхождению.

При заменах могут использоваться пустые строки

Если в схеме используется несколько правил, в которых правые части совпадают, а левые части являются подстроками, которые можно объединить в какое-то множество, то пишут

, где - все элементы от А до Я

Пустая строка может встречаться и в левой части. Если есть такие правила, то пустота замениться слева. В этом случае при составлении схемы, нужно думать о том, чтобы алгоритм был применим.

Каким образом алгоритм завершает работу?

Есть несколько вариантов:

1. Не применима ни одна подстановка в схеме (не действует на полученную строку)

2. Выбирается формула подстановки вида: . Такая формула подстановки называется заключительной. После ее применения алгоритм завершает работу. Если в левой части этой формулы используется пустая стока, то эта формула подстановки не должна иметь высокий приоритет и обязательно должна присутствовать заключительная формула с большим приоритетом.

4) Вычислимые функции. Базовый набор функций и операции над функциями: суперпозиция, примитивная рекурсия, минимизация. Классы вычислимых функций. Примеры.

При разработке алгоритма (программы) встает несколько вопросов:

1) Является ли задача алгоритмические вычислимой, т.е можно ли построить алгоритм для ее решения.

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

2) Если функция вычислима, как построить алгоритм?

Попробуем построить алгоритм:

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

Предположим, что все функции преобразуют целые числа в целые числа.

- функция обнуления

- функция суммы

- функция выбора. Выбирает из набора аргументов аргумент с номером

Обозначим этот базовый набор за

2. В базовом наборе функций определим основные операции. Операции получают функции (а не значения функций) в качестве операндов и дают в результате новые функции. Эти операции также должны быть очевидны с математической точки зрения – не должно возникать сомнения в том, что из вычислимых функций с помощью операций получаются вновь вычислимые функции. Последовательно применяя операции из к множеству функций из мы будем получать новые функции, которые будут расширять набор . Следовательно, мы сможем построить бесконечный набор функций.

Обозначим набор этих операций . в систему операций входят три операции: суперпозиция , примитивная рекурсия и минимизация .