ПОСТ ЭМИЛЬ ЛЕОН
11 февраля 1897, Августов, Польша — 21 апреля 1954, Нью-Йорк
американский логик и математик.
В 1920 получил степень доктора философии в Колумбийском университете.Читал лекции по математике и логике в этом университете и в колледже НьюЙорка.
Профессор колледжа с 1938. В диссертации, опубликованной в 1921,
Пост изложил метод оценки пропозициональных формул посредством истинностных таблиц.
В ней впервые получен ряд фундаментальных результатов в металогике для классической логики высказываний: непротиворечивость, дедуктивная полнота, разрешимость, функциональная полнота.
.
После двадцати лет работы опубликовано полное описание решетки замкнутых классов, каждый класс строится эффективно, и показано,
что каждый замкнутый класс имеет конечный базис. Эти классы названы классами Поста. Впервые определен критерий функциональной полноты, применяемый сейчас для произвольного множества функций многозначной логики.
Алгебраический эквивалент многозначным логикам Поста получил название “алгебр Поста”,
которые интенсивно развиваются уже на протяжении полувека. В 1936 независимо от работ Тьюринга, уточнено понятие алгоритма и компьютерной программы. Пост входит в четверку великих ученых, практически одновременно осознавших возможность уточнения общего представления об алгоритме.
Машина Поста
Среда — бесконечная информационная лента, разделенная на позиции (клетки). В каждой клетке может либо стоять метка (будем обозначать ее жирной точкой: •) либо — пусто. Вдоль ленты движется каретка. Она может передвигаться шагами; один шаг — смещение на одну клетку вправо или влево. Клетку, у которой установлена каретка будем называть текущей.
Назначение исполнителя: преобразование записи на информационной ленте.
Данные: определенная расстановка меток в позициях информационной ленты.
Действия исполнителя: с помощью каретки машина Поста может:
— распознать, клетка пустая или помеченная;
— стереть метку в текущей клетке;
— поставить метку в пустую текущую клетку.
Система команд исполнителя: (везде буква п обозначает номер текущей команды):
Выполните самостоятельно:
Комментариев нет:
Отправить комментарий