p123

論理的深さ

そこで，ベネットは論理的深さを考えた[C. Bennett, “Logical depth and physical complexity,” in The Universal Turing Machine, a half century survey edited by R. Herken (Oxford UP, 1988) p227-257]．ある系を生成するに必要なプログラムの長さと実際にそのプログラムを使って系を生成するに必要な手間の間のギャップに注目し，プログラムに比してたくさんの計算の手間がかかるならば，生成された系は論理的に深いと言われ，その系は複雑であるとみなされる． こうして， コルモゴロフの意味で，ランダムでない数列が複雑なもの(深いもの) とそうでないものとに分類される．直観的に見て，統計的にはランダムだが，アルゴリズム的にはランダムでない数列が複雑ということになる．先の相関を使った議論との違いは，与えられたパタンだけに注目するのではなくその生成過程にも注目する点である．

　これに関して面白い話題は数列(記号列) の変換(たとえば2 進法から5 進法への変換) の下で「論理的深さ」は不変か，という問題である．つまり，論理的に浅い数列が変換で深くなったりしないかどうかである．．進法間の変換 は一般には計算手間数が数列の長さに比例しないアルゴリズムでは可能でない．ということはもともと浅い数列が進法の変換だけでより深くなりうるということだろう(コルモゴロフのランダムさにはこういう問題はないことに注意)．2.8 節の脚注128 に出て来た円周率を16 進法で書く話の根本的重要さはここにある．

作ることとわかることのギャップ

von Neumann が考えていたということは，この考え方はたぶん的を外しているということだろう.