Пост Эмиль Леон

Первые многозначные логики построили независимо друг от друга польский логик Я. Лукасевич в 1920 г. и американский логик Э. Пост в 1921 г. С тех пор построены и исследованы десятки и сотни таких «логик».

Пост (Post) Эмиль Леон (11.2.1897 — 21.04.1954) — американский математик и логик. Читал лекции по математике и логике в Колумбийском, Нью-йоркском и других университетах США. Им получен ряд фундаментальных результатов в математической логике: одно из наиболее употребительных определений понятий непротиворечивости и полноты формальных систем (исчислений); доказательства функциональной полноты и дедуктивной полноты (в широком и узком смысле) исчисления высказываний; изучение систем многозначной логики с более чем 3 значениями истинности; одно из первых (независимо от Тьюринга) определений понятия алгоритма в терминах «абстрактной вычислительной машины» и формулировка основного тезиса теории алгоритмов о возможности описать любой конкретный алгоритм посредством этого определения; результаты о выразимости общерекурсивных функций и предикатов через примитивно рекурсивные, в частности так называемая теорема о нормальной форме; первые (одновременно с А.А.Марковым) доказательства алгоритмической неразрешимости ряда проблем математической логики и алгебры.

Э. Пост подходил к построению многозначных логик чисто формально. Пусть 1 означает истину, а 0 — ложь. Естественно допустить тогда, что числа между единицей и нулем обозначают какие-то уменьшающиеся к нулю степени истины.

Такой подход вполне правомерен на первом этапе. Но чтобы построение логической системы перестало быть чисто техническим упражнением, а сама система — сугубо формальной конструкцией, в дальнейшем необходимо, конечно, придать ее символам определенный логический смысл, содержательно ясную интерпретацию. Вопрос о такой интерпретации — это как раз самая сложная и спорная проблема многозначной логики. Как только между истиной и ложью допускается что-то промежуточное, встает вопрос: что, собственно, означают высказывания, не относящиеся ни к истинным, ни к ложным? Кроме того, введение промежуточных степеней истины изменяет обычный смысл самих понятий истины и лжи. Приходится поэтому не только придавать смысл промежуточным степеням, но и переистолковывать сами понятия истины и лжи.

Машина Поста — математическое построение, предназначенное для уточнения понятия алгоритма.

Машиной называется потому, что при построении используются некоторые понятия реальных машин — память, команда, и пр.

Машина Поста состоит из неограниченной в обе стороны ленты, разделенной на ячейки, которые последовательно пронумерованы целыми числами, как положительными, так и отрицательными. В каждой ячейке ленты стоит либо признак того, что в ячейке записана метка, либо ячейка пустая. Состояние ленты — это данные о том, какие ячейки заняты, а какие пусты.