波斯特Emil Leon Post

波斯特的父亲是弗拉基米尔·阿诺尔德 波斯特，母亲是Pearl 波斯特。阿诺尔德和Pearl是波兰犹太人，他们的儿子波斯特出生在俄罗斯控制的波兰，并在那里度过了生命的最初七年。1904年5月，全家为了寻求更好的生活移民到美国，并在纽约安家。

波斯特是一个异常聪明的孩子，但他的一生却充满了巨大的悲剧。童年时，他因事故失去了一条手臂，但他很好地应对了这一残疾。成年后，他不得不面对精神问题，这些问题对他产生了毁灭性的影响，相比之下，失去手臂的身体问题显得微不足道。

纽约为特别有天赋的儿童提供免费的中等教育。这所学校是Townsend Harris High School，与纽约市立学院位于同一地点。从高中毕业后，波斯特留在同一校园，继续在纽约市立学院学习。

我们现在把波斯特视为数学逻辑学家，但最初吸引他的学科是天文学。在纽约市立学院学习期间，他学习了数学，但几乎没有迹象表明在这个阶段他特别被逻辑所吸引。在学院读本科时，他写了第一篇论文，是关于广义微分的。他提出的问题非常引人入胜：当$n$不是整数时，微分算子$D^{n}$意味着什么？尽管是在本科期间写的，波斯特直到1923年才将论文提交给美国数学会，直到1930年才最终发表。这篇论文确实包含了一个非常重要的思想，因为在论文中波斯特证明了关于皮埃尔·西蒙·拉普拉斯变换求逆的一个重要结果。这篇出版物出现在波斯特获得第一个学位很久之后，那是他1917年由纽约市立学院授予的B.S.学位。

获得第一个学位后，波斯特开始在哥伦比亚大学进行研究生研究。对波斯特职业生涯具有重要意义的事件是伯特兰·罗素和阿尔弗雷德·诺思·怀特海的Principia Mathematica的出版。Principia Mathematica的第一卷于1910年出版，第二卷于1912年，第三卷于1913年。当波斯特开始他的研究生学习时，这是一个令人兴奋的新发展，波斯特参加了哥伦比亚大学Cassius J Keyser的研讨会，该研讨会研究Principia Mathematica。波斯特于1918年获得A.M.学位，1920年获得Ph.D.学位。他的博士论文是关于数学逻辑的，我们稍后会进一步讨论，但首先让我们注意到，波斯特作为研究生写了第二篇论文，这篇论文发表在他的第一篇论文之前，这是一篇关于伽马函数函数方程的短篇作品。

现在我们转向波斯特的博士论文，在论文中，他通过引入真值表方法，证明了Principia Mathematica中描述命题演算的完备性和一致性。然后，他将基于“真”和“假”两个值的真值表方法推广到具有任意有限个真值的方法。波斯特在论文中引入的最后一个，也许是最引人注目的新思想，是为逻辑系统提供了一个框架，作为基于符号有限操作过程的推理系统。波斯特提出的这种逻辑系统，用今天的术语来说，在有限字母表上产生了一个递归可枚举的词集。可以说，波斯特的论文标志着证明论的开端。

获得博士学位后，波斯特作为Proctor Fellow前往普林斯顿大学一年。他回到哥伦比亚大学，此后不久，他首次发作了一种疾病，这种疾病将在他整个职业生涯中反复出现，并限制了他可能取得的成就。正如马丁·戴维斯在[4]中所写：-

他整个成年生活都饱受严重的躁郁症折磨，而当时尚无药物治疗这种疾病。

1924年，波斯特去了康奈尔，但再次生病。1927年，他在纽约重新担任高中教师。1929年，他与Gertrude Singer结婚，育有一个孩子，女儿Phyllis。然后，在1932年，他被任命到城市学院。短暂工作一段时间后，他再次因精神疾病而离开，但三年后返回，并在那里度过了余生。在城市学院，他的教学工作量是每周16个接触小时，这使得寻找研究时间非常困难。此外，教职员工没有自己的办公室，而是全部被安排在一个中间有一张大桌子的房间里。波斯特选择在家工作，但有一个年幼的孩子，这给家庭带来了压力。波斯特的女儿Phyllis后来在她的一生中解释了Gertrude Post如何努力给丈夫机会投入时间进行研究：-

我的父亲是个天才；我的母亲是个圣人……除了打推荐信，我的母亲还打父亲的手稿和信件……我的母亲也是处理所有财务事务的人……她是日常生活中的缓冲，让我的父亲能够将注意力集中在数学上（以及他对当代世界事务的各种兴趣）。没有她，他能取得这么多成就吗？我个人认为不能。

