English Russian
Известия
Журнал
теоретических
и прикладных
исследований
Алтайского государственного университета
Print ISSN 1561-9443
On-line ISSN 1561-9451
Список выпусков
Содержание номера
Физика
Математика
О журнале
Редакционная коллегия и редакционный совет журнала
Порядок рецензирования научных статей в журнале "Известия АлтГУ"
Новые правила представления статей в журнал «Известия АлтГУ»
Публикационная этика журнала «Известия АлтГУ»
 
1-2(85)2015
  МАТЕМАТИКА

В.А. Ганов, Р.В. Дегтерева

Алгоритмические проблемы и ограничения на сложность вывода

Авторы продолжают свои исследования логических сетей над базисом конечных автоматов. Вводится специальный базис конечных автоматов и определяются словарные операторы, реализуемые логическими сетями над этим базисом. Программы автоматов связаны с правилами вывода известного исчисления Поста. Главная особенность этого исчисления в том, что в нем проблема эквивалентности слов не является алгоритмически разрешимой. Отсюда следует, что множество операторов, реализуемых данными сетями, также не является алгоритмически разрешимым. Далее определяются правильно организованные логические сети, и показывается, что только автоматы таких сетей работают правильно. Сложность вывода определяется следующим образом. Выделяются так называемые основные автоматы, которые непосредственно моделируют правила вывода слов в данном исчислении. Сложностью вывода называется число основных автоматов, содержащихся в вычислительной модели этого вывода. Доказывается, что при фиксированном ограничении множество операторов, реализуемых выделенными сетями, является алгоритмически разрешимым. Каждый реализуемый оператор связан с некоторым словом алфавита A0, выводимом в L0. Поэтому для данного оператора, соответствующего слову T, можно организовать поиск вывода этого слова путем перебора всех возможных выводов. И если искомый вывод короткий, то по теореме 10 он будет найден. А если этот вывод очень длинный или не существует, то этот метод не поможет.

DOI 10.14258/izvasu(2015)1.2-17

Ключевые слова: конечные автоматы Мура, логические сети, вывод слова в исчислении Бэра

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

ГАНОВ Валерий Александрович
доктор физико-математических наук, профессор кафедры алгебры и математической логики Алтайского государственного университета
E-mail: ganov-math.asu.ru@mail.ru

ДЕГТЕРЕВА Руслана Валерьевна
кандидат физико-математических наук, доцент кафедры высшей математики и математического моделирования Алтайского государственного технического университета (Барнаул, Россия)
E-mail: docentdegtereva@gmail.com

 

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