Помощь по Теле2, тарифы, вопросы

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

Пост Эмиль Леон (Post Emil Leon) (11 февраля 1897, Августов, Польша – 21 апреля 1954, Нью-Йорк) – американский логик и математик. В 1920 году получил степень доктора философии в Колумбийском университете. Читал лекции по математике и логике в этом университете и в колледже Нью-Йорка. Профессор колледжа с 1938 года. В диссертации, опубликованной в 1921 году, Пост изложил метод оценки пропозициональных формул посредством истинностных таблиц. В ней впервые получен ряд фундаментальных результатов в металогике для классической логики высказываний : непротиворечивость, дедуктивная полнота, разрешимость, функциональная полнота. В этой работе впервые построена многозначная логика более чем с 3 истинностными значениями и с произвольным числом выделенных значений. Здесь же установлено, что множество замкнутых классов в классической логике счетно. После двадцати лет работы опубликовано полное описание решетки замкнутых классов, каждый класс строится эффективно, и показано, что каждый замкнутый класс имеет конечный базис. Эти классы названы классами Поста. Впервые определен критерий функциональной полноты, применяемый сейчас для произвольного множества функций многозначной логики. Алгебраический эквивалент многозначным логикам Поста получил название «алгебр Поста», которые интенсивно развиваются уже на протяжении полувека. В 1936 году независимо от работ Тьюринга, Чёрча и Клини уточнено понятие алгоритма в терминах, как бы сегодня сказали, компьютерной программы. Таким образом, Пост входит в четверку великих ученых, практически одновременно осознавших возможность уточнения общего представления об алгоритме. В 1943 году Постом было впервые предложено общее понятие исчисления, имеющее фундаментальное значение для доказательства неразрешимости ряда проблем математики. В 1944 году публикуется, по-видимому, наиболее влиятельная работа Поста, где в первоначальном виде излагается теория степеней неразрешимости, а в 1947 году впервые в истории математики (независимо от А.А. Маркова ) был указан пример «внутриматематической» неразрешимой массовой алгоритмической проблемы, а именно проблемы А Туэ (проблема равенства для полугрупп). Пост считал – и писал об этом К. Гёделю , – что за 15 лет до революционных гёделевских работ о неполноте, он уже имел эти теоремы, хотя и не в такой законченной форме.

А.С. Карпенко

Новая философская энциклопедия. В четырех томах. / Ин-т философии РАН. Научно-ред. совет: В.С. Степин, А.А. Гусейнов, Г.Ю. Семигин. М., Мысль, 2010, т. III, Н – С, с. 292-293.

Далее читайте:

Философы, любители мудрости (биографический указатель).

Исторические лица США (биографический указатель).

Сочинения:

