Вычисление функций автоматами со счётчиками - курсовая работа | ИСТИНА – Интеллектуальная Система Тематического Исследования НАукометрических данных

Научный руководитель: Волков Н.Ю.
Автор: Илхомов Мухаммад Муроджон угли
Тип: Бакалавр
Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
Кафедра: Филиал МГУ в г. Ташкент
Год защиты: 2022
Курс: 3
Аннотация: В данной работе изучаются одноместные частичные функции, вычислимые через автоматы с двумя счётчиками. Уже давно известно, что при специальной кодировке автомат с двумя счётчи- ками может моделировать автомат с тремя счётчиками и, как следствие, может вычислять любые одноместные функции, вычислимые по Тьюрингу. В этой работе рассматривается вычислимость в естественной кодировке. Вводится понятие манёвра, как простой части поведения автомата с 2 счётчиками. И вводятся по- нятия функции манёвра и функции манёвра с переключателем, которые можно вычислять за один манёвр. Вводятся операции обобщенной суперпозиции и специальной рекурсии над функциями с пере- ключателями. И через эти операции будет введен класс функций, называемых обобщенными функ- циями манёвра. Дальше вводится понятие вычислительного графа, который служит для доказательства равенства класса одноместных функций, вычислимых через автоматы с двумя счётчиками и класса обобщенных функций манёвра.
Добавил в систему: Волков Николай Юрьевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ЦЭМИ РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ЦЭМИ РАН

Вычисление функций автоматами со счётчикамикурсовая работа (Бакалавр)

Прикрепленные файлы