Э пост краткое сообщение

Обновлено: 05.07.2024

ПОСТ ЭМИЛЬ ЛЕОН (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 Post's 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.

Новая философская энциклопедия: В 4 тт. М.: Мысль . Под редакцией В. С. Стёпина . 2001 .

Эмиль Пост родился на территории Российской империи в 1897 году городе Августов, который сейчас находится в Польше.

С юных лет Пост увлекался математикой и уже в 23 года становится доктором в Колумбийском университете. Его считают одним из отцов многозначной логики, а самым известным его изобретением, прославившим ученого, стала абстрактная вычислительная машина, получившая его имя. Вычислительная машина Поста была создана в один год с машиной Тьюринга, но чуть позже. Она также предназначалась для уточнения понятия алгоритма и алгоритмической разрешимости.

Пост считается одним из четырех столпов теории алгоритма и стоял у истоков современной вычислительной техники.

Кто такой Эмиль Пост и чем известен?

Эмиль Леон Пост — российский верноподданный, родившийся в конце 19 века на территории современной Польши, тогда входившей в состав Российской империи. За свои 57 лет (1897-1954) он прославился открытиями в области математики и логики. Его работы прежде всего посвящены изучению закономерностей в сформировавшейся уже позднее теории исчисляемости.

Поскольку Эмиль был из польских евреев, его родители покинули родную гавань и уплыли за океан. В мае 1904 года они обосновались в США. Самым первым его увлечением была астрономия.

Однако из-за трагедии в автомобильной катастрофе, которая стоила Эмилю левой руки, юный гений стал больше погружаться в математику. Уже в 1920 году он защитил докторскую по математике в Колумбийском университете, а позднее пост-докторскую в Принстонском. С 1936 года работал на факультете математики Нью-Йоркского Городского университета. В браке с Гертрудой Сингер родилась дочь.

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

Прославился Эмиль Пост своими открытиями в области математики. Он основал многозначную математическую логиику. Именем изобретателя названа алгебра Поста, абстрактная вычислительная машина Поста. Также он уточнил понятие алгоритма.

Эмиль Леон Пост (англ. Post Emil Leon ) — американский математик, философ, логик, профессор, специалист в области информатики, один из основателей многозначной логики [1] .

Родился 11 февраля 1897 года в Августове, Царство Польское, в ортодоксальной еврейской семье, проживавшей недалеко от Белостока.

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

В детском возрасте увлёкся астрономией. В 12 лет потерял левую руку. Затем решил заняться математикой. Окончил Townsend Harris High School.

В 1917 году получил степень бакалавра по математике в Городском колледже Нью-Йорка‎.

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

1920—1921 учебный год провёл на постдокторских студиях в Принстонском университете, где у него случился первый приступ маниакально-депрессивного психоза. Эта болезнь сопровождала учёного в течение всей его жизни. Постдостаточно восстановился после этого первого нападения и получил должность преподавателя в Корнелльском университете, однако второе нападение заставило его прекратить преподавание в Университете.

В 1920-е годы преподавал математику в George Washington High School в Нью-Йорке.

В 1929 году женился на Гертруде Сингер, которая ассистировала ему, печатая его статьи и письма, и занималась ежедневными финансами семьи.

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

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

В 1943 году впервые предложил общее понятие вычисления, которое имеет фундаментальное значение для доказательства неразрешимости ряда проблем математики.

В 1944 году опубликовал свою самую влиятельную работу, в которой в первоначальном виде излагается теория степеней неразрешимости.

Вы можете поделиться своими знаниями, улучшив их ( как? ) Согласно рекомендациям соответствующих проектов .

Ознакомьтесь со списком задач, которые необходимо выполнить, на странице обсуждения .

Кладбище на горе Хеврон ( in )

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

Townsend Harris High School ( in ) (до 1913 г. )
Колумбийский университет ( 1917 г. - 1920 г. )
Городской колледж Нью-Йорка (до 1917 г. )

Принстонский университет ( 1920 г. - 1921 г. ) , Колумбийский университет ( 1921 г. - 1924 г. ) , Корнельский университет ( 1924 г. - 1927 г. ) , Средняя школа Джорджа Вашингтона ( en ) ( 1927 г. - 1932 г. ) , Городской колледж Нью-Йорка ( 1932 г. - 1954 г. )

Библиотека Американского философского общества ( d ) (г-жа Колл 45)

Проблема Пост-корреспонденции , формула обращения Поста ( d ) , решетка Поста ( d ) , теорема Поста , каноническая система Поста

Эмиль Леон Пост (родился 11 февраля 1897 г. в Августове и умерла 21 апреля 1954 г. в Нью-Йорке) - американский математик, родившийся на территории современной Польши в еврейской семье . Он является источником проблем с перепиской Поста .

Он также опубликовал в 1921 г. исчерпывающее исследование клонов двухэлементных алгебр.

Резюме

биография

Эмиль Пост родился в Польше в 1897 году под именем Поставельский, в 1904 году эмигрировал с семьей в США, где его имя было американизировано.

Ему ампутировали левую руку в 13 лет после автомобильной аварии. Он не будет вспоминать это событие на протяжении всей своей жизни и всегда позирует на фото, чтобы мы не видели пропавшую руку.

Блестящий студент, он защитил диссертацию в Колумбийском университете в 1920 году, а на следующий год начал свои исследования в области логики в Принстоне благодаря стипендии.

Он пережил кризис в 1921 году, затем второй кризис в 1924 году, из-за которого он не занимался логикой до 1936 года, когда он вернулся к работе в ограниченное время.

Он умер 21 апреля 1954 года после лечения электрошоком, он был интернирован с прошлого лета.

Работа над исчислением высказываний

В своем введении к общей теории элементарных предложений в 1921 году, он устанавливает смысловую полноту в исчислении высказываний в Principia Mathematica из Уайтхеда и Рассела по системе таблиц истинности . Затем он обобщает этот результат на любое конечно-валентное исчисление высказываний (а не только на двухвалентное ).

Проблема с перепиской поста

Начнем с двух конечных последовательностей U и V, содержащих одинаковое количество конечных слов в любом алфавите. Например

ты 1 знак равно в б в , ты 2 знак равно б , ты 3 знак равно в , ты 4 знак равно в б а также v 1 знак равно в , v 2 знак равно б , v 3 знак равно в б в б в , v 4 знак равно б = aba, u_ = b, u_ = a, u_ = ab \ qquad > \ qquad v_ = a, v_ < 2>= b, v_ = ababa, v_ = b ~> .

Мы ищем такую последовательность индексов , что конкатенация соответствует конкатенации . Здесь последовательность (1,2,3,2,1) является решением, поскольку я 1 , я 2 , . . . я нет , i_ , . i_ > ты я k >> v я k >>

ты 1 ты 2 ты 3 ты 2 ты 1 знак равно v 1 v 2 v 3 v 2 v 1 знак равно в б в б в б в б в u_ u_ u_ u_ = v_ v_ v_ v_ v_ = ababababa ~> .

Проблема соответствия поста (сокращенно PCP) состоит в том, чтобы определить, существует ли такая последовательность. Это неразрешимо : не существует общего алгоритма, способного дать ответ для произвольных U и V.

Читайте также: