4. Теорія програмування та обчислень

11. Співвідношення між класами примітивно рекурсивних та елементарних функцій

Нехай , де носій El – клас елементарних функцій; – це операції.

Алфавіт:

Визначення операторного терму:

1. Усі символи базових функцій є операторними термами.

2. Якщо є операторними термами для завдання m-арних функцій, а є термом для задання n-арної функції, то терм є термом для позначення m-арної функції.

3. Якщо є операторним термом для бінарної функції, то терми є операторними термами для бінарних функцій.

4. Інших оператор них термів не існує.

Зрозуміло, що кожна елементарна функція є ПРФ. Доведемо зворотне твердження – що це включення строге.

Для цього розглянемо допоміжну функцію :

Функцію назвемо k-східчастою, якщо має місце умова: .

Теорема: Довільна елементарна функція є k-східчастою для певного відповідного значення k.

Доведення:

• Базові функції:

  • 

  • так само для ;

  • .

• Нехай є операторним термом для бінарної функції . Утворимо функції та (обидві вони бінарні). Нехай є -східчастою функцією. Тоді є -східчастими функціями.

  • Це випливає з двох нерівностей:

    • 

    • 

  • Обидві вони доводяться математичною індукцією.

• Нехай , де - -арна функція, а - -арні. Тоді є -арною функцією.

Покажемо тепер, що існує ПРФ, яка не є елементарною.

Наприклад, візьмемо функцію . Для такої функції не існує такого єдиного , для якого можна було б мажорувати цю функцію -східчастою.

4. Теорія програмування та обчислень

12. Техніка слідів. Лема про заміщення

Р ассмотрим вычислит. процесс, обозначаемый M[P], который выполняет МТ М, запущенная в начальной конфигурации с исходным словом р. Пронумеруем границы между соседними ячейками так:

С каждой фиксированной границей j можно ассоциировать послед-сть внутренних состояний МТ след. образом: если в процессе М[P] головка ни разу не пересекает границу j, то эта последовательность пуста (не содержит никаких элементов). Пусть головка пересекает границу j ровно s раз: первый раз в состоянии q(1), 2-ой – в состоянии q(2) и т.д. Тогда последовательность q(1), q(2),…, q(s), являющаяся словом в алфавите Q внутренних состояний, называется следом процесса M[P] в точке j и обозначается след_M(P, j). Это обозначение содержит указание на рассматриваемую машину М и на исходное слово Р. Однако в тех случаях, когда из контекста ясно, какая имеется в виду машина или слово, будем применять упрощенніе обозначения типа след(Р, j) или след(j). Если первое прохождение головки было слева направо, то второе будет справа налево и далее направление будет также чередоваться. Ясно, что при j>0 первое прохождение будет только слева направо, а при j0 – в противоположном направлении. Если процесс M[P] бесконечен, то может случиться, что в некоторых границах j след также будет бесконечен. Однако поскольку мы далее будем рассматривать только конечные процессы, заканчивающиеся выдачей результирующего слова R (зависящего от исходного слова P), то и следы будут конечными. Пусть |след(j)| обозначает длину следа в т. j, т. е. число пересечений границы j. Очевидно, что каждое пересечение головкой какой-либо границы связано с затратой 1 такта работы МТ. Поэтому справедливо нер-во: t_M(P)|след(P, j)| (1), где суммирование берется по любому мн-ву границ. Строгое нер-во может возникнуть за счет того, что рассматривается лишь часть границ, пересекаемых головкой, а также по той причине, что на некоторых тактах головка не сдвигается с обозреваемой ячейки, а следовательно не совершается никаких пересечений. Иногда анализ процесса M[P] позволяет обнаружить, что в некоторых точках возникают достаточно длинные следы. В таких случаях нер-во (1) может послужить для установления нижней оценки сигнализирующей t_M(P).

Лемма о замещениях.

Пусть есть МТ А=<K, Г, , Н, q₀, q^*> и разметки ленты ₁ и ₂. Пусть на разметке _i возникает полное поведение q_i, i=1,2 MT A.

П усть теперь для некоторых i и j (i<j) верно S(i, q₁)=S(j, q₂). След S(i, q_i) конечен, и если q₁=(₁, q₁, i₁) , q₂=(₂, q₂, i₂) , то (i₁<i) & (i₂<j) или (i_1i) & (i_2j). Тогда на разметке :

Возникает полное поведение q₃ МТ А такое, что k

Д оказательство будем вести индукцией по n – длине следа S=S(i, q₁), n=|S|.

При n=0 в случае (i₁<i) & (i₂<j) имеем, что начиная с разметки ₁ МТ не заходит правее (i-1)-ой ячейки, а тогда k i |S(k, q₁)|=0. Аналогично, k j |S(k, q₂)|=0, а тогда утверждение леммы тривиально. Случай (i₁i) & (i₂j) разбирается аналогично. Пусть мы доказали лемму для некоторого n. Докажем ее справедливость для n+1. Пусть (i₁<i) & (i₂<j). Поведение q₁ и q₂ можно представить в виде

О статочные поведения и являются полными, и их следы на i- и j- разрезах соответственно совпадают и меют длину n, к тому же (i=i) & (j=j). Мы попадаем в условия леммы, а тогда на разметке возникает полное поведение МТ А такое, что k

З аметим, что .

П оведение q₃ на разметке ₃ можно представить в виде

получено из заменой разметки  на такую

И меем :

Что и требовалось доказать.

Случай (i₁i) & (i₂j) разбирается аналогично. По принципу мат. индукции лемма доказана.