Реферат: Эквивалентность пяти классов функций элементарных по Кальмару
Реферат
Эквивалентность пяти классовфункций элементарных по Кальмару
студента группы ТК
четвертого курса
Польщи М.В.
Научный руководитель: профессор Лисовик Леонид Петрович
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">Определение. Функцияназывается элементарной по Кальмару, если ее можно получить й из функций s1, Inm,x+y,x-y,S,а также конечногоприменения операцийсуммирования и мультиплицирования.
Определим пять классовфункций, элементарных по Кальмару.
L1 Классфункций, получаемый из функций s1, Inm,x+y,x-y,S,а также конечногоприменения операцийсуммирования и мультиплицирования.
L2 Класс функций, получаемый изфункций s1, Inm,x-y,2x,S,а также конечного применения операции суммирования.
L3 Класс функций, получаемый изфункций s1, Inm,x-y,x*y, 2x,S,а также конечногоприменения операции ограниченной минимизации.
L4 Класс функций, получаемый изфункций s1, Inm,x-y,x+y2x,S,а также конечного применения операции ограниченной рекурсии.
L5 Класс функций, получаемый изфункций s1, Inm,x-y,x*y, S,а также конечногоприменения операции мультиплицирования.
Доказательство будемпроводить по следующей схеме:
1. L1ÊL2ÊL3ÊL4ÊL1
2. L1ÊL5
3. L5ÊL3
Докажем, что L1ÊL2(для этого выразим 2xчерез функции L1)
<img src="/cache/referats/3307/image002.gif" v:shapes="_x0000_i1025">
Докажем, что L2ÊL3(для этого выразим x*y и операцию ограниченнойминимизации через функции L2)
<img src="/cache/referats/3307/image004.gif" v:shapes="_x0000_i1026">
Пусть
<img src="/cache/referats/3307/image006.gif" v:shapes="_x0000_i1027"> тогда
<img src="/cache/referats/3307/image008.gif" v:shapes="_x0000_i1028"> <img src="/cache/referats/3307/image010.gif" v:shapes="_x0000_i1029">
Докажем, что L3ÊL4(для этого выразим x+y иоперацию ограниченной рекурсии через функции L3)
<img src="/cache/referats/3307/image012.gif" v:shapes="_x0000_i1030">
Выразим операциюограниченной рекурсии на основании следующего свойства функции Геделя.
<img src="/cache/referats/3307/image014.gif" v:shapes="_x0000_i1031">
Пусть
<img src="/cache/referats/3307/image016.gif" v:shapes="_x0000_i1032"> тогда
<img src="/cache/referats/3307/image018.gif" v:shapes="_x0000_i1033">
Отношение, примененное воперация конечной минимизации, является элементарным по Кальмару.
Докажем, что L4ÊL1(для этого выразим операции суммирования имультиплицирования через функции L4)
Выразим м3ультиплицированиечерез ограниченную рекурсию.
<img src="/cache/referats/3307/image020.gif" v:shapes="_x0000_i1034">
Где y(x,y)-к-ступенчатая функция.
Выразим суммирование черезограниченную рекурсию.
<img src="/cache/referats/3307/image022.gif" v:shapes="_x0000_i1035">
Докажем, что L1ÊL5(для этого выразим x*y через функции L5)
<img src="/cache/referats/3307/image004.gif" v:shapes="_x0000_i1036">
Докажем, что L5ÊL3(для этого выразим 2xиоперацию ограниченной минимизации выразим через функции L5)
<img src="/cache/referats/3307/image024.gif" v:shapes="_x0000_i1037">
Пусть
<img src="/cache/referats/3307/image006.gif" v:shapes="_x0000_i1038"> тогда
<img src="/cache/referats/3307/image026.gif" v:shapes="_x0000_i1039">
Эквивалентность классовдоказана.