• 20-30 годы XX века
• Алан Тьюринг, Эмиль Леон Пост, Андрей Андреевич Марков, Андрей Николаевич Колмогоров, Алонзо Чёрч
• Теория алгоритмов
• Теория исчислимости
• Различные строгие определения алгоритма

• \(\mathcal A\) – алфавит, т.е. набор символов \(a \in \mathcal A\)
• слова \(\mathcal A^*\) – последовательности 0 или больше символов \(a\in \mathcal A\)
• Входные и выходные данные МТ – подмножество всех слов \(\mathcal A^*\)
• Допустимые входные слова \(\mathcal I \subset \mathcal A^*\) – область применимости алгоритма

Описание машины Тьюринга

• Бесконечная лента, разделённая на ячейки
• Управляющее устройство (автомат, головка записи-чтения)
• Содержимое ячеек – символы алфавита \(\mathcal A\)
• Выделяется особый символ \(a_0 \in \mathcal A\), также обозначаемый \(\Lambda\), означающий “пустую” ячейку
• Автомат имеет внутреннее состояние
• Число состояний автомата конечно и известно заранее
• Автомат может перемещаться влево и вправо по ленте
• Автомат может читать и записывать содержимое ячеек

• Алгоритм – правила перехода автомата
• Правило перехода включает запись нового символа и возможно смещение влево или вправо
• Некоторые состояния – называемые терминальными – означают конец работы

• Алгоритм удобно представлять в виде таблицы
• Столбцы – текущий символ на ленте
• Строки – текущее состояние автомата
• Ячейки – команда, выполняемая на данном шаге работы

Структура команды:

\[ a_k \left\lbrace \begin{matrix} Л \\ Н \\ П \end{matrix}\right\rbrace q_m \]

Условные обозначения:

• В начале работы автомат находится в состоянии \(q_1\)
• При переходе в состояние \(q_0\) работа завершается

Пример

• Увеличение десятичного числа на 1
• В начальном состоянии автомат находится слева от входного слова

• Алфавит: \(\mathcal A= \{0,1,2,3,4,5,6,7,8,9,Λ\}\)
• Состояния автомата: \(\mathcal Q = \{q_0, q_1, q_2, q_3\}\) (по одному на шаг алгоритма плюс состояние останова)
• Пусть, \(q_1\) – поиск начала входного слова, \(q_2\) – поиск конца входного слова, \(q_3\) – прибавление 1.

Формальное описание

Машина Тюринга (МТ)

это система вида \(\{A, a_0, Q, q_1, q_0, T, \tau\}\), где

• \(A\) – конечное множество символов алфавита МТ
• \(a_0 \in A\) – пустой символ алфавита
• \(Q\) – конечное множество состояний МТ
• \(q_1 \in Q\) – начальное состояние МТ
• \(q_0 \in Q\) – конечное состояние МТ (состояние останова)
• \(T = \{Л, П, Н\}\) – множество сдвигов МТ
• \(\tau\) – программа МТ, то есть функция, задающая отображение \(\tau: A\times Q\backslash \{q_0\} \rightarrow A\times T \times Q\)

Тезис Тьюринга

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

иначе, для любого алгоритма существует эквивалентная ему машина Тьюринга.

Отличия от МТ:

• Двоичный алфавит
• Вместо состояния автомата – номер строки “программы”

Команды МП:

1. Записать 1, перейти к i-той строке программы
2. Записать 0, перейти к i-той строке программы
3. Выполнить сдвиг влево, перейти к i-той строке программы
4. Выполнить сдвиг вправо, перейти к i-той строке программы
5. Условный переход: если в наблюдаемой ячейке 0, перейти к i-той строке программы, иначе – перейти к j-той строке программы.
6. Останов.

Запрещённые команды:

1. Запись в ячейку 1, когда там уже 1.
2. Запись в ячейку 0, когда там уже 0.

Обозначения:

1. ∨ i – записать 1, перейти к i-той строке программы
2. × i – записать 0, перейти к i-той строке программы
3. ← i – выполнить сдвиг влево, перейти к i-той строке программы
4. → i – выполнить сдвиг вправо, перейти к i-той строке программы
5. ? i; j – условный переход: если в наблюдаемой ячейке 0, перейти к i-той строке программы, иначе – перейти к j-той строке программы.
6. ! – останов.

Пример программы:

1. → 2
2. ? 1; 3
3. × 4
4. ← 5
5. !

• МП – императивная модель вычисления
• Эквивалентна МТ
• Следствие – любой алгоритм над произвольным алфавитом сводится к алгоритму над двоичным алфавитом

Тезис Поста

всякий алгоритм представим в виде машины Поста.

Нормальный алгоритм Маркова

Андрей Андреевич Марков (1903-1979)

