Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритмическая система А.Чёрча
Все известные примеры алгоритмов можно свести к вопросу вычисления подходящей функции. Считая эту черту алгоритмов основной, можно построить формальное уточнение понятия вычислимой функции. В основе этого утверждения лежит тезис Черча: “Всякая функция, значение которой может вычисляться эффективно, является частично-рекурсивной” (т.е. вычислимыми функциями являются частично-рекурсивные функции – функции, получаемые за конечное число шагов из простейших с помощью суперпозиции, примитивной рекурсии и μ-оператора).
В свете изложенного в алгоритмической системе Черча исходными конструктивными объектами являются базисные функции , , (x1, x2,…,xm,…,xn)= xm, конструктивный процесс обусловлен применением к базисным функциям операторов суперпозиции S, примитивной рекурсии R и минимизации μ, а результатом конечного процесса являются рекурсивные функции, т.е.:
Отметим, что: - вычислимая функция всегда имеет сопутствующий ей алгоритм Sp; - невычислимая функция не имеет сопутствующего алгоритма (заранее заданной эффективной процедуры Sf); - класс всюду определенных вычислимых функций эквивалентен классу рекурсивных функций; - всякая вычислимая функция вычислима на подходящей машине Тьюринга; - вопрос о вычислимости функции равносилен вопросу о ее рекурсивности.
A. Базисные функции Базисные (простейшие элементарные) функции – числовые вычислимые функции , сопутствующие алгоритмы которых – одношаговые (очевидно, что это всюду определенные рекурсивные функции)
Примеры: ; ;
Примеры: (7,6,1,4)= 6, (6)= 6, (7,15)= 15.
Примеры: ; .
Замечание: базисные функции имеют значения только для заданных значений их аргументов.
Б. Операторы построения производных рекурсивных функций Ниже рассмотрим три оператора (операции) получения алгебраических функции из базисных.
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 с.) |