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

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

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

Визначення[ред.ред. код]

Численням Поста називається четвірка виду \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 \le i \le m, 1 \le n_i + 1) та G_k (1 \le k \le n + 1) 
деякі конкретні слова в алфавіті A,
 p_{i,j} (1 \le i \le m, 1 \le j \leq n), p_k (1 \le  k \le 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 /p Q_1.

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

Qp \over Q_1p,

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

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

Джерела інформації[ред.ред. код]

Див. також[ред.ред. код]