エミル・ポストとは？
えみるぽすと
エミル・ポストは、計算可能性理論や数理論理学の基礎を築いたアメリカの数学者・論理学者です。
エミル・レオン・ポスト（Emil Leon Post、1897〜1954年）は、ポーランド生まれでアメリカで活躍した数学者・論理学者です。計算可能性理論と数理論理学の分野で先駆的な業績を残しました。
ポストの最も重要な業績のひとつは、ポスト対応問題（Post Correspondence Problem）の提唱です。これは、与えられた文字列の対のリストから同じ文字列を構成できるかどうかを問う問題で、決定不能であることが証明されています。計算可能性理論において、他の問題が決定不能であることを示す際の「基準問題」として広く使われています。
また、ポストは1921年の博士論文において、命題論理の完全性と一貫性を（チューリングやゲーデルより先に）独立して証明していたことが知られています。さらにポスト機械（Tagシステム）と呼ばれる計算モデルを考案し、チューリング機械と同等の計算能力を持つことが示されています。
チューリングの停止問題と類似した結果も独立に導いており、計算の限界を探る研究において並外れた先見性を示しました。精神疾患を抱えながらも研究を続けたポストは、現代の計算理論・複雑性理論の礎を築いた重要人物として評価されています。
使い方・例文
「この問題の決定不能性はポスト対応問題への帰着によって示すことができる」という形で、計算理論や情報科学の授業・教科書に登場します。
この用語をシェア
最終更新: