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

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

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

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

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

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

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

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

Кроме ленты, имеется головка чтения/записи, которая: - умеет двигаться вперед, назад и стоять на месте;

– умеет читать содержимое, стирать и записывать метку;

– управляется программой, в которую могут входить в любой комбинации и любом количестве шесть команд:

1) Вправо

2) Влево

3) Поставить метку

4) Стереть метку

5) Передачи управления на один номер команды в программе, если в текущей ячейке есть метка; если метки нет, то передача управления на другой номер команды

6) Прекращения работы

Состояние машины – это состояние ленты и положение головки чтения/записи.

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

Машина Поста – это модель компьютера.

Машина решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима.

Машина Поста и машина Тьюринга эквивалентны по своим возможностям. Разработаны практически в одно и то же время (в 1936 г.) независимо друг от друга.

Можно ли любой алгоритм представить в форме машины Поста? Ответ на этот вопрос дается в виде так называемого тезиса Поста: всякий алгоритм представим в форме машины Поста. Это тезис потому, что его невозможно доказать, так как в нем фигурируют с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны – точное понятие «машина Поста».