エミール・ポスト

エミール・レオン・ポストは当時ロシア領だったポーランドのアウグストゥフに生まれ、ニューヨークで育った。1921年の博士論文で真理値表を手法として導入し、命題論理の完全性を証明した。同時期の未発表のノートでは、ゲーデルが発表する十年前に、不完全性定理に近いところまで辿り着いていた。彼はその論文をしまい込んだ。

1936年に発表した『有限組合せ過程――定式化1』は、無限に並んだ箱の間を作業者が動き、命令表に従って印をつけたり消したりするというものだ。実質的にチューリングのモデルと同じだが、ポストの側は人間が指示に従う形で記述した点が違う。のちに生成系（1943年）を作り、形式文法の基礎となった。さらに対応問題（1946年）は、ナプキンに書けるほど単純に述べられる決定不能問題で、決定不能性の証明では定番の道具になっている。