Алгоритмическая система А.Чёрча 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Алгоритмическая система А.Чёрча



 

Все известные примеры алгоритмов можно свести к вопросу вычисления подходящей функции. Считая эту черту алгоритмов основной, можно построить формальное уточнение понятия вычислимой функции. В основе этого утверждения лежит тезис Черча: “Всякая функция, значение которой может вычисляться эффективно, является частично-рекурсивной” (т.е. вычислимыми функциями являются частично-рекурсивные функции – функции, получаемые за конечное число шагов из простейших с помощью суперпозиции, примитивной рекурсии и μ-оператора).

 

В свете изложенного в алгоритмической системе Черча исходными конструктивными объектами являются базисные функции , , (x1, x2,…,xm,…,xn)= xm, конструктивный процесс обусловлен применением к базисным функциям операторов суперпозиции S, примитивной рекурсии R и минимизации μ, а результатом конечного процесса являются рекурсивные функции, т.е.:

Результат

Отметим, что:

- вычислимая функция всегда имеет сопутствующий ей алгоритм Sp;

- невычислимая функция не имеет сопутствующего алгоритма (заранее заданной эффективной процедуры Sf);

- класс всюду определенных вычислимых функций эквивалентен классу рекурсивных функций;

- всякая вычислимая функция вычислима на подходящей машине Тьюринга;

- вопрос о вычислимости функции равносилен вопросу о ее рекурсивности.

 

A. Базисные функции

Базисные (простейшие элементарные) функции – числовые вычислимые функции , сопутствующие алгоритмы которых – одношаговые (очевидно, что это всюду определенные рекурсивные функции)

  1. Нуль-функция Z (x1, x2,…,xk)=0 – k-арная функция (оператор аннулирования Z), соответствующий алгоритм вычисления которой: “Любой совокупности значений аргументов xi функции Z ставится в соответствие ее значение 0”.

Примеры:

; ;

 

  1. Функция тождества (x1, x2,…,xm,…,xn)= xm ( - оператор проектирования) – n-арная функция, алгоритм вычисления которой: “Значением функции принять значение m-го аргумента.” (m, n>0, m n).

Примеры:

(7,6,1,4)= 6, (6)= 6, (7,15)= 15.

 

  1. Функция следования (λ – оператор сдвига) – унарная функция, для которой: “Значением принять натуральное число, следующее за числом, являющимся значением аргумента x ”.

Примеры:

; .

 

Замечание: базисные функции имеют значения только для заданных значений их аргументов.

 

Б. Операторы построения производных рекурсивных функций

Ниже рассмотрим три оператора (операции) получения алгебраических функции из базисных.

 

1. Оператором суперпозиции(подстановки) Snm называется операция подстановки в функцию от m переменных m функций от n переменных. (одних и тех же). ,а сопутствующий алгоритм которого: «Значения m –арных функций принять за значения аргументов n–арной функции и вычислить её значение». В этом случае говорят, что m –арная функция получена в результате операции суперпозиции Sn+1 из функций .

 

Пример.

Функция f(x1,…, xn) возникает из функций h(x1,…, xm), g1(x1,…, xn), …gm(x1,…, xn) суперпозицией, если

f(x1,…, xn)= Snm(h, g1,…, gm) = h(g1(x1,…, xn), …, gm (x1,…, xn)).

Если заданы функции Jnm и операторы Snm, то можно считать заданными всевозможные операторы подстановки функции в функцию, а также переименования, перестановки и отождествления переменных.

Так, если f(x1, x2)= h(g1(x1, x2), g2(x1)), то ее стандартный вид следующий: f(x1, x2)= S22(h(x1, x2), g1 (x1, x2), S12 (J21(x1, x2), g2(x1), g3(x1))), где g3 – любая функция от х1. Если же имеем f(x2, x1, х3, …, xn) и f(x1, x1, x3,…, xn), то пишем:

f(x2, x1, х3, …, xn) = f(J22(x1, x2), J21(x1, x2), х3, …, xn),

f(x1, x1, x3,…, xn)= f(J21(x1, x2), J21(x1, x2), х3, …, xn).

 

Пример:

2. Оператором примитивной рекурсии Rn[f1n-1,f2n+1,x1(n)]=fmn называется процесс определения функции f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:

