English Russian
Известия
Журнал
теоретических
и прикладных
исследований
 Алтайского государственного университета
Print ISSN 1561-9443
On-line ISSN 1561-9451
Список выпусков
Содержание 1-2(73) 2012
Управление, вычислительная техника и информатика
Математика и механика
Физика
Редакционная коллегия
Форматы файлов полных текстов статей
 
1-2(73)2012
Математика и механика

Предыдущий | Следующий
 
В.А. Ганов

Конечные автоматы и нормальное исчисление Поста

Строится базис конечных автоматов, связанный выводимостью слов в нормальном исчислении Поста. Определяются операторы, реализуемые логическими сетями над этим базисом. Они являются вычислимыми на автоматах Мура, но их класс рекурсивно неразрешимый. При введении ограничений на сложность сети множество соответствующих операторов становится рекурсивным.
Ключевые слова: конечные автоматы, логические сети, выводимость слов, рекурсивно неразрешимые множества.

Полный текст в формате PDF, 226Kb. Язык: русский.

ГАНОВ Валерий Александрович
доктор физико-математических наук, профессор, доцент кафедры алгебры и математической логики Алтайского государственного университета (Барнаул)
Печатное издание "Известия АГУ" copyright © 1996-2012 Алтайский государственный университет.
Зарегистрировано Комитетом РФ по печати. Свидетельство о регистрации Г-0745. Все права защищены. Ни одна из частей журнала либо издание в целом не могут быть перепечатаны без письменного разрешения авторов или издателя.
По вопросам приобретения журнала обращаться в издательство АГУ по адресу:
656049, Россия, Барнаул, ул. Димитрова 66. Телефон +7 (3852) 366351.