計算機科学のブログ

全体像 はじめに:計算できるもの、できないものとは 扱いやすい問題、扱いにくい問題、計算不能問題とその例

計算できるもの、計算できないもの ―実践的アプローチによる計算理論入門 (John MacCormick(著)、松崎 公紀(監修)、長尾 高弘(翻訳)、オライリー・ジャパン)の全体像、1章(はじめに:計算できるもの、できないものとは)、演習問題1.1の解答を求めてみる。

1.1

  1. 扱いやすい問題: メモリーが十分な範囲での自然数の1からnまでの和
  2. 扱いにくい問題: 二人零和有限確定完全情報ゲームの将棋、囲碁、チェス、オセロ等の先手と後手のどちらが必勝か、あるいは引き分けか。大きいある整数が素数かどうかの判定。
  3. 計算不能問題: 自然数全部の集合の濃度(自然数の個数)を求める問題。無限こあるから計算が終わることはない。(これを計算不能問題といっていいか、計算不能問題をちゃんと理解できてないからかよく分かってない。)