ПОСТА КОМБИНАТОРНАЯ ПРОБЛЕМА

— массовая проблема, заключающая в распознавании свойства сочетаемости списков. П. к. п. сформулировал и доказал ее алгоритм, неразрешимость амер. математик Э. Пост (1897— 1954). Списком наз. любой конечный упорядоченный набор конечных слов в некотором алфавите. Два списка: состоящие из одинакового числа слов, наз. сочетаемыми, если найдется хотя бы одна последовательность индексов для которой совпадают слова полученные приписыванием друг к другу соответствующих слов.

П. к. п. является примером неразрешимой алгоритмической проблемы, если алфавит содержит более одной буквы, т. е. не существует алгоритма, позволяющего для любой пары списков узнать, сочетаемы иди нет эти списки. Оказывается неразрешимой даже более узкая массовая проблема, заключающаяся в распознавании сочетаемости списков, содержащих фиксированное число слов (напр., если только это число не меньше 88). Алгоритм, неразрешимость многих массовых проблем в автоматов теории, в лингвистике математической и в некоторых др. разделах теоретической кибернетики была доказана методом сведения П. к. п. к этим массовым проблемам.

Лит.: Марков А. А. Теория алгорифмов. «Труды Математического института им. В. А. Стеклова АН СССР», 1954, т. 42 [библиогр. с. 373—374]; Post Е. L. A variant of a recursively unsolvable problem. «Bulletin of the American Mathematical Society», 1946. v. 52, Ka 4. Г. С? Плесневич.