計算理論の基礎(チューリング機械)part2

停止問題(halting problem)とは、チューリング機械の結果が「受理・拒否」か「ループ」を
判定できるかという問題。
一般的に「停止性をアルゴリズム的に決定する方法は存在しない」。

万能チューリング機械(universal Turing machine)：他の任意のTuring機械の記述を用いて、
その機械をシミュレートする能力がある機械。

対角線論法：無限集合の大きさを比較する方法。二つの有限集合が与えられたとき、
一方の集合の要素がもう一方の集合の要素と対になることができるならば、その二つの集合は
同じサイズといえる。
これを無限集合へ拡張する。

対角線論法の定義
集合AとB、およびAからBへの関数fがあると仮定する。
・fが二つの異なる要素を同じあたいに決して写像しない。
つまり\[ a \neq b \]であるとき、\[f(a) \neq f(b) \]であるならば、
fは一対一(one-to-one)であるという。

・また、fがBのすべての要素に当たる、つまりすべての\[ b \in B \]に対して、\[f(a) = b \]となる
\[a \in A\]があるならば、fは上への(onto)関数であるという。

・一対一かつ上への関数\[ f:A\rightarrow B\]が存在するとき、AとBは同じサイズ(same size)
であるという。一対一かつ上への関数は対応(correspondence) or 全単射(bijection)と呼ばれる。

定義：集合Aが有限であるか、N(自然数)と同じサイズを持つならば、Aは可算(countable)である。

非可算(uncountable)：N(自然数)より大きい。例：実数

補Turing認識可能(co-Turing-recognizable)：ある言語がTuring認識可能な言語の補集合であるとき、その言語を補Turing認識可能と呼ぶ。