サイト内検索

詳細検索

ヘルプ

セーフサーチについて

性的・暴力的に過激な表現が含まれる作品の表示を調整できる機能です。
ご利用当初は「セーフサーチ」が「ON」に設定されており、性的・暴力的に過激な表現が含まれる作品の表示が制限されています。
全ての作品を表示するためには「OFF」にしてご覧ください。
※セーフサーチを「OFF」にすると、アダルト認証ページで「はい」を選択した状態になります。
※セーフサーチを「OFF」から「ON」に戻すと、次ページの表示もしくはページ更新後に認証が入ります。

【HB】丸善丸の内本店×hontoブックツリー 「本」の本 ポイント5倍キャンペーン(~4/25)

【HB】丸善丸の内本店×hontoブックツリー 「本」の本 ポイント5倍キャンペーン(~4/25)

目次

  • 第1章 導入
    • 1.1 一番大切な定義
    • 1.2 自然数,表記の約束
    • 1.3 部分関数
    • 1.4 関数プログラム
    • 1.5 現実のC言語との相違
    • 1.6 再び,一番大切な定義
    • 1.7 計算の理論の概観
    • 第1章の章末問題
  • 第2章 ジャンププログラム
    • 2.1 準備
    • 2.2 ジャンププログラム
    • 2.3 ジャンププログラムへの書換え
    • 2.4 特定形プログラム
    • 第2章の章末問題
  • 第3章 万能関数
    • 3.1 自然数のペアのコード化
    • 3.2 自然数の有限列のコード化
    • 3.3 ジャンププログラムのコード化
    • 3.4 万能関数
    • 第3章の章末問題
  • 第4章 計算可能・不可能の境界付近
    • 4.1 対角線論法
    • 4.2 停止問題の決定不可能性
    • 4.3 パラメータ定理
    • 4.4 再帰定理
    • 4.5 ライスの定理
    • 第4章の章末問題
  • 第5章 原始帰納的関数
    • 5.1 原始帰納的関数とは
    • 5.2 原始帰納的口数の定義
    • 5.3 具体例
    • 5.4 while文のないプログラム
    • 5.5 限定反復プログラム
    • 5.6 限定反復プログラムから原始帰納的関数へ
    • 5.7 原始帰納的でない計算可能関数
    • 第5章の章末問題
  • 第6章 帰納的部分関数
    • 6.1 準備
    • 6.2 帰納的部分関数,帰納的述語
    • 6.3 「計算可能」との同値性
    • 6.4 クリーネの標準形定理
    • 6.5 最小化に関する注意
    • 第6章の章末問題
  • 第7章 半決定可能集合
    • 7.1 集合を扱うことについて
    • 7.2 集合を半決定するプログラム
    • 7.3 集合を枚挙するプログラム
    • 7.4 さまざまな同値な条件
    • 第7章の章末問題
  • 第8章 計算不可能性の度合い
    • 8.1 量化の重なり具合による比較
    • 8.2 算術的階層
    • 8.3 万能述語,そして算術的階層が潰れないこと
    • 8.4 還元可能性による比較
    • 8.5 完全集合
    • 第8章の章末問題
  • 第9章 チューリング機械
    • 9.1 チューリング機械とは
    • 9.2 正確な定義
    • 9.3 具体例
    • 9.4 自然数上の関数の計算可能性
    • 9.5 チューリング機械の変種
    • 9.6 万能チューリング機械
    • 9.7 計算不可能性:ビジービーバー関数,ポストの対応問題
    • 第9章の章末問題
  • 第10章 P≠NP予想
    • 10.1 ハミルトン閉路問題
    • 10.2 多項式時間計算可能性
    • 10.3 非決定性チューリング機械
    • 10.4 P≠NP予想の正確な内容
    • 10.5 多項式時間還元可能性
    • 10.6 NP完全問題
    • 第10章の章末問題
  • 第11章 ラムダ計算
    • 11.1 導入
    • 11.2 ラムダ項
    • 11.3 ベータ簡約
    • 11.4 チャーチ−ロッサーの定理
    • 11.5 簡約の標準的な順番と最左簡約
    • 11.6 自然数上の関数の計算と決定不可能問題
    • 11.7 型付きラムダ計算
    • 第11章の章末問題
  • 付録A チューリング機械シミュレータ
  • 付録B ラムダ計算の定理の詳細な証明
    • B.1 チャーチ−ロッサーの定理
    • B.2 簡約順番の標準化定理
    • B.3 帰納的部分関数のラムダ項による計算