Математическая логика и теория алгоритмов. Анкудинов Г.И - 71 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

отличны от x , а при y=k+1 не определено;
n
,...,x ; y) при всех y=0,1,2,3,... определены,
3) значения f(x
1 n-1
но отличны от x
.
n
Определение 4.2. Функция называется частично-рекурсивной
(ЧР), если она может быть получена из S(x), 0(x) и Im с помощью
применения конечного числа операторов подстановки, примитивной
рекурсии и минимизации.
Определение 4.3. ЧР-функция называется общерекурсивной
(ОР), если она всюду определена.
Примеры ЧР-функций
Целая часть [x/y]. Функция x/y является частичной, поскольку
для y=0 не определена. Введем в рассмотрение функцию [x/y],
полученную доопределением x/y так, что [x/0]=x. Можно показать,
что [x/y]= μ
z
[(x ¬ z)((x + 1) ¬ y(z + 1))=0], следовательно, [x/y] – ОР-
функция [14].
Функция [x mod y]. Функция x mod y (остаток от деления x на y)
является частичной, поскольку для y=0 не определена. Введем в
рассмотрение функцию [x mod y], полученную доопределением
x mod y так, что [x mod 0]=x.
Можно показать, что [x mod y]= x ¬ y[x/ y], следовательно, [x
mod y] – ОР-функция [14].
4.4. Эквивалентность алгоритмических систем
Как было сказано в начале данной главы, А.Черч впервые
обосновал положение о том, что все уточнения понятия алгоритма
эквивалентны. Продемонстрируем подход к доказательству
эквивалентности вычислимости по Тьюрингу, и класса функций,
определяемых ЧР-схемой.
Теорема 4.1. Класс функций, вычислимых по Тьюрингу,
эквивалентен классу ЧР-функций.
155

Страницы