NO.10408045
大学数学全般に関する質問＆疑問【文系も可】
-
7 名前：タワー７１３：2007/07/28 10:39
-
第1不完全性定理
自然数論を含む帰納的に記述できる公理系が、ω無矛盾であれば、証明も反証もできない命題が存在する。
第2不完全性定理
自然数論を含む帰納的に記述できる公理系が、無矛盾であれば、自身の無矛盾性を証明できない。
Q は有限集合であり、その元を状態という。
Γ は Q に交わらない有限集合であり、字母とよばれる。
その元を記号という。
b は Γ の元であり、空白記号とよばれる。
Σ は Γ - {b} の部分集合であり、入力字母とよばれる。
その元を入力記号という。
δ は Q × Γ から Q × Γ × {left, right} への写像であり、
遷移函数とよばれる。δ(q, a) = (q', a', m) は、
「現在の状態が q であり、着目位置にある記号が a であれば、
状態を q' に移し、着目位置に記号 a' を書き込んでから、
着目位置を m 方向に1つずらす」と読む。
qinit は Q の元であり、初期状態とよばれる。
qacc は Q の元であり、受理状態とよばれるんだったと思う
後半はチェーリングマシーンの説明、これを使えば
説明しやすいかな？