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

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

Визначення

Численням Поста називається четвірка виду ${\mathfrak {R}}=\left\langle A,{\mathfrak {A}},P,\pi \right\rangle$, де:

$A$

алфавіт числення,

${\mathfrak {A}}$

список слів в алфавіті A, що називається аксіомами,

$P$

алфавіт змінних, при чому $A\cap P=\emptyset$

$\pi$

список правил виведення.

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

$G_{1,1}p_{1,1}G_{1,2}p_{1,2}\dots G_{1,n}p_{1,n}G_{1,n+1}\,$

$G_{2,1}p_{2,1}G_{2,2}p_{2,2}\dots G_{2,n}p_{2,n}G_{2,n+1}\,$

$G_{m,1}p_{m,1}G_{m,2}p_{m,2}\dots G_{m,n}p_{m,n}G_{m,n+1} \over G_{1}p_{1}G_{2}p_{2}\dots G_{n}p_{n}G_{n+1}$

де

$G_{i,j}(1\leq i\leq m,1\leq n_{i}+1)$ та $G_{k}(1\leq k\leq n+1)$

деякі конкретні слова в алфавіті A,

$p_{i,j}(1\leq i\leq m,1\leq j\leq n)$, $p_{k}(1\leq k\leq n)$

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

Слово Q називається виводимим із слів $Q_{1},\dots ,Q_{m}$ по описаному правилу, якщо для кожної змінної $p_{i,j}$ та $p_{k}$ знайдеться таке слово в алфавіті A, що, якщо підставити всі ці слова на місця входження цих змінних в описаному правилі, то отримаємо вираз виду:

${\begin{matrix}Q_{1}\\Q_{2}\\\vdots \\Q_{m}\end{matrix}}$

—

$Q\,$

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

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

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

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

$Qp \over Q_{1}p$,

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

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

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

• Енциклопедія кібернетики, т. 2, с. 188.

Див. також

• Алгоритм
• Теорія алгоритмів
• Машина Тюринга
• Нормальні алгоритми Маркова.
• Повноти проблема в теорії автоматів.