Introduction to a general theory of elementary propositions. – «American Journal of Mathematics», 1921, v. 43, № 3 (Переиздано: From Frege to Godel. Cambr. (Mass.), 1967;

Finite combinatory processes – formulation I. – «The Journal of Symbolic Logic», 1936, v. 1 (рус. пер. в кн.: Успенский В.А. Машины Поста. М., 1979);

Two-valued iterative systems. – «Annals of Mathematical Studies», 1941, v. 5;

Formal reductions of the general combinatorial decision problem. – «American Journal of Mathematics», 1943, v. 65;

Recursively enumerable sets of positive integers and their decision problems. – «Bull. Amer. Math. Soc», v. 50, 1944 (Переиздано: The Undecidable, ed. M.Davis. N. Y., 1965);

Recursive unsovability of a problem of Thue. – «The Journal of Symbolic Logic», v. 12, 1947 (Переиздано: The Undecidable... 1965).

Литература:

Клини С.К. Введение в метаматематику. М., 1957;

Мальцев А.И. Итеративные алгебры Поста. Новосибирск, 1976;

Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.;

Davis M. Emil Post"s contributions to computer science. – Proceedings Fourth Annual Symposium on Logic in Computer Science. Washington, 1989;

Dwinger Ph. A survey of the theory of Post algebras and their generalizations. – Modern uses of multiple-valued logic. Dordrecht, 1977.

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

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

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

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

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

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

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

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

›

Эмиль Леон Пост (англ. Post Emil Leon , 11 февраля 1897, Августов, Царство Польское (ныне Польша) - 21 апреля 1954, Нью-Йорк) - американский математик и логик; один из основателей многозначной логики (1921); основные труды по математической логике: алгебра Поста , классы Поста функций алгебры логики; предложил абстрактную вычислительную машину - машину Поста.

Биография

Эмиль Леон Пост родился в ортодоксальной еврейской семье, проживавшей недалеко от Белостока. В 1897 году его отец Арнольд эмигрировал в Соединенные Штаты. Когда у отца наладились дела, семья (семилетний Эмиль, его две сестры и мать) тоже переехала с Царской России в Нью-Йорк. Семья жила в комфортабельном доме в Гарлеме.

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

В 1921 году Эмиль Пост защитил докторскую диссертацию в области математики в Колумбийском университете. В диссертации он изложил метод оценки пропозициональных формул с помощью таблиц истинности. В ней впервые получен ряд фундаментальных результатов в металогике для классической логики высказываний: непротиворечивость, дедуктивная полнота, развязность, функциональная полнота. В этой работе впервые построена многозначная логика более чем 3 истинными значениями и с произвольным количеством выделенных значений. Здесь же установлено, что множество замкнутых классов в классической логике счетное.

1920-1921 учебный год Пост провел на постдокторских студиях в Принстонском университете. Именно здесь у него случился первый приступ маниакально-депрессивного психоза. Эта болезнь сопровождала Поста течение всей его жизни. Он достаточно восстановился после этого первого нападения и получил должность преподавателя в Корнельском университете, однако второе нападение заставил его прекратить преподавание в Университете. В 20-х годах Эмиль Пост зарабатывал на жизнь преподавая математику в George Washington High School в Нью-Йорке. Со своим врачом Пост разработал режим, который был назначен с целью исключить посторонние возбуждения, которые вели к нападениям психоза. Режим позволял Посту заниматься наукой и исследованиями всего 3 часа в день.

Несмотря на такой режим и большое учебную нагрузку (16 часов в неделю) Пост смог в этот период опубликовать свои влиятельные труды. Его брак с Гертрудой Сингер в 1929 несомненно поспособствовал стабильности его жизни. Жена ассистировала Эмилю, печатая его статьи и письма, а также занималась ежедневными финансами семьи.

В 1932 году Эмиль Пост был назначен на факультет математики Сити Колледжа в Нью-Йорке. Проработав месяц, он оставил должность, однако, вернулся в 1935 году, и оставался на посту до самой смерти в 1954 году от сердечного приступа во время электрошока.

Эмиль Пост входит в четверку великих ученых, которые практически одновременно осознали возможность уточнения общего представления об алгоритме. В 1943 Постом было впервые предложено общее понятие вычисления, которое имеет фундаментальное значение для доказательства неразрешимости ряда проблем математики. В 1944 публикуется, пожалуй, самая влиятельная работа Поста, где в первоначальном виде излагается теория степеней неразрешимости, а в 1947 впервые в истории математики (независимо от А Маркова) был приведен пример «внутриматематической» неразрешимой массовой алгоритмической проблемы, а именно проблемы А. Туэ (проблема равенства для полугрупп). Пост считал - и писал об этом Курту Геделю, - что за 15 лет до революционных геделевських работ о неполноте, у него уже имелись эти теоремы, хотя и не в такой завершенной форме.

Дальнейшее чтение

• Davis, Martin (1993). The Undecidable (Ed.), pp. 288–406. Dover. ISBN 0-486-43228-9. Reprints several papers by Post.
• Davis, Martin (1994). «Emil L. Post: His Life and Work» in Davis, M., ed., Solvability, Provability, Definability: The Collected Works of Emil L. Post . Birkhäuser: xi-xxviii. A biographical essay.

См. также

• Машина Поста
• Критерий Поста

Частично использовались материалы сайта http://ru.wikipedia.org/wiki/

, Царство Польское

Биография

Эмиль Леон Пост родился в ортодоксальной еврейской семье, проживавшей недалеко от Белостока. В 1897 году его отец Арнольд эмигрировал в Соединенные Штаты. Когда у отца наладились дела, семья (семилетний Эмиль, его две сестры и мать) тоже переехала из Царской России в Нью-Йорк. Семья жила в комфортабельном доме в Гарлеме.

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

В 1921 году Эмиль Пост защитил докторскую диссертацию в области математики в Колумбийском университете. В диссертации он изложил метод оценки пропозициональных формул с помощью таблиц истинности. В ней впервые получен ряд фундаментальных результатов в металогике для классической логики высказываний: непротиворечивость, дедуктивная полнота, развязность, функциональная полнота. В этой работе впервые построена многозначная логика более чем 3 истинными значениями и с произвольным количеством выделенных значений. Здесь же установлено, что множество замкнутых классов в классической логике счетное.

1920-1921 учебный год Пост провел на постдокторских студиях в Принстонском университете. Именно здесь у него случился первый приступ маниакально-депрессивного психоза. Эта болезнь сопровождала Поста течение всей его жизни. Он достаточно восстановился после этого первого нападения и получил должность преподавателя в Корнельском университете, однако второе нападение заставило его прекратить преподавание в Университете. В 20-х годах Эмиль Пост зарабатывал на жизнь преподавая математику в George Washington High School в Нью-Йорке. Со своим врачом Пост разработал режим, который был назначен с целью исключить посторонние возбуждения, которые вели к нападениям психоза. Режим позволял Посту заниматься наукой и исследованиями всего 3 часа в день.

Несмотря на такой режим и большое учебную нагрузку (16 часов в неделю) Пост смог в этот период опубликовать свои влиятельные труды. Его брак с Гертрудой Сингер в 1929 несомненно поспособствовал стабильности его жизни. Жена ассистировала Эмилю, печатая его статьи и письма, а также занималась ежедневными финансами семьи.

В 1932 году Эмиль Пост был назначен на факультет математики Сити Колледжа в Нью-Йорке. Проработав месяц, он оставил должность, однако, вернулся в 1935 году, и оставался на посту до самой смерти в 1954 году от сердечного приступа во время электрошока.

Эмиль Пост входит в четверку великих ученых, которые практически одновременно осознали возможность уточнения общего представления об алгоритме. В 1943 Постом было впервые предложено общее понятие вычисления, которое имеет фундаментальное значение для доказательства неразрешимости ряда проблем математики. В 1944 публикуется, пожалуй, самая влиятельная работа Поста, где в первоначальном виде излагается теория степеней неразрешимости, а в 1947 впервые в истории математики (независимо от А Маркова) был приведен пример «внутриматематической» неразрешимой массовой алгоритмической проблемы, а именно проблемы А. Туэ (проблема равенства для полугрупп). Пост считал - и писал об этом Курту Геделю, - что за 15 лет до революционных геделевских работ о неполноте, у него уже имелись эти теоремы, хотя и не в такой завершенной форме.

Дальнейшее чтение

• Davis, Martin (1993). The Undecidable (Ed.), pp. 288–406. Dover. ISBN 0-486-43228-9 . Reprints several papers by Post.
• Davis, Martin (1994). «Emil L. Post: His Life and Work» in Davis, M., ed., Solvability, Provability, Definability: The Collected Works of Emil L. Post . Birkhäuser: xi-xxviii. A biographical essay.

См. также

Напишите отзыв о статье "Пост, Эмиль Леон"

Примечания

Ссылки

• Джон Дж. О’Коннор и Эдмунд Ф. Робертсон . (англ.) - биография в архиве MacTutor .

Отрывок, характеризующий Пост, Эмиль Леон

– Не глупее тебя, матушка, – сказал девятилетний Петя, точно как будто он был старый бригадир.
Графиня была приготовлена намеками Анны Михайловны во время обеда. Уйдя к себе, она, сидя на кресле, не спускала глаз с миниатюрного портрета сына, вделанного в табакерке, и слезы навертывались ей на глаза. Анна Михайловна с письмом на цыпочках подошла к комнате графини и остановилась.
– Не входите, – сказала она старому графу, шедшему за ней, – после, – и затворила за собой дверь.
Граф приложил ухо к замку и стал слушать.
Сначала он слышал звуки равнодушных речей, потом один звук голоса Анны Михайловны, говорившей длинную речь, потом вскрик, потом молчание, потом опять оба голоса вместе говорили с радостными интонациями, и потом шаги, и Анна Михайловна отворила ему дверь. На лице Анны Михайловны было гордое выражение оператора, окончившего трудную ампутацию и вводящего публику для того, чтоб она могла оценить его искусство.
– C"est fait! [Дело сделано!] – сказала она графу, торжественным жестом указывая на графиню, которая держала в одной руке табакерку с портретом, в другой – письмо и прижимала губы то к тому, то к другому.
Увидав графа, она протянула к нему руки, обняла его лысую голову и через лысую голову опять посмотрела на письмо и портрет и опять для того, чтобы прижать их к губам, слегка оттолкнула лысую голову. Вера, Наташа, Соня и Петя вошли в комнату, и началось чтение. В письме был кратко описан поход и два сражения, в которых участвовал Николушка, производство в офицеры и сказано, что он целует руки maman и papa, прося их благословения, и целует Веру, Наташу, Петю. Кроме того он кланяется m r Шелингу, и m mе Шос и няне, и, кроме того, просит поцеловать дорогую Соню, которую он всё так же любит и о которой всё так же вспоминает. Услыхав это, Соня покраснела так, что слезы выступили ей на глаза. И, не в силах выдержать обратившиеся на нее взгляды, она побежала в залу, разбежалась, закружилась и, раздув баллоном платье свое, раскрасневшаяся и улыбающаяся, села на пол. Графиня плакала.
– О чем же вы плачете, maman? – сказала Вера. – По всему, что он пишет, надо радоваться, а не плакать.
Это было совершенно справедливо, но и граф, и графиня, и Наташа – все с упреком посмотрели на нее. «И в кого она такая вышла!» подумала графиня.
Письмо Николушки было прочитано сотни раз, и те, которые считались достойными его слушать, должны были приходить к графине, которая не выпускала его из рук. Приходили гувернеры, няни, Митенька, некоторые знакомые, и графиня перечитывала письмо всякий раз с новым наслаждением и всякий раз открывала по этому письму новые добродетели в своем Николушке. Как странно, необычайно, радостно ей было, что сын ее – тот сын, который чуть заметно крошечными членами шевелился в ней самой 20 лет тому назад, тот сын, за которого она ссорилась с баловником графом, тот сын, который выучился говорить прежде: «груша», а потом «баба», что этот сын теперь там, в чужой земле, в чужой среде, мужественный воин, один, без помощи и руководства, делает там какое то свое мужское дело. Весь всемирный вековой опыт, указывающий на то, что дети незаметным путем от колыбели делаются мужами, не существовал для графини. Возмужание ее сына в каждой поре возмужания было для нее так же необычайно, как бы и не было никогда миллионов миллионов людей, точно так же возмужавших. Как не верилось 20 лет тому назад, чтобы то маленькое существо, которое жило где то там у ней под сердцем, закричало бы и стало сосать грудь и стало бы говорить, так и теперь не верилось ей, что это же существо могло быть тем сильным, храбрым мужчиной, образцом сыновей и людей, которым он был теперь, судя по этому письму.
– Что за штиль, как он описывает мило! – говорила она, читая описательную часть письма. – И что за душа! Об себе ничего… ничего! О каком то Денисове, а сам, верно, храбрее их всех. Ничего не пишет о своих страданиях. Что за сердце! Как я узнаю его! И как вспомнил всех! Никого не забыл. Я всегда, всегда говорила, еще когда он вот какой был, я всегда говорила…
Более недели готовились, писались брульоны и переписывались набело письма к Николушке от всего дома; под наблюдением графини и заботливостью графа собирались нужные вещицы и деньги для обмундирования и обзаведения вновь произведенного офицера. Анна Михайловна, практическая женщина, сумела устроить себе и своему сыну протекцию в армии даже и для переписки. Она имела случай посылать свои письма к великому князю Константину Павловичу, который командовал гвардией. Ростовы предполагали, что русская гвардия за границей, есть совершенно определительный адрес, и что ежели письмо дойдет до великого князя, командовавшего гвардией, то нет причины, чтобы оно не дошло до Павлоградского полка, который должен быть там же поблизости; и потому решено было отослать письма и деньги через курьера великого князя к Борису, и Борис уже должен был доставить их к Николушке. Письма были от старого графа, от графини, от Пети, от Веры, от Наташи, от Сони и, наконец, 6 000 денег на обмундировку и различные вещи, которые граф посылал сыну.

Post Emu Leon) (11 февраля 1897, Августов, Польша - 21 апреля 1954, Нью-Йорк) - американский логик и математик. В 1920 получил степень доктора философии в Колумбийском университете. Читал лекции по математике и логике в этом университете и в колледже НьюЙорка. Профессор колледжа с 1938. В диссертации, опубликованной в 1921, Пост изложил метод оценки пропозициональных формул посредством истинностных таблиц. В ней впервые получен ряд фундаментальных результатов в металогике для классической логики высказываний: непротиворечивость, дедуктивная полнота, разрешимость, функциональная полнота. В этой работе впервые построена многозначная логика более чем с 3 истинностными значениями и с произвольным числом выделенных значений. Здесь же установлено, что множество замкнутых классов в классической логике счетно. После двадцати лет работы опубликовано полное описание решетки замкнутых классов, каждый класс строится эффективно, и показано, что каждый замкнутый класс имеет конечный базис. Эти классы названы классами Поста. Впервые определен критерий функциональной полноты, применяемый сейчас для произвольного множества функций многозначной логики. Алгебраический эквивалент многозначным логикам Поста получил название «алгебр Поста», которые интенсивно развиваются уже на протяжении полувека. В 1936 независимо от работ Тьюринга, Черча и Клини уточнено понятие алгоритма в терминах, как бы сегодня сказали, компьютерной программы. Т. о., Пост входит в четверку великих ученых, практически одновременно осознавших возможность уточнения общего представления об алгоритме. В 1943 Постом было впервые предложено общее понятие исчисления, имеющее фундаментальное значение для доказательства неразрешимости ряда проблем математики. В 1944 публикуется, по-видимому, наиболее влиятельная работа Поста, где в первоначальном виде излагается теория степеней неразрешимости, а в 1947 впервые в истории математики (независимо от А А. Маркова) был указан пример «внутриматематической» неразрешимой массовой алгоритмической проблемы, а именно проблемы А. Туэ (проблема равенства для полугрупп). Пост считал - и писал об этом К. Геделю, - что за 15 лет до революционных геделевских работ о неполноте, он уже имел эти теоремы, хотя и не в такой законченной форме.

