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

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

Определим отношение

-> <= Conf(M) x Conf(M)
 M

C_1 ->_M C_2 - конфигурация С_1 переходит в конфигурацию С_2 за 1 шаг работы М

1. \delta(q, a) = (q', a', S)
qa -> q'a'S

AqaB ->_M Aq'a'B

2. \delta(q, a) = (q', a', R)
qa -> q'a'R'

2.1 B = b B' != /\
AqaB ->_M Aaq'bB'

2.2 B = /\
AqaB ->_M Aa'a'#

3.qa -> q'a'L

3.1 AqaB ->_M A'q'ba'B
A = A', b != /\
3.2 A = /\ AqaB ->_M q'#a'B

C_1 -»_M C_2 - C_1 переходит в C_2 за несколько шагов (это то, что называется вычислением МТ)

*происходит какая-то дичь во время обсуждения, когда машина зацикливается