大事な関数を構成するのを忘れていたので、今日はそれについて。 x が偶数であるとき 1、そうでないとき 0 を返す関数 even と、奇数について同様の関数 odd を次のように定義しますよ。 次に、ヘッドが指し示すテープのマス目の番号が x であるとき、ヘッド…

前回の記事では、チューリングマシンのインデックス e が与えられたとき、その状態数 n と、状態数が n のチューリングマシンの中での順番 k を求める関数をそれぞれ構成しました。 今回は、n と k とチューリングマシンの状態 q とテープに書き込まれた記号…

途中から面倒になって途絶えていましたが、最後までやろうと思います。 今日は、チューリングマシンのコード化についての話。 チューリングマシンは、状態と記号から、次の状態と書き込む記号と移動パターンへの関数と考えることができます。 今、記号は簡単…

多分、この世界では、P=NP であるか P≠NP であるかのどちらかだと思うのです。 つまり、一方が正しく、一方が間違いなのです。 そこで、P対NP問題を解決するため、P=NP を形式化した命題 を考えます。 さて、ある無矛盾で帰納的な公理系 T において が証明で…

ちょいと訂正の回です。 以前の記事で、チューリングマシンの動作を表現するには、チューリングマシンとチューリングマシンの状態とテープの状態のそれぞれをコード化したものがあれば良いと書きましたが、テープヘッドの場所も必要なのを忘れていました。 …

今回は、テープの状態を非負整数を使って表現することを考えます。 簡単のため、記号は 0 と 1 のみとし、テープに書き込まれている 1 は有限個で、1 が書き込まれていない全てのマス目は 0 で埋まっているものとします。 また、テープは左方向にのみ無限に…

便利な関数を色々と定義しておきます. 変数は全て整数全体を渡るものとします. クロネッカーのデルタや大なりなり小なりなどは, 論理式として正しければ 1, 正しくなければ 0 を返します. 単位階段関数. イコール（クロネッカーのデルタ）. ノットイコール. …

チューリングマシンの動作を数式で表現しようと思い立ちました。 数式で表現するにあたり必要なのは、チューリングマシンのインデックスと、チューリングマシンの状態と、テープの状態、の、それぞれを適当にコード化したもの。 したがって、3つの自然数をい…

PとNPが等しい、または等しくないという主張を形式化した文が体系に依存して構成されるものだとすると、P対NP問題を形式的体系内で解決することは難しいのではないかと思います。 ゲーデルの第二不完全性定理の証明に使われる証明可能性述語はまさに体系に依…

チューリングマシンは可算無限個あり、しかも洩れなく列挙することが可能なので、各チューリングマシンに適当にナンバリングをすることができます。 要するに、ゲーデル数を割り当てることができます。 しかしながら、普通にコード化すると、ある自然数には…