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

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

Реферат

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

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

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

Польщи М.В.

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

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

получить й из функций 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+y 2x ,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 )

[pic]

Докажем, что L2КL3 (для этого выразим x*y и операцию ограниченной

минимизации через функции L2 )

[pic]

Пусть

[pic] тогда

[pic] [pic]

Докажем, что L3КL4 (для этого выразим x+y и операцию ограниченной

рекурсии через функции L3 )

[pic]

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

функции Геделя.

[pic]

Пусть

[pic] тогда

[pic]

Отношение, примененное в операция конечной минимизации, является

элементарным по Кальмару.

Докажем, что L4КL1 (для этого выразим операции суммирования и

мультиплицирования через функции L4)

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

[pic]

Где y(x,y)-к-ступенчатая функция.

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

[pic]

Докажем, что L1КL5 (для этого выразим x*y через функции L5 )

[pic]

Докажем, что L5КL3 (для этого выразим 2x и операцию ограниченной

минимизации выразим через функции L5 )

[pic]

Пусть

[pic] тогда

[pic]

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