理論上出来ないことの一覧
ある条件を満たす理論には必ず存在する証明も反証も出来ない文が存在する.
理論(すなわち論理式の集合)$ Tから$ \varphiが証明されることを$ T \vdash \varphiと書く.
ある条件を満たす$ Tでは必ず証明も反証も出来ないような文$ gが存在する
すなわち,$ T \not\vdash gかつ$ T \not\vdash \lnot g
構造$ \mathcal{M}で真な文の集合を言及する論理式は構成できない.
すなわち,次のような$ \varphi\lbrack v\rbrackは構成できない.
$ \vdash \varphi \left\lbrack \overline{\ulcorner\psi\urcorner} \right\rbrack \implies \mathcal{M} \models \psi
$ \varphi\lbrack v\rbrackは自由変数が一つ($ vとする)の論理式であるということを表す
「ある文$ \psiのGödel数の数項$ \overline{\ulcorner\psi\urcorner}を$ \varphiの自由変数とした文$ \varphi \left\lbrack \overline{\ulcorner\psi\urcorner} \right\rbrackが証明可能なら,元の文$ \psiは$ \mathcal{M}で真である」ということを表す.
インフォーマルな形式
プログラムを実行したときそのプログラムが有限時間で停止するかは前もって知ることは出来ない.
もうすこしフォーマルな形式
次のエミュレータ関数$ \varepsilon(i,x,y)を考える
$ \varepsilon(e,x,y) = 0: $ iというインデックスを持つTuringマシン$ \mathcal{M}_iに入力$ xを入れたとき出力$ yが得られる $ \varepsilon(e,x,y) = 1: それ以外
この$ \varepsilonを計算するTuringマシン$ \mathcal{M}_\varepsilonを構成することは出来ない.
永久機関の設計
永久機関を作ることは出来ない.
熱平衡化の解決不能性
この一覧の完全な列挙
ほんとうに?