f(x1, x2, …, xn, 0)= g(x1, x2,…, xn)

f(x1, x2, …, xn, y+1)=h(x1, x2,…, xn, y, f(x1, x2, …, xn, y)),

где g и h – две различные функции соответственно n и n+2 аргументов.

Эта пара равенств называется схемой примитивной рекурсии. Тот факт, что функция f определена схемой примитивной рекурсии выражается равенством f(x1, x2, …, xn, y)=Rn(g, h). В случае, когда n=0, то есть определяемая функция f является одноместной, схема примитивной рекурсии принимает более простой вид:

f(0)=с, f(у+1)=h(y, f(y)), где с – константа.

 

Схема примитивной рекурсии определяет f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точках: значение функции f в точке у+1 зависит от значения функции f в точке у. Очевидно, что для вычисления f(x1,…, xn, k) понадобиться k+1 вычислений по схеме примитивной рекурсии – для у=0, k.

 

Замечания:

Существенным в операторе примитивной рекурсии Rn является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной у (остальные n переменных x1, x2, …, xn на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров).

 

 

3. Оператор минимизации (m- оператор).

Оператором минимизации m (наименьшего числа оператора) называется преобразование (n+1)-местной функции (в общем случае частичной) j в n-местную f, такую, что для любых х1, х2, …хn, у равенство f(х1, х2, …хn)=у имеет место лишь в том случае, если определены и не равны нулю значения j(х1, …, хn, 0), …, j(х1, …, хn, у-1) и при этом j(х1, х2, …хn, у)=0. Применение оператора минимизации обозначают m[j, (y)], где у - исчезающий аргумент.

 

Говорят, что n-местная арифметическая функция f: Nn®N получается из функции j: Nn+1®N с помощью m-оператора, если выполнено условие: для любых k1, k2,…, kn, kÎN. f(k1, k2,…, kn)=k, тогда и только тогда, когда для всех l<k значения j(k1, k2,…, kn, l) определены и отличны от нуля, а значение j(k1, k2,…, kn, k) определено и равно нулю.

Если f получается из функции j с помощью оператора наименьшего числа m, то пишут: f(x1, x2,…, xn)=my[j(x1,…, xn, y)=0].

 

Важным свойством m-оператора является то, что с его помощью из вычислимой функции jвсегда получается частичная вычислимая функция f. Именно, если имеется алгоритм для вычисления j, то значение f(x1, x2,…, xn) может вычисляться следующим образом: вычисляется j(x1, x2,…, xn, 0); если процесс вычисления закончился, то есть значение j(x1, x2,…, xn, 0) определено, и j(x1, x2,…, xn, 0)=0, то полагаем f(x1, x2,…, xn)=0, а если j(x1, x2,…, xn, 0)¹0, то начинают вычислять j(x1, x2,…, xn, 1). Если процесс вычисления закончился и j(x1, x2,…, xn, 1)=0, то полагают f(x1, x2,…, xn)=1, а если j(x1, x2,…, xn, 1)¹0, то переходят к вычислению j(x1, x2,…, xn, 2) и так далее.

Процесс вычисления закончится, если найдется такое у, что для всех z < y значение j(x1, x2,…, xn, z) определено и отлично от нуля, а j(x1, x2,…, xn, у) определено и равно нулю. Тогда f(x1, x2,…, xn) = у.

 

Пример:

f(x)=my[12*y-x½=0]. Тогда f(x)=x/2 при всех четных значениях хÎN.

Замечание:

Примитивно-рекурсивные функции всегда определены (имеют значения) для любых значений аргументов. Иначе обстоит дело с функциями, полученными при помощи m-оператора. Для некоторых комбинаций значений аргументов они могут быть не определены, потому что исходная функция не принимает нулевых значений.

Пример:

det f(x)=m[J21(x, y), (y)].

Полученная функция f(х) обладает следующими свойствами:

f(0)=0, f(k) не существует при k¹0. Последнее означает, что для заданной функции J21(x, y) m-оператор не может построить f(k) kÎN, так как при x=k функция j(x, y)= J21(x, y) ни для какого значения у не будет равной нулю.

 



Поделиться:


Последнее изменение этой страницы: 2016-04-19; просмотров: 292; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.205.246.61 (0.018 с.)