РАЗНОЕ (последнее)
Эквивалентность пяти классов функций элементарных по Кальмару
Публикации на разные темы ("без рубрики").
Эквивалентность пяти классов функций элементарных по Кальмару
Определение. Функция называется элементарной по Кальмару, если ее можно получить й из функций s 1 , I n m , x+y, x-y, S, а также конечного применения операций суммирования и мультиплицирования.
Определим пять классов функций, элементарных по Кальмару.
L 1 Класс функций, получаемый из функций s 1 , I n m , x+y, x-y, S, а также конечного применения операций суммирования и мультиплицирования.
L 2 Класс функций, получаемый из функций s 1 , I n m , x-y, 2 x ,S, а также конечного применения операции суммирования.
L 3 Класс функций, получаемый из функций s 1 , I n m , x-y, x*y, 2 x ,S, а также конечного применения операции ограниченной минимизации.
L 4 Класс функций, получаемый из функций s 1 , I n m , x-y, x+y 2 x ,S, а также конечного применения операции ограниченной рекурсии.
L 5 Класс функций, получаемый из функций s 1 , I n m , x-y, x*y, S, а также конечного применения операции мультиплицирования.
Доказательство будем проводить по следующей схеме:
1. L 1 ? L 2 ? L 3 ? L 4 ? L 1
2. L 1 ? L 5
3. L 5 ? L 3
Докажем, что L 1 ? L 2 (для этого выразим 2 x через функции L 1 )
Докажем, что L 2 ? L 3 (для этого выразим x*y и операцию ограниченной минимизации через функции L 2 )
Пусть
тогда
Докажем, что L 3 ? L 4 (для этого выразим x+y и операцию ограниченной рекурсии через функции L 3 )
Выразим операцию ограниченной рекурсии на основании следующего свойства функции Геделя.
Пусть
тогда
Отношение, примененное в операция конечной минимизации, является элементарным по Кальмару.
Докажем, что L 4 ? L 1 (для этого выразим операции суммирования и мультиплицирования через функции L 4 )
Выразим м3ультиплицирование через ограниченную рекурсию.
Где ?(x,y)-к-ступенчатая функция.
Выразим суммирование через ограниченную рекурсию.
Докажем, что L 1 ? L 5 (для этого выразим x*y через функции L 5 )
Докажем, что L 5 ? L 3 (для этого выразим 2 x и операцию ограниченной минимизации выразим через функции L 5 )
Пусть
тогда
Эквивалентность классов доказана.
Опубликовано 04 июня 2010 года
Новые статьи на library.by:
РАЗНОЕ:
Комментируем публикацию: Эквивалентность пяти классов функций элементарных по Кальмару
подняться наверх ↑
ССЫЛКИ ДЛЯ СПИСКА ЛИТЕРАТУРЫ
Стандарт используется в белорусских учебных заведениях различного типа.
Для образовательных и научно-исследовательских учреждений РФ
Прямой URL на данную страницу для блога или сайта
Предполагаемый источник
Полностью готовые для научного цитирования ссылки. Вставьте их в статью, исследование, реферат, курсой или дипломный проект, чтобы сослаться на данную публикацию №1275679405 в базе LIBRARY.BY.
подняться наверх ↑
ПАРТНЁРЫ БИБЛИОТЕКИ рекомендуем!
подняться наверх ↑
ОБРАТНО В РУБРИКУ?
Уважаемый читатель! Подписывайтесь на LIBRARY.BY в VKновости, VKтрансляция и Одноклассниках, чтобы быстро узнавать о событиях онлайн библиотеки.
Добавить статью
Обнародовать свои произведения
Редактировать работы
Для действующих авторов
Зарегистрироваться
Доступ к модулю публикаций