|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О вычислимости функций малыми коллективами автоматовкурсовая работа (Магистр)
- Научный руководитель: Волков Николай Юрьевич
- Автор: Ушакова Валентина Владимировна
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Филиал МГУ в г. Ташкент
- Год защиты: 2018
- Курс: 1
- Аннотация: Данная работа продолжает исследования по вычислимости одноместных целочисленных функций коллективами автоматов. Показано, что любая периодическая целочисленная функция f(x): N0→ N0 вычислима некоторым коллективом из двух автоматов. Также показано, что являются вычислимыми коллективами из двух автоматов все функции, ко-торые при х>T0 выражаются формулой вида f(x)=x+С, где С - константа. Доказано, что никакие другие функции, кроме функций указанных выше типов, коллективами из двух автоматов не вычислимы. Эти же результаты обобщены на функции, аргументы и значения которых могут быть отрицательными, т.е. на функции вида f(x): Z→ Z. Результаты сохранились, с уточнением того, что вычисляемая периодическая функция может иметь разные предпериоды и периоды на положительной и на отрицательной полуосях, а функции из второго класса также могут иметь на положительной и на отрицательной полуосях разные предпериоды T0 и разные константы С. Кроме этого, являются вычислимыми коллективами из двух автоматов «гибриды» функций из этих двух классов, т.е. функции, которые на одной (положительной или отрицательной) полуоси множества целых чисел Z ведут себя, как периодическая функция, а на другой полуоси – выражаются формулой вида f(x)=x+С.
- Добавил в систему: Волков Николай Юрьевич