Числення Поста

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Числення Поста — клас числень, який запропонував американський математик Еміль Пост. Числення Поста можна розглядати як математичне уточнення інтуїтивного поняття алгоритму.

Визначення

[ред. | ред. код]

Численням Поста називається четвірка виду , де:

алфавіт числення,
список слів в алфавіті A, що називається аксіомами,
алфавіт змінних, при чому
список правил виведення.

Список правил виведення має вигляд:

де

та
деякі конкретні слова в алфавіті A,
,
деякі (не обов'язкові відмінні між собою) літери алфавіту P.

Слово Q називається виводимим із слів по описаному правилу, якщо для кожної змінної та знайдеться таке слово в алфавіті A, що, якщо підставити всі ці слова на місця входження цих змінних в описаному правилі, то отримаємо вираз виду:

 —

Список слів називається виводом в численні , якщо кожне його слово є або аксіомою, або виводимо із попередніх слів по одному із правил виведення. Слово D називається виводимим в численні , якщо існує вивід, останнім словом якого є слово D.

Властивості числення Поста

[ред. | ред. код]

Доведено, що будь-яку рекурсивно перелічену множину слів в алфавіті A можна отримати як множину виводимих слів у спеціально підібраному численні Поста, що має лише скінченну кількість аксіом та правил виведення. Еміль Пост довів, що такий самий результат справедливий для більш вузького класу числень, так званих нормальних канонічних числень, всі правила яких мають вигляд .

Разом з тим, числення Поста, які мають правила виводу

,

породжують лише регулярні події в теорії автоматів.

Числення Поста виявились дуже зручними для зведення їх до різноманітних алгоритмічних проблем дискретної математики та теоретичної кібернетики. Тим самим була доведена алгоритмічна нерозв'язність цілого ряду проблем, наприклад проблема тотожності слів в напівгрупах, проблема розпізнавання повноти для скінченних автоматів тощо.

Джерела інформації

[ред. | ред. код]

Див. також

[ред. | ред. код]