Числення ПостаЧислення Поста — клас числень, який запропонував американський математик Еміль Пост. Числення Поста можна розглядати як математичне уточнення інтуїтивного поняття алгоритму. ВизначенняЧисленням Поста називається четвірка виду , де:
Список правил виведення має вигляд: де
Слово Q називається виводимим із слів по описаному правилу, якщо для кожної змінної та знайдеться таке слово в алфавіті A, що, якщо підставити всі ці слова на місця входження цих змінних в описаному правилі, то отримаємо вираз виду:
Список слів називається виводом в численні , якщо кожне його слово є або аксіомою, або виводимо із попередніх слів по одному із правил виведення. Слово D називається виводимим в численні , якщо існує вивід, останнім словом якого є слово D. Властивості числення ПостаДоведено, що будь-яку рекурсивно перелічену множину слів в алфавіті A можна отримати як множину виводимих слів у спеціально підібраному численні Поста, що має лише скінченну кількість аксіом та правил виведення. Еміль Пост довів, що такий самий результат справедливий для більш вузького класу числень, так званих нормальних канонічних числень, всі правила яких мають вигляд . Разом з тим, числення Поста, які мають правила виводу породжують лише регулярні події в теорії автоматів. Числення Поста виявились дуже зручними для зведення їх до різноманітних алгоритмічних проблем дискретної математики та теоретичної кібернетики. Тим самим була доведена алгоритмічна нерозв'язність цілого ряду проблем, наприклад проблема тотожності слів в напівгрупах, проблема розпізнавання повноти для скінченних автоматів тощо. Джерела інформації
Див. також
|
Portal di Ensiklopedia Dunia