Частично-рекурсивные функции. Тезис Черча. Регулярные выражения. Лекция 4

1.

Лекция 4
Частично-рекурсивные функции. Тезис Черча. Регулярные выражения

2.

Функциональная парадигма
•Не используется оператор присваивания для изменения состояний
•Не используются циклы
•Выполнение последовательности команд не имеет смысла, т.к. одна команда не
влияет на выполнение следующей
•Функции можно передавать в другие функции в качестве аргументов и
возвращать в качестве результата, результатом вычислений тоже может быть
функция
•Вместо циклов используется рекурсия

3.

Машины Тьюринга
• Из бесконечной в две стороны ленты, в ячейках которой могут быть записаны
символы алфавита А.
• Головки, которая может двигаться вдоль ленты, обозревая в каждый момент
времени одну из ячеек.
• Оперативной памяти, которая имеет конечный размер.
• Таблицы переходов, которая задает функцию:
Поскольку таблица переходов - это функция на конечном множестве, ее
возможно задать таблицей, где каждая строка это пять значений: a, q, a’, q’, d.

4.

Машины Тьюринга. Пример.
Если головка находиться над ячейкой, содержащей символ a, а состояние
равно q, то на очередном такте работы записывается в текущую ячейку
символ a’, изменяет на состояние q’ и сдвигает ячейку на d ячеек.

5.

Частично рекурсивные функции
Класс частично рекурсивных функций — одно из главных понятий теории
алгоритмов. Это объясняется тем, что какие бы классы точно очерченных
«алгоритмов» до сих пор не рассматривались, во всех случаях оказывалось, что
соответствующие числовые функции, вычислимые посредством алгоритмов этих
классов, были частично рекурсивными.
Класс алгоритмически вычислимых функций совпадает с классом всех частично
рекурсивных функций. Принятие данного тезиса позволяет истолковывать
доказательство, что некоторая функция не является частично рекурсивной, как
доказательство отсутствия алгоритма вычисления ее значений.

6.

Определения
Пусть Y= F(X1, X2,…, Xn) – функция от N переменных. Обозначим:
D(Y) – область определения функции Y= F(X1, X2,…, Xn)
E(Y) – область значений функции Y= F(X1, X2,…, Xn)
Функция Y=F(X1, X2,…, Xn) Называется числовой функцией, если:
1) D(Y)=N ×∙ N ∙× …×∙ N = N*;
2) E(Y) ⊆ N
Функция Y=F(X1, X2,…, Xn) Называется частично числовой функцией, если:
1) D(Y) ⊆ N ×∙ N ∙× …×∙ N = N*;
2) E(Y) ⊆ N

7.

Простейшие функции
1) O(X)=0 – нуль-функция