全体像 はじめに:計算できるもの、できないものとは 扱いやすい問題、扱いにくい問題、計算不能問題とその例
計算できるもの、計算できないもの ―実践的アプローチによる計算理論入門 (John MacCormick(著)、松崎 公紀(監修)、長尾 高弘(翻訳)、オライリー・ジャパン)の全体像、1章(はじめに:計算できるもの、できないものとは)、演習問題1.1の解答を求めてみる。
1.1
- 扱いやすい問題: メモリーが十分な範囲での自然数の1からnまでの和
- 扱いにくい問題: 二人零和有限確定完全情報ゲームの将棋、囲碁、チェス、オセロ等の先手と後手のどちらが必勝か、あるいは引き分けか。大きいある整数が素数かどうかの判定。
- 計算不能問題: 自然数全部の集合の濃度(自然数の個数)を求める問題。無限こあるから計算が終わることはない。(これを計算不能問題といっていいか、計算不能問題をちゃんと理解できてないからかよく分かってない。)