Эквивалентность пяти классов функций элементарных по Кальмару

Реферат

Эквивалентность пяти классов функций элементарных по Кальмару

студента группы ТК

четвертого курса

Польщи М.В.

Научный руководитель: профессор Лисовик Леонид Петрович

Определение. Функция называется элементарной по Кальмару, если ее можно получить й из функций 1, Iⁿ_m,

Определим пять классов функций, элементарных по Кальмару.

L₁ н Класс функций, получаемый из функций 1, Iⁿ_m,

L₂ н Класс функций, получаемый из функций 1, Iⁿ_m, x ,S, также конечного применения операции суммирования.

L₃ н Класс функций, получаемый из функций 1, Iⁿ_m, x,S, также конечного применения операции ограниченной минимизации.

L₄ н Класс функций, получаемый из функций 1, Iⁿ_m, x ,S, также конечного применения операции ограниченной рекурсии.

L₅ н Класс функций, получаемый из функций 1, Iⁿ_m,

Доказательство будем проводить по следующей схеме:

1. L₁ÊL₂ÊL₃ÊL₄ÊL₁

2. L₁ÊL₅

3. L₅ÊL₃

Докажем, что L₁ÊL₂ (для этого выразим 2^x через функции L₁ )

Докажем, что L₂ÊL₃ (для этого выразим 2 )

Пусть

атогда

а

Докажем, что L₃ÊL₄ (для этого выразим 3 )

Выразим операцию ограниченной рекурсии на основании следующего свойства функции Геделя.

Пусть

атогда

Отношение, примененное в операция конечной минимизации, является элементарным по Кальмару.

Докажем, что L₄ÊL₁ (для этого выразим операции суммирования и мультиплицирования через функции L₄)

Выразим м3ультиплицирование через ограниченную рекурсию.

Где

Выразим суммирование через ограниченную рекурсию.

Докажем, что L₁ÊL₅ (для этого выразим 5 )

Докажем, что L₅ÊL₃ (для этого выразим 2^x и операцию ограниченной минимизации выразим через функции L₅ )

Пусть

атогда

Эквивалентность классов доказана.