Лекция 4

X поставлены в соответствие однозначно определенные элементы Y, то говорят,

что задана частичная функция из Х в Y
(f: X -> Y)

в Y, называется областью определения функции, а совокупность элементов Y,

называют областью значений функции.

множеством X, то функция называется всюду определенной

алгоритм, позволяющий вычислить ее значение по известным значениям аргументов

функция следования;
0n(х1,х2,…,хn) = 0 - это n-местная функция тождественного равенства

нулю;
Inm (х1,х2,…,хn) = хm (1 ≤ m≤n; n = 1, 2, ...) - n-местная функция тождественного повторения значения одного из своих аргументов.

n-местную функцию g(х1,х2,…,хn).
В результате получается n-местная функция
h((х1,х2,…,хn) ) =

g(f1(х1,х2,…,хm), f2(х1,х2,…,хm), …, fn(х1,х2,…,хm))

суперпозицией (или подстановкой).
Обозначение: S(g, f1,..., fn )
Если умеем вычислять

функции
g, f1,..., fn , то функция h также может быть вычислена.

(x)= O1 -> h(x) = g(f (x)) = S1(O1)
Для

этого значение простейшей функции О1 должно быть подставлено в S1(x) = х + 1.
Но O1(х) = 0, следовательно,
h(x) = S(S1, O1) = S1(O1) = 0+1 = 1.

функция будет двуместной (n = 3 - 1 =2), следовательно

h(x1,x2) = I22(I11 ,01) = I22(x1, 0) = 0 .

y).
Говорят, что (n + 1)-местная частичная функция f образуется из

функций g и h посредством примитивной рекурсии, если для всех натуральных значений х1,х2,…,хn, у справедливо:
f (х1,х2,…,хn,0) = g(х1,х2,…,хn),
f(х1,х2,…,хn, y+1) = h(х1,х2,…,хn,y,f(х1,х2,…,хn,y))

получить конечным числом операций суперпозиции и примитивной рекурсии, исходя лишь

из простейших функций S1, On и Inm

является примитивно-рекурсивной.
Данная функция может быть представлена:
x+0 = x= I11(x),
x+(y+

1) = (х+у)+1 = S1(x+y).
Следовательно, функция f(x,y) образуется из примитивно рекурсивных функций операцией примитивной рекурсии и, следовательно, она сама примитивно рекурсивна.

= 0,
f(x, y+1)=x + f(y,x)
В данном случае g(х) = 0,

h(x,y,z) = x + z.
Так как f(x,0) = g(х) = 0 при любом х, то и
f(2,0) = 0, а другие значения можно вычислить последовательно:
f(2,1) = h(2,0,0) = 2 + 0 = 2;
f(2,2) = h(2,1,2) = 2 + 2 = 4;
f(2,3) =h(2,2,4) = 2 + 4 = 6.

Несложно доказать, что в данном примере
f(x,y) = ху

Зафиксируем значение x и выясним, при каких у

значение f(x,y) = 0.
Можно найти наименьшее из тех значений у , при которых f(х,у) = 0.

Примем обозначение:
F(х) = μy[f(x,y) = 0]
(читается: «наименьшее y такое, что f(x,y) = 0», a μy называют μ -оператором или оператором минимизации).

Зафиксируем значения х1,х2,…,хn-1, и выясним, при каких у значение f(х1,х2,…,хn-1

,y) = 0.
Можно найти наименьшее из тех значений у, при которых f(х1,х2,…,хn-1 ,у) = 0.

Примем обозначение:
F(х1,х2,…,хn-1) = μy[f(х1,х2,…,хn-1,y) = 0]
(читается: «наименьшее y такое, что f(х1,х2,…,хn-1,y) = 0»).

F:
Вычисляем f(х1,х2,…,хn,0); если значение равно нулю, то полагаем F (х1,х2,…,хn)

= 0. Если f(х1,х2,…,хn,0) ≠ 0, то переходим к следующему шагу.
Вычисляем f(х1,х2,…,хn,1); если значение равно нулю, то полагаем F (х1,х2,…,хn) = 1. Если f(х1,х2,…,хn,1) ≠ 0, то переходим к следующему шагу и т.д.
Если окажется, что для всех y функция f(х1,х2,…,хn,0) ≠ 0, то функция F (х1,х2,…,хn) считается неопределенной.

быть получена с помощью оператора минимизации к функции f(x,y,z) =

x-y-z:
F(x,y) = μz [x-y-z=0 или y + z =x] = μz[ I23 (x, y, z) + I33 (x, y, z) = I13(x, y, z)]

Вычислим, например, F(7,2), т.е. значение функции при y = 2 и х = 7. Будем z придавать последовательные значения:
z=0, 2 + 0 = 2≠7,
z=1, 2 + 1 = 3≠7,
z=2, 2 + 2 = 4≠7,
z=3, 2 + 3 = 5≠7,
z=4, 2 + 4 = 6≠7,
z=5, 2 + 5 = 7 = 7.
Таким образом, найдено значение функции F(7,2) = 5.

конечным числом операций суперпозиции, примитивной рекурсии и минимизации, исходя лишь

из простейших функций S1, On и Imn

всех частично рекурсивных функций.

означает фраза: «Машины Поста и Тьюринга являются абстрактными машинами»?
Для

чего предназначены машины Поста и Тьюринга?
 Как «устроена» машина Тьюринга?
 Каков принцип исполнения программы машиной Тьюринга?

алгоритмов?
3.Перечислите простейшие функции.
4. Перечислите операторы.
5. Чем отличается

частично рекурсивная функция от примитивно-рекурсивной?
6. Дайте определение частично-рекурсивной функции