波斯特在57岁时的早逝几乎可以肯定是他接受精神疾病治疗的一个直接后果。当时，这类躁郁症是用电击疗法治疗的。对于一种可怕的疾病来说，这是一种可怕的治疗方法，它给病人带来了极大的痛苦。这种疗法所依据的不过是这样一个事实：病人在接受这种治疗后，许多人有过一段精神状况较为正常的时期。波斯特多次接受电击治疗，而正是在一家精神病院中，在接受电击后不久，他突发心脏病去世。

波斯特最为人所知的是他在多值群、递归可枚举集和不可解度方面的工作，以及他对组合数学中问题不可解性的贡献。他在一篇关于真值表方法的论文中引入了完备性和一致性的概念，这篇论文是从他的学位论文工作发展而来的。他把这些方法归功于他在哥伦比亚大学的老师C J Keyser，而不是像以前那样归功于查尔斯·桑德斯·皮尔士和E 恩斯特·施勒德。20世纪20年代，波斯特证明了与库尔特·弗雷德里希·哥德尔、丘奇和艾伦·图灵后来发现的结果相似的结果，但他没有发表。他没有发表的原因是他觉得需要一种“完全的分析”才能获得认可。他写道：-

这个结果的正确性显然完全取决于导致上述推广的分析的可靠性……它在依赖⟦L1⟧的逻辑方面从根本上说是薄弱的……为了获得完全的普遍性，必须对人类心智能够建立生成序列的有限过程的所有可能方式给出完全的分析。

他还对扬·武卡谢维奇的三值逻辑进行了数学研究。大约在这个时候，他在日记中写道：-

我研究数学是把它当作人类心智的产物，而不是绝对的东西。

当库尔特·弗雷德里希·哥德尔在1931年发表他的不完备性定理时，波斯特意识到他等待发表自己已证明的结果太久了，现在全部功劳都将归于库尔特·弗雷德里希·哥德尔。在1938年写给库尔特·弗雷德里希·哥德尔的一张明信片中，就在他们第一次见面后不久，波斯特写道：-

……十五年来，我一直怀揣着用我的非正统思想震惊数学界的念头，而见到那个对这一梦想的破灭负主要责任的人，让我有些不能自已。既然你似乎对我如何得出这些新进展感兴趣，也许丘奇可以给你看我写给他的一封关于这些的长信。至于我可能提出的任何主张，也许我最多只能说，我本会在1921年证明库尔特·弗雷德里希·哥德尔定理——如果我是库尔特·弗雷德里希·哥德尔的话。

在他第二天写的一封后续信件中，他写道：-

……毕竟，构成伟大标志的不是思想，而是思想的执行。

1936年，他提出了现在所谓的波斯特机，一种自动机，其概念早于冯·诺伊曼在1946年研究的程序概念。1941年，他写道：-

……数学思维本质上是，也必须是，创造性的……

但他说存在局限性，而符号逻辑是：-

……揭示和发展这些局限性的无可争议的手段。

波斯特在1947年证明了半群的字问题递归不可解，从而解决了一个由阿克塞尔·图厄在1914年提出的问题。

威拉德·范奥曼·蒯因在1954年波斯特去世后写的一封信中说：-

现代证明论，以及同样地，现代机器计算理论，都依赖于递归函数的概念。这个重要的数论概念……由四位数学家独立发现……其中之一就是波斯特。随后波斯特的工作对递归函数理论的进一步发展起到了关键作用。

威拉德·范奥曼·蒯因在1972年补充道：-

波斯特作为共同创立者的递归函数理论，现在几乎是我写那封信时的两倍之久。它已被证明是一片多么肥沃的领域。

波斯特在城市学院授课的方式，至少可以说，是不寻常的。马丁·戴维斯于20世纪40年代末在纽约市立学院听过这样的课，在[4]中他给我们清晰地描绘了：-

波斯特的课组织得极为紧凑。每节课开始时，学生先背诵当天作业中的问题和定理证明。这些内容是随机指定的，必须在没有教科书或笔记帮助的情况下写到黑板上。准备不足的学生可就倒霉了。他（或很少是她）将不得不面对波斯特那“哀其不幸甚于怒其不争的神情”。接着，学生们依次背诵自己的作业。之后，波斯特会拿出他的3乘5卡片，讲解各种精妙之处。如果他在铃声响起时刚好讲完最后一张卡片，这节课就算成功了。课堂提问是不被鼓励的：没有时间。令人惊讶的是，这些刻板的教学方法极为成功，波斯特是一位非常受欢迎的老师。

Paul Chessin回忆大约1943年在纽约由波斯特授课的情形：-

