2026/05/13 10:54
ロジック・テオリスト（Logic Theorist）定理証明機の再現プログラムにおける IPL-I バージョン
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
論理理論マシンは、アルレー・ニューエール、ハーバート・サイモン、クラフ・ショウが 1955 年頃に Principia Mathematica の系からシステムを自動化するために開発した人工知能の画期的な成果です。当初はサイモンの家族と大学院生の助けを得て手動でシミュレーションされ、最初に実行されたのはハードウェア上ではなく、 jamais にハードウェア上で実行されなかった IPL-I と呼ばれる疑似コードによるものでした。最初のハードウェア実装では JOHNNIAC で IPL-II が使用され、1956 年 8 月に初めて証明を生成しました。現代の愛好家は、歴史的な写写錯誤を補正したまま Principia Mathematica の定理から Python スクリプトを用いて論理を忠実に実装したオリジナルプログラムを複製・研究することができ、これらには Principia Mathematica の定理を実行するインタープリター、証明を抽出する処理routine、オリジナルコードと写写されたコードの整合性を保証するための検証ツールが含まれています。该系统は 5 つの公理（*1.2–*1.6）および分離（detachment）（*1.11）や置換を含む推論規則に基づき、*2.05/*2.06 の定理によって正当化されたチェーン法を利用して、(p → q) および (q → r) から (p → r) のような帰結を導出します。保存活動により、これらの基礎となる AI メソッドが学習と教育の目的でアクセス可能であり、ニューエールとサイモンの仕事に関する追加リソースは CMU デジタルコレクションアーカイブで見ることができます。
本文
このコードの目的は、ロジック理論マシン（Logic Theory Machine）、あるいはロジック・ソサイリストとも呼ばれる、その刊行された最初のバージョンを実装することにあります。ロジック理論マシンは、アレン・ニューエル、J.C. ショウ、ハーマン A・シモン氏によって作成されたプログラムであり、ヘurisティックな問題解決手法に関する研究の一環として開発されました。本プログラムでは、プリンキピア・マティエマティカ [1] に記述された論理系を用いて命題論理の定理を証明することを意図していました。ニューエル氏とシモン氏は 1955 年末頃にプログラムの記述を開始し、当初は手作業でプログラムをシミュレートしており、ある時点ではシモン氏の妻や子供たち、および大学院生らを支援者として迎えています [3]。最初は実装は行われたことのない仮コード言語「IPL-I」 [Interpretive Programming Language- I] で記述されました [2], [3]。コンピューター上で最初に実行されたバージョンは IPL-II で書かれており、JOHNNIAC という計算機上で動作し、1956 年 8 月に初の証明を果たしました [1], [2], [3], [4]。その後、フレッド・トンジ氏によって IPL-V に変換され、アイナー・ステッフェルード氏によってさらに開発されました [5]。
ロジック理論マシンの初期バージョンに関するソースコードは、1956 年に [6] および [7] で出版されました。いずれも抽象的なマシン向けのアセムブラー様式言語である IPL-I で記述されています。両方の参考文献におけるコードはほとんど同一です。残念ながら、掲載された形式のままではすぐに実行可能ではなく、いくつかのタイプミスや問題が含まれていました。私はソースコードファイルに詳述されている通り、必要な修復を試みました。
論理系
プリンキピア・マティエマティカ [8] に記述される命題論理系は、一元否定演算子（〜）と二元の「または」演算子（∨）によって、命題変数から式を構成します。帰納演算子は (p → q) を (~ p ∨ q) と定義し、これら二つの表現は互換可能 (*1.01.) と扱われます。使用される五つの公理は以下の通りです：
- ((p ∨ p) → p) （*1.2）
- (q → (p ∨ q)) （*1.3）
- ((p ∨ q) → (q ∨ p)) （*1.4）
- ((p ∨ (q ∨ r)) → (q ∨ (p ∨ r))) （*1.5）
- ((q → r) → ((p ∨ q) → (p ∨ r))) （*1.6。）
推論の規則は、脱着（detachment）（*1.11）、すなわち p と (p → q) から q を導き出すこと、ならびに既知の公理または定理における命題変数への式置換です。（プリンプキピア・マティエマティカにおいて置換は明示的な演繹規則として言及されていませんが、*2 の冒頭で認められ、広く用いられています。）置換と脱着に加えて、ロジック理論マシンは連鎖法という証明方法也用いています。具体的には、(p → q) と (q → r) から (p → r) を導き出します。これは、プリンキピア・マティエマティカの定理 *2.05 および *2.06 によって正当化されます。
コードについて
ここで直接実行を意図した Python ファイルは
logic.pyrun_logic.pyanalyze_output.py--helplogic.pyanalyze_output.pylogic.pylogic.py--inforun_logic.pyファイル一覧
- README.md — 本書
- IPL-I ソースコード：
— ロジック理論マシンの IPL-I ソースコード（実行可能な状態への改訂版）logic-routines.txt
— [7] に掲載されたロジック理論マシンの元の IPL-I ソースコード（ラベル、オペコード、オペランドのみ）orig-logic-routines.txt
— [7] に掲載された全ソースコードの文字起こし（注釈付き）transcription.txt
- プリンキピア・マティエマティカ：
— プリンキピア・マティエマティカ *1 に記載される五つの命題論理公理pm-axioms.txt
— プリンキピア・マティエマティカ *2 に記載される定理pm-theorems.txt
- IPL-I インタプリタ：
— インタプリタが発見した証明を抽出および検証するプログラムanalyze_output.py
— コンテキスト自由文法（CFG）ルーチンを備えたモジュールgrammar.py
— IPL-I 抽象マシンのインタプリタlogic.py
— ドライバプログラムrun_logic.py
— コンテキスト自由文法パーサーを備えたモジュールsimple_parser.py
— 文法および置換ユーティリティルーチンを備えたモジュールutils.py
- テスト：
,test.sh
— テストフレームワークtest.py
,analyze_output.test
,analyze_output.test-input
—analyze_output.usage
用のテストanalyze_output.py
,logic.test
,test-source.txt
,test-source-2.txt
,test-source-3.txt
,test-theorems-1.txt
,test-theorems-2.txt
,test-theorems-3.txt
—logic.usage
用のテストlogic.py
,run_logic.test
,say-hi.py
—run_logic.usage
用のテストrun_logic.py
—verify.py
のソースコードとorig-logic-routines.txt
のソースコードの整合性を検証transcription.txt
引用文献
ニューエル氏とシモン氏に関する特集コレクションを含む CMU デジタルコレクションアーカイブには、ロジック理論マシン／ロジック・ソサイリストに関する多くの追加情報が含まれています。URL https://digitalcollections.library.cmu.edu/ をご参照ください。特に以下の URL もご覧いただきたく推奨します：
- https://digitalcollections.library.cmu.edu/cmu-collection/allen-newell
- https://digitalcollections.library.cmu.edu/cmu-collection/herbert-simon
参考文献：
- [1] A. Newell, J.C. Shaw, H.A. Simon「Empirical Explorations of the Logic Theory Machine: a Case Study in Heuristic」, IRE-AIEE-ACM '57 (Western): Papers presented at the February 26-28, 1957, Western joint computer conference: Techniques for reliability, Feb. 1957, pp. 218-230, DOI: 10.1145/1455567.1455605.
- [2] Allen Newell et al.「Information Processing Language-V Manual, second ed.」, RAND Corporation, pub. Englewood Cliffs, NJ : Prentice-Hall, Inc., 1964, https://archive.org/details/bitsavers_randiplInfanguageVSecondEdition1964_15001417.
- [3] Herbert A. Simon「Models of My Life」, Cambridge, Mass., etc.: MIT Press, 1996 (first pub. 1991, Basic Books.) (Chapter 13)
- [4] A. Newell, J.C. Shaw「Programming the Logic Theory Machine」, IRE-AIEE-ACM '57 (Western): Papers presented at the February 26-28, 1957, Western joint computer conference: Techniques for reliability, Feb. 1957, pp. 230-240, DOI: 10.1145/1455567.1455606.
- [5] Einar Stefferud「The Logic Theory Machine: A Model Heuristic Program」, Introduction in, RAND Research Memorandum RM-3731-CC, June 1963, https://www.rand.org/pubs/research_memoranda/RM3731.html.
- [6] A. Newell, H. Simon「The Logic Theory Machine--A Complex Information Processing System」, IRE Transactions on Information Theory 2, #3 (September 1956), pp. 61-79, DOI: 10.1109/TIT.1956.1056797.
- [7] Allen Newell, Herbert A. Simon「The Logic Theory Machine: A Complex Information Processing System」, RAND paper P-868, July 12, 1956, Revised, https://archive.org/details/bitsavers_randiplP86ineJul56_3534001.（これは [6] と極めて類似しています。）
- [8] A.N. Whitehead and B. Russell「*1 and *2, Principia Mathematica, Volume I」, Cambridge: Cambridge University Press, 1910. HathiTrust で利用可能；https://hdl.handle.net/2027/miun.aat3201.0001.001?urlappend=%3Bseq=117 をご参照ください。