Ну, похнали.

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