「すべての計算可能な関数は プログラムで表現できる」を公開しました

【「すべての計算可能な関数は プログラムで表現できる」を公開しました 】

9/30 マルゼミ「計算科学とエントロピー」 https://info-entropy4.peatix.com/ にむけたショートムービー「ランダムさの不思議」を公開しました。ご利用ください。

https://youtu.be/UplIfbz0Qsk?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K

スライドのpdfは、こちらからアクセスできます。https://drive.google.com/file/d/1WoI4t4KPvUU39APaTjVddr5S9BPleeCO/view?usp=sharing

ここでは、関数とプログラムの関係を、コロモゴロフの複雑性の定義から、考えようと思います。

コロモゴロフの複雑性は、「yを出力するプログラムpの最小の長さ」として、次のように定義されました。

　　𝐾_𝜑 (𝑦)=min⁡{ |𝑝|  :𝜑(𝑝)=𝑦 }

この定義の中に出てくる関数の型を確認しておきましょう。プログラムのクラスを𝒫とし、プログラムの出力のクラスを𝒪としましょう。

　𝜑 : 𝒫 ⟶ 𝒪　

　　  /* 𝜑(𝑝)=𝑦 */

　 　 /* 𝜑は、プログラム p : 𝒫を出力 y : 𝒪に変える関数 */

  𝐾_𝜑  : 𝒪 ⟶ ℕ　    

　　 /* 𝐾_𝜑 (𝑦)=min⁡{ |𝑝|  :𝜑(𝑝)=𝑦 } */

　　 /* 𝐾_𝜑は、出力 y : 𝒪を自然数 ℕに変える関数 */

ここで、すこし天下り的ですが、「すべての計算可能な関数は、プログラムで表現できる」と考えることにしましょう。

計算可能な関数の値は、関数に対応するあるプログラムがあって、そのプログラムを実行して得られる出力に等しいということです。

こうした主張を、「チャーチ＝チューリングの提言」と言います。

「チャーチ＝チューリングの提言」は、基本的には、関数とプログラムは同じものであることを主張しているのですが、関数とプログラムでは、言葉の使い方が異なります。

　　関数の「引数」を、プログラムでは「入力」と言います。

　　関数の「値」を、プログラムでは「出力」と言います。

まあ、でもこの言い換えは、自然なものです。

関数 f(x) という表現は、「関数 f(x) そのもの」という意味で用いられることもあれば、「関数 f(x) の値」という意味で用いられることもあります。それは曖昧です。

関数そのものと、関数の計算で得られた関数の値とは違うものです。二つを区別するために、fがxについての関数そのものであることを、次のように表します。

　　𝜆𝑥.𝑓(𝑥)

もちろん、プログラムそのものと、そのプログラムの実行とは別のものです。

関数とプログラムの対応の例として、コロモゴロフの複雑性の定義の中に出てくる、「プログラムpを出力yに変える関数𝜑」を、プログラムとして考えて見ましょう。

𝜑の働きは、 𝜑(𝑝)=𝑦で、入力のないプログラム p を、それを実行して、出力 y に変えることでした。

関数𝜑に対応するプログラムを e としましょう。

この時、プログラムeの実行 は、入力として プログラム p を受け取って、出力 y を返すと考えることができます。

　　𝜑 : 𝒫 ⟶ 𝒪　　　　/* 𝜑 : (プログラム)⟶(出力) */

でしたが、このプログラムは、入力を持っているわけではありません。ここで、プログラムとそれへの入力を、プログラムを実行して出力に変える、もう少し一般的な、関数 Uを考えます。

入力のクラスを ℐとすれば、Uの型は次のように表現できます。　　

　　𝑈 : 𝒫 × ℐ ⟶ 𝒪　　　　/* 𝑈: (プログラム,入力)⟶(出力) */

関数𝜑に対応するプログラムを e とすると、プログラムeの実行は、プログラムe は、入力として プログラム p を受け取って、出力 y を返すのですから、Uを使えば、次のように書けます。

　　𝑈(𝑒,𝑝)= 𝜑(𝑝) = 𝑦

このUは、面白い性質を持っています。

𝑈 : 𝒫 × ℐ ⟶ 𝒪　/* 𝑈: (プログラム,入力)⟶(出力) */ で、
𝑈_𝑐 = 𝜆𝑖 : ℐ. 𝑈(c, i) とすると、

　

　𝑈_c  : ℐ ⟶ 𝒪　　　　/* 𝑈_𝑐:  (入力)⟶(出力) */

𝑈_c は、入力を出力に変えるという、極めて一般的なプログラムの特徴を表現しています。

それについては、後でもっと詳しく見ていきます。