どんなに時間があっても、計算できない関数がUCが存在する 命題 どのチューリングマシンでも計算することが出来ないUC:{0,1}*→{0,1}が存在する 証明 UCを以下のように定義する 全てのa∈{0,1}*はチューリングマシン Mを表す - Mが有限ステップで終了し1を出力…