Теорема Кратко

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Теорема Кратко — утверждение об алгоритмической неразрешимости проблемы полноты относительно операций суперпозиции и обратной связи для конечных систем автоматов. Установлена в 1964 году советским математиком Мирославом Кратко (укр. Кратко Мирослав Іванович)[1].

Суть проблемы полноты конечной системы автоматов заключается в том, чтобы по заданному автоматному базису выяснить, является ли он полным. Если схемами на основе данного автоматного базиса могут быть реализованы все автоматы с заданным алфавитом, то он называется полным, иначе — неполным[2].

Примечания[править | править вики-текст]

  1. Кратко М. И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов // Доклады АН СССР. — 1964. — Т. 155, № 1. — С. 35–37.
  2. Шоломов, 1980, с. 222—229.

Литература[править | править вики-текст]

  • Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. — М.: Наука, 1980. — 400 с.