我记得他是个矮壮的人，总是穿着三件套西装，空袖子仔细地塞进西装外套侧面的口袋里。他会稳步地在黑板前来回踱步，说话清晰，动作有力。他常常突然转身面向黑板，手里拿着粉笔写字。这个动作总是使那只袖子从固定处松脱，直到最后（令全班松了一口气）它像斗篷一样松散地摆动。在我们看来，这种活动的自由似乎在他讲课时解放了他的思维。

最后，我们给出马丁·戴维斯对波斯特的这段非常美好的赞词：-

波斯特的意义超越了他的科学贡献，尽管那些贡献很重要。他同样是一种激励，因为他克服了可能使他丧失能力的心理残疾，因为他独特的声音，以及因为他对科学和学生的持续奉献。

Emil Post's father was Arnold Post and his mother was Pearl Post. Arnold and Pearl were Polish Jews and their son Emil was born in Russian controlled Poland and spent the first seven years of his life there. The family emigrated to the United States in May 1904 looking for a better life, and set up home in New York.

Emil was an extraordinarily bright child but his life was one of great tragedy. When he was a child he lost an arm in an accident but this handicap was one which he handled well. He had to face mental problems in his adult life which had a devastating effect on him, making the physical problem of having lost an arm seem rather trivial in comparison.

There was free secondary schooling available for specially gifted children in New York. This was at the Townsend Harris High School which was situated on the same site as the College of the City of New York. After graduating from the High School Post remained on the same campus as he continued his studies at the City College.

We now think of Post as a mathematical logician but the first subject which attracted him was astronomy. While studying at the College of the City of New York he studied mathematics but there is little sign that at this stage he was particularly attracted towards logic. While an undergraduate at the College he wrote his first paper which was on generalised differentiation. The question he asked was a fascinating one: what does the differential operator $D^{n}$ mean when $n$ is not an integer? Although written while he was an undergraduate, Post did not submit the paper to the American Mathematical Society until 1923 and it was not finally published until 1930. It does contain a really important idea, for in the paper Post proves an important result about inverting the Laplace transform. This publication appeared long after Post's graduation with his first degree which was his B.S. awarded by the City College in 1917.

After graduating with his first degree, Post began postgraduate research at Columbia University. The significant event for Post's career had been the publication of Russell and Whitehead's Principia Mathematica. The first volume of Principia Mathematica was published in 1910, the second in 1912, and the third in 1913. When Post began his graduate studies it was an exciting new development and Post participated in Cassius J Keyser's seminar at Columbia which studied the Principia Mathematica. Post was awarded the degree of A.M. in 1918 and of Ph.D. in 1920. His Ph.D. thesis was on mathematical logic, and we shall discuss it further in a moment, but first let us note that Post wrote a second paper as a postgraduate, which was published before his first paper, and this was a short work on the functional equation of the gamma function.

We now turn to Post's Ph.D. thesis, in which he proved the completeness and consistency of the propositional calculus described in the Principia Mathematica by introducing the truth table method. He then generalised his truth table method, which was based on the two values "true" and "false", to a method which had an arbitrary finite number of truth values. The final, and perhaps the most remarkable, new idea which Post introduced in his thesis was to give a framework for systems of logic as inference systems based on a finite process of manipulation of symbols. Such a system of logic that Post proposed produces, in today's terminology, a recursively enumerable set of words on a finite alphabet. It would be fair to say that Post's thesis marks the beginning of proof theory.

After receiving his doctorate, Post went to Princeton University for a year as Proctor Fellow. He returned to Columbia University and, shortly after this, he had his first bout of an illness which was to recur throughout his career and limit what he might have achieved. As Davis writes in [4]:-

He suffered all his adult life from crippling manic-depressive disease at a time when no drug therapy was available for this malady.

In 1924 Post went to Cornell but again became ill. He resumed work as a high school teacher in New York in 1927. He married Gertrude Singer in 1929 and they had one child, a daughter Phyllis. Then in 1932 he was appointed to the City College. He left after a short spell, again struggling with his mental illness, but returned three years later and spent the rest of his life there. At the City College his teaching load was 16 contact hours per week which made finding time for research very difficult. Also members of staff has no offices of their own but were all put in a single room with one large table in the middle. Post chose to work at home, but with a young child this put a strain on the family. Post's daughter Phyllis explained later in her life how Gertrude Post had struggled to give her husband the opportunity to devote time to research:-

My father was a genius; my mother was a saint ... Besides typing letters of recommendation, my mother also typed my father's manuscripts and correspondence ... My mother was also the one who handled all financial matters ... she was the buffer in daily life that permitted my father to devote his attention to mathematics (as well as his varied interests in contemporary world affairs). Would he have accomplished so much without her? I for one, don't think so.

