Теорема Кратко
Перейти к навигации
Перейти к поиску
Теорема Кратко — утверждение об алгоритмической неразрешимости проблемы полноты относительно операций суперпозиции и обратной связи для конечных систем автоматов. Установлена в 1964 году советским математиком Мирославом Кратко (укр. Кратко Мирослав Іванович)[1].
Суть проблемы полноты конечной системы автоматов заключается в том, чтобы по заданному автоматному базису выяснить, является ли он полным. Если схемами на основе данного автоматного базиса могут быть реализованы все автоматы с заданным алфавитом, то он называется полным, иначе — неполным[2].
Примечания[править | править код]
- ↑ Кратко М. И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов // Доклады АН СССР. — 1964. — Т. 155, № 1. — С. 35–37.
- ↑ Шоломов, 1980, с. 222—229.
Литература[править | править код]
- Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. — М.: Наука, 1980. — 400 с.
 | Для улучшения этой статьи по математике желательно:
|
| На эту статью не ссылаются другие статьи Википедии. |