Определение включает:

1. Алфавит \(\mathcal A\)
2. Схема \(\mathcal S\)

• Простая формула подстановки \(L\to D\)
• Заключительная формула подстановки \(L\to\cdot D\)
• \(L\in \mathcal A^*\), \(D\in \mathcal A^*\)
• \(\to \notin \mathcal A\), \(\to\cdot \notin \mathcal A\)

Применение к слову \(V\):

1. \(V\) – слово в начале текущего шага
2. Если \(\nexists (L\to D)\in \mathcal S: L \subset V\), завершить работу
3. Иначе, выбрать первую из \((L\to D)\in \mathcal S: L\subset V\)
4. \(V = R\mathbin\Vert L\mathbin\Vert S\), так, что \(|R| = \min\); Выполняется подстановка \(V=R\mathbin\Vert D\mathbin\Vert S\).
5. Если формула – конечная, алгоритм завершён. Иначе, переход к пункту 1.

• Любой НАМ эквивалентен МТ и наоборот
• Аналог тезиса Тьюринга для НАМ – принцип нормализации

Пример

• Преобразование двоичных чисел в “единичные”
• 101₂ ~ |||||

Алфавит:

{ 0, 1, | }

Правила:

1. 1 → 0|
2. |0 → 0||
3. 0 → (пустая строка)

Рекурсивные функции

Курт Гёдель (1906-1978)

Алонзо Чёрч (1903-1995)

• примитивно рекурсивные функции
• общерекурсивные функции
• частично рекурсивные функции

Примитивно рекурсивные функции

• Базовые функции
• Все функции, получаемые из базовых подстановкой и примитивной рекурсией

Базовые функции:

• \(O()=0\) – нулевая функция
• \(S(x)=x+1\) – функция следования
• Функции \(I_n^m(x_1,\ldots,x_n) = x_m\), где \(0<m\leq n\) – функции проекции

Операторы:

• Подстановка \(S\). \(S(f,g_1,\ldots,g_m)=h\), \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\)
• Примитивная рекурсия. \(h=R(f,g):\)
  • \(h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n)\)
  • \(h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y))\)

Частично рекурсивные функции

Оператор минимизации аргумента

\(\mu(f) = h:\) \(h(x_1,\ldots,x_{n-1}) = \min y,\) такой, что \(f(x_1,\ldots,x_{n-1},y)=0.\)

Общерекурсивные функции

Общерекурсивные функции

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

• Определение принадлежности классу общерекурсивных функций – в общем случае алгоритмически неразрешимо

Функция Акермана

Вильге́льм Фри́дрих Аккерман (1896-1962)

Функция, являющаяся общерекурсивной, но не являющаяся примитивно-рекурсивной

\[ \begin{array}{lcl} \operatorname{A}(0, n) & = & n + 1 \\ \operatorname{A}(m+1, 0) & = & \operatorname{A}(m, 1) \\ \operatorname{A}(m+1, n+1) & = & \operatorname{A}(m, \operatorname{A}(m+1, n)) \end{array} \]

Проблема останова

По описанию алгоритма A и входным данным \(x\) необходимо выяснить, остановится ли алгоритм \(A\) на входных данных \(x\).

• Является алгоритмически неразрешимой

• Пусть существует универсальный алгоритм \(A\), решающий проблему останова.
• Рассмотрим класс алгоритмов \(\mathcal T\), обрабатывающий тексты описания алгоритмов.

• Т.к. существует \(A\), существует алгоритм \(B\), определяющий, остановится \(T\in \mathcal T\) на собственном тексте или нет.

• Построим алгоритм \(C\). Вход: текст алгоритма \(T\in\mathcal T\)

  1. Выполнить алгоритм \(B\) над \(T\).
  2. Если алгоритм \(B\) определил, что \(T\) остановится на своём тексте, перейти к шагу 1. Иначе – к шагу 3.
  3. Конец алгоритма

• Применим \(C\) к тексту \(C\)

• Если \(C\) остановится на собственном тексте, то он не может остановиться, и наоборот.

• Следовательно, не существует алгоритма \(А\). \(\blacksquare\)

Проблема распознавания выводимости

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

Существует ли для любых двух слов \(R\) и \(S\) дедуктивная цепочка, ведущая от \(R\) к \(S\) в рамках данного логического исчисления?

Теорема Чёрча

Проблема распознавания выводимости алгоритмически неразрешима.

Вычислимая функция

функция, для вычисления которой можно составить алгоритм.

Пример невычислимой функции

\[ n \in \mathbb N\\ h(n) = \begin{cases} 1, & \text{если в }\pi\text{ есть последовательность из ровно }n\text{ 9-к} \\ 0, & \text{в противном случае} \end{cases} \]