Post's early death at the age of 57 was almost certainly a direct consequence of the treatment he received for his mental illness. At that time such manic-depressive illnesses were treated with electric shock treatment. It was an horrific treatment for an horrific illness and one which caused great distress. It was based on nothing better than the fact that after patients received this treatment many had periods of more normal mental states. Post received the electric shock treatment on a number of occasions and it was while he was in a mental institution, shortly after receiving electric shocks, that he suffered a heart attack and died.

Post is best known for his work on polyadic groups, recursively enumerable sets, and degrees of unsolvability, as well as for his contribution to the unsolvability of problems in combinatorial mathematics. He introduced the concepts of completeness and consistency in a paper on truth-table methods which developed from the work of his doctoral thesis. He attributed these methods to his teacher at Columbia, C J Keyser, rather than to Charles Peirce and E Schröder as had been done previously. In the 1920s Post proved results similar to those which Gödel, Church and Turing discovered later, but he did not publish them. He reason he did not publish was because he felt that a 'complete analysis' was necessary to gain acceptance. He wrote:-

The correctness of this result is clearly entirely dependent on the trustworthiness of the analysis leading to the above generalisation... it is fundamentally weak in its reliance on the logic of Principia Mathematica ... for full generality a complete analysis would have to be given of all possible ways in which the human mind could set up finite processes for generating sequences.

He also made a mathematical study of Łukasiewicz's three-valued logic. At around this time he wrote in his diary:-

I study Mathematics as a product of the human mind not as absolute.

When Gödel published his Incompleteness Theorems in 1931, Post realised that he had waited too long to publish what he had proved and that now the whole credit would go to Gödel. In a postcard written to Gödel in 1938, just after they had met for the first time, Post wrote:-

... for fifteen years I carried around the thought of astounding the mathematical world with my unorthodox ideas, and meeting the man chiefly responsible for the vanishing of that dream rather carried me away. Since you seemed interested in my way of arriving at these new developments perhaps Church can show you a long letter I wrote to him about them. As for any claims I might make perhaps the best I can say is that I would have proved Gödel's Theorem in 1921 - had I been Gödel.

In a follow-up letter written the day after he writes:-

... after all it is not ideas but the execution of ideas that constitute a mark of greatness.

In 1936 he proposed what is now known as a Post machine, a kind of automaton which predates the notion of a program which von Neumann studied in 1946. In 1941 he wrote:-

... mathematical thinking is, and must be, essentially creative...

but he said there are limitations and symbolic logic is:-

... the indisputable means for revealing and developing these limitations.

Post showed that the word problem for semigroups was recursively insoluble in 1947, giving the solution to a problem which had been posed by Thue in 1914.

Quine, in a letter written in 1954 after Post's death, said:-

Modern proof theory, and likewise the modern theory of machine computation, hinge on the concept of the recursive function. This important number theoretic concept ... was discovered independently ... by four mathematicians, and one of these was Post. Subsequent work by Post was instrumental to the further progress of the theory of recursive functions.

Quine added in 1972:-

The theory of recursive functions of which Post was cofounder is now nearly twice as old as when I wrote that letter. What a fertile field it has proved to be.

The way that Post conducted his classes at the City College was, to say the least, unusual. Davis attended such classes at the College of the City of New York during the late 1940s, and in [4] he gives us a clear picture:-

Post's classes were tautly organised affairs. Each period would begin with student recitations covering problems and proofs of theorems from the day's assignment. These were handed out apparently at random and had to be put on the blackboard without the aid of textbooks or notes. Woe betide the hapless student who was unprepared. He (or rarely she) would have to face Post's "more in sorrow than anger look". In turn, the students would recite on their work. Afterwards, Post would get out his 3 by 5 cards and explain various fine points. The class would be a success if he completed his last card just as the bell rang. Questions from the class were discouraged: there was no time. Surprisingly, these inelastic pedagogic methods were extremely successful, and Post was a very popular teacher.

Paul Chessin recalls being taught by Post in New York in about 1943:-

I recall that he was a short stocky fellow who invariably dressed in a three piece suit, empty sleeve carefully tucked into the side suitcoat pocket. He would stride steadily up and down before the blackboard, speaking clearly, vigorous in his motions. He would frequently, suddenly whirl around to face the board, chalk in hand, to write. This motion always tended to loosen that sleeve from its anchor until finally (to the relief of the class) it flapped loosely about as a cape might. That freedom of motion seemed to us to liberate his thinking as he lectured.

Finally we give this very fine tribute to Post from Davis:-

Post's significance transcends his scientific contributions, important as those were. He remains an inspiration as well, for the manner in which he overcame his potentially crippling mental disability, for his distinctive voice, and for his continued devotion to science and his students.