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

  • В.А. Ганов Алтайский государственный университет (Барнаул, Россия) Email: ganov-math.asu.ru@mail.ru
  • Р.В. Дегтерева Алтайский государственный технический университет им. И.И. Ползунова (Барнаул, Россия) Email: docentdegtereva@gmail.com
Ключевые слова: конечные автоматы Мура, логические сети, вывод слова в исчислении Бэра

Аннотация

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

DOI 10.14258/izvasu(2015)1.2-17

Скачивания

Данные скачивания пока недоступны.

Metrics

Загрузка метрик ...

Биографии авторов

В.А. Ганов, Алтайский государственный университет (Барнаул, Россия)
доктор физико-математических наук, профессор кафедры алгебры и математической логики
Р.В. Дегтерева, Алтайский государственный технический университет им. И.И. Ползунова (Барнаул, Россия)
кандидат физико-математических наук, доцент кафедры высшей математики и математического моделирования

Литература

Марков А.А., Нагорный Н.М. Теория алгорифмов. - М., 1984.

Кратко М.И. О существовании нерекурсивных базисов конечных автоматов // Алгебра и логика. - 1964. - Т. 3, № 2.

Как цитировать
Ганов В., Дегтерева Р. Алгоритмические проблемы и ограничения на сложность вывода // Известия Алтайского государственного университета, 1, № 1/2(85) DOI: 10.14258/izvasu(2015)1.2-17. URL: http://izvestiya.asu.ru/article/view/%282015%291.2-17.