Тотальная функция - всюду определённая функция.
Частичная функция - не всюду определённая функция.

Класс примитивно-рекурсивных функций (\P\R) - это наименьший класс функций натурального аргумента,

1. содержащий базовые функции:
1.1. 0(x) \equiv 0 (конст. ноль),
1.2. S(x) = x + 1 (функции последовательности),
1.3. I^n_k = (x_1, x_2, ..., x_n) = x_k, где 1 <= k <= n (селекторная функция).

2. и замкнуты относительно операций:
2.1. Суперпозиции,
2.2. Примитивной рекурсии.

Эта функция определена на всех входах (доказывается по индукции).
---
(прим автора - объяснений к 2.* нет, так как мне очень лень это записывать 🙂).
---

f \in \P\R <=> \exists последовательность функций f_1, f_2, ..., f_n, т.ч. f_n = f, \forall k 1 <= k <= n -> f_k либо
1. является базовой,
2. получена из базовых правилом суперпозиции или примитивной рекурсии.
Последовательность таких f_1, f_2, ..., f_n является примитивно рекурсивной схемой определяющей функцию f.

Лекция 22.01.

Дерево вычислений.

* Для базовых функций дерево состоит из одной вершины, помеченной соответствующим равенством.
* Для cуперпозиции f(X) = y:

f(X) --> g1(X) = z1
     |--> g2(X) = z2
    |--> ...

Для gi(X) = zi строятся такие же деревья.

* f получено прим. рек. из g и h:

f(X, 0) = y --> g(X) = y
~~ or ~~
f(X, y + 1) = z
    |--> f(X, y) = u
    |--> h(X, y, u) = z

Утв. Каждая прим. рек. функция тотальна.
Док-во: индукция по построению (используя прим. рек. схему и то, что базовые функции тотальны).

Утв. Сущесвтует тотальная вычислимая функция, не являющаяся прим. рек.
Док-во: Пронумеруем все прим. рек. схемы (задающие прим. рек. функции от одной переменной): P_0, P_1, P_2, ...
Рассмтрим U(x, y) = P_x(y), тогда d(x) = U(x, x) + 1 - искомая функция. То, что d(x) не прим. рек доказывается от противного.

Слабая последовательность Гудстейна.

a_0 = 13 =2^3 + 2^2 + 2^0
a_1 = {2 -> 3, -1} = 3^3 + 3^2 + 3^0 - 1 = 3^3 + 3^2
a_2 = {3 -> 4, -1} = 4^3 + 4^2 - 1 = ...
a_3 = {4 ->5, -1} = ...
Утв. Всякая такая последовательность приходит в ноль.

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

f - ч. р., если f может быть получена из базовых операций, суперпозиции, прим. рекурсии и минимизации.

Лекция 3

Напоминание о частично рекурсивной функции

Минимизация: (она же мю-рекурсия)
f(x->) := my(g(x->, y) = 0)
Полуачается перебором y
y = 0, 1, 2, ...
g(x->, 0) != 0
g(x->, 1) != 0
.
.
g(x->, y-1) != 0
g(x->, y) = 0

Может статься, что на каком-то входе функция не определена, либо же такого y нет (тогда эта функция не определена при таком x)

*еще много раз повторил то же самое*

g(x, y) = 1
f(x) = my(g(x, y) = 0)
f(x) нигде не определена

Сказали, как обращаться с не всюду определенными функциями с помощью суперпозиции и примитивной рекурсии (если кто-то по дороге не определен, то никак)

*шутка про программистов*

Общерекурсивная функция - тотальная и частично рекурсивная

m-рекурсивная функция - м.б. получена как примитивно рекурсивная и специальной минимизации вида f(x) = my(g(x, y) = 0), где \forall x-> \exists y (g(x->, y) = 0)

Определение универсальной функции для класса n-местных функций (переписывать не буду, уж простите)

Лекция 4.

В начале - середине марта будет ДЗ. Дедлайн - две недели.
Задачи на примитивно рекурсивно / частично рекурсивные функции, на машины Тьюринга. Если успеем разобрать ещё какую-то модель, то и на неё что-то будет.

В конце марта будет КР.

Лекция 6.
Машины Тьюринга.

Память будем представлять в виде бесконечной в обе стороны ленты, которая разбита на ячейки:

------------------------
  ...  |  |  |  |  ...
------------------------

В ячейках у нас храянятся символы из некоторого конечного алфавита Г (ленточный (рабочий) алфавит Машины). При чём в одной ячейке только один символ.
В алфавите существует пробельный символ (будем обозначать его #).

Так же у нас есть управляющее устройство - головка Машины Тьюринга.
В каждый момент времени оно может смотреть только на одну ячейку, может двигаться на одну ячейку (в любую сторону (в т.ч. стоять на месте)), записывать что-то в ячейку.

У устройства Машины есть состояния q. Множество всех состояний конечно (будем обозначать его Q).

У машины есть действия:
L - сдвиг головки влево, S - остаться на месте, R - сдвиг головки вправо.

Команда программы выглядит так:
qa -> q'a'D
Читается вот так:
Если машина находится в состоянии q, а головка смотрит на эл-т a, то надо перейти в состояние q', записать в ячейку эл-т a' и сделать действие D.

У Машины есть q_0 - начальное состояние и q_f - заключительное состояние.

Тогда, программа - это функция Q \ {q_f} x Г -> Q x Г x D.

Изначально головка стоит перед первым символом первого слова.
В конце концов головка у нас стоит перед ответом.

Лекция 7
Конфигурация МТ; M = (Г, Q, ...)
AqaB, где А, В принадлежат Г* (те мн-ву всех слов в алфавите Г), q \in Q, a \in Г

...#|A|a|B|#...
       ^
       |
       q

Conf(M) - мн-во всех конфигураций машины M