数学 › 数理論理学と型理論 › 計算可能性

停止問題

定義 7.1(「計算可能性」§7)

K={ e∈N∣φe(1)(e)↓ }K=\{\,e\in\mathbb{N}\mid\varphi^{(1)}_e(e)\downarrow\,\} を停止問題の集合という。機械 MeM_e を自分自身の番号 ee を入力として走らせたとき、標準出力で停止するような ee の集合である。

本文で読む(前後の説明と例)→

閉包の状態

定義

定義は閉包の起点です(証明を要しません)。

印の意味: ✓公理まで証明済み ・ △証明あり(閉包未完)・ ※主張のみ。テーマごとの集計は 閉包の状況。

これを使っている定理 証明で参照している 2 件

関連するノック 2 問