Ну, похнали.

1. Все предложенные варианты формализации приводят к одному и тому же понятию вычислимой функции (алгоритма).
2. Для многих интуит. вычисл. функций были найдены программы вычисл. эти функции.
3. Любую программу в одной модели мы можем записать программой из другой модели.

Тезис Чёрча-Тьюринга.
Всякая "интуитивно" вычислимая функция вычислима в формальном смысле.

Понятия алгоритма:
Всякий алгоритм может принимать на вход какие-то данные.
Всякий алгоритм может давать на что-то выход.
Вход и выход конечны в символьном виде.
Всякий алгоритм - конечный текст.
Есть синтаксис (правила написания программы) и семантика (значение программы).
Алгоритм - пошаговый процесс. И каждый следующий шаг однозначно определён текущим положением.

\Sigma - алфавит.
f: \Sigma* -> \Sigma* - функция.
\Sigma* - множество всех конечных слов в алфавите \Sigma.

Мы будем рассматривать функции f: \N -> \N (функции от одной переменной).
И функции f: \N^k -> \N (функции от k переменных).

В нашем курсе \N = {0, 1, 2, ...}.

*Доказали, что метод мат. индукции верен*

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

Класс примитивно-рекурсивных функций (\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) нигде не определена

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

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