Теорема Кратко — утверждение об алгоритмической неразрешимости проблемы полноты относительно операций суперпозиции и обратной связи для конечных систем автоматов. Установлена в 1964 году советским математиком .
Суть проблемы полноты конечной системы автоматов заключается в том, чтобы по заданному автоматному базису выяснить, является ли он полным. Если схемами на основе данного автоматного базиса могут быть реализованы все автоматы с заданным алфавитом, то он называется полным, иначе — неполным.
Примечания
Литература
Кратко