Соч.: Introduction to a general theory of elementary propositions.- «American Journal of Mathematics», 1921, v. 43, № 3 (Переиздано: From Frege to Godel. Cambr. (Mass.), 1967; Finite combinatory processes - formulation I.- «The Journal of Symbolic Logic», 1936, v. (рус. пер. в кн.: Успенский В. А. Машины Поста. М., 1979); Two-valued iterative systems.- «Annals of Mathematical Studies», 1941, v. 5; Formal reductions of the general combinatorial decision problem.- «American Journal of Mathematics», 1943, v. 65; Recursively enumerable sets of positive integers and their decision problems.- «Bull. Amer. Math. Soe», v. 50, 1944 (Переиздано: The Undecidable, ed. M. Davis. N. Y, 1965); Recursive unsovability of a problem ofThue.- «The Journal of Symbolic Logic», v. 12, 1947 (Переиздано: The Undecidable... 1965)

Лит.: Кдини С. К. Введение в метаматематику. М., 1957; Мальцев А. И. .Итеративные алгебры Поста. Новосибирск, 1976; Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. M.; Davis M. Emil Posts conlributions to computer science.- Proceedings Fourth Annual Symposium on Logic in Computer Science. Wishington, 1989; Dwinger Ph. A survey of the theory of Post algebras and their generalizations.- Modern uses of multiple-valued logic. Dordrecht, 1977.