再帰理論

　

概要「計算ができるかどうかの話」

チューリングマシン「ほぼ全て表現できるやつ」

　　　チューリング完全「2状態3記号で十分」

　　　停止問題「計算が終わるかどうかの話」

　

　

μ再帰関数「自然数 → 自然数の関数」

　　　ラムダ計算「変数置換と関数定義のみ」

　

計算複雑性理論「計算が何で複雑になるのか」

　　　チューリング次数「複雑さを表す指標」

　

再帰定理「自己完結してるよ、という感じの話」