突然ひらめいたので、とにかく書いておきます。
同じことは既に誰かがやってそうですが、とりあえずRyuzのオリジナル思考です。
前提として、コンピュータの停止問題などの証明は知って置いてください。
ぐぐった限りでは
こちらのこことか大変よくまとまっておられるようです。
以下、プロセッサパワーは無限、メモリも無限。 チューリング記述可能か否かのみ論じます。
チューリングマシン用の記述ルールを任意に定める（例えばアセンブリ言語でも、LI SPでも、pythonでも、C言語でもなんでも良い）。
n bit の値を 1 bitに変換する任意の写像Xを考える（←出力もm bitにすればチューリングマシンの定義そのものかも）。
この写像を実現する関数の記述は無数にあるが、このうち最小の文字数での記述を求める関数 f(X) の記述が存在すると仮定する。
（ここでは仮に f 関数自身は、100万文字で記述できると仮定する。別に何文字でも
いい、とにかく有限数で書けると仮定する）。
n bit の場合の写像の種類は 2^(2^n) 種類ある。
＃ 2^(2^n)種類の写像のi番目を得る関数X(i)は簡単に定義できるので割愛。
この 2^(2^n) 種類のうち、記述に要する最小の文字数が最大であるものを求める関
数g(n)を考えると、
strlen(g(n)) ＞ 200万文字 となる n は必ず存在する。
そうでなければ、無数にある写像のすべてが200万文字以内で記述できてしまうこと
になる。
しかしながら、関数 g は、先に仮定した関数 f を用いると
g(n)
{
max_len = 0;
for ( i = 0; i < 2^(2^n) ; i++ )
{
if ( strlen(f(X(i))) > max_len )
{
max_len = strlen(f(X(i)));
max_X = X(i)
}
}
return max_X;
}
のように、100万文字＋αで記述可能である。
これは矛盾する。
従って、n bit の値を 1 bitに変換する任意の写像Xを最小の文字数での記述を求 める関数 f(X) の有限な記述は存在しない。
最少のステップ数で解く関数も求められないことを証明したい。「最少のステップ数で解く関数の記述文字数 ＞＝ 最少の記述文字数の関数の記述文字数」だし、最少演算ステップ数を求める有限の演算ステップとかを仮定すれば同じロジックで証明できそうな気はする。
＃ だって、求める演算ステップ×定数のオーダーでインタプリタ実現可能だから。
即ち、演算速度最適コードを求めるコードも記述不可能と思われる。
―――― 2005/08/31 追記 ――――
と思ってたんですが大嘘な気がしてきました。最少ステップで求める問題難しすぎです。
コンパイラとかでよくある、サイズ優先／速度優先の最適化がありますが、サイズと速度は等価交換できない概念な気がしてきました。
有限の写像をテーブル化して全展開すれば有限の写像に関しては高速実装可能ですが、逆に時間さえ掛ければいくらでも小さくなるかというとＮＧな気もします。
とはいえ、入力が「有限」というだけでサイズ固定されないと写像定義も出来ないわけでこまったぞっと。
答えはどこにあるのやら。
で、まあ、最適化がらみで、新たに考えたことなぞ
「２つの任意のチューリングマシン記述を比較して、等価か否かを判定するチューリングマシン記述は存在しない」って証明できそうな気がします。
だってこれが出来たら、ある記述より短い記述すべて（これは有限）と、その記述を比較して回れば、等価でかつより短い表現が探索できてしまうので「数の最小表現」を求めるアルゴリズムが存在しないことと矛盾しちゃいますから。
そもそもこれが出来たら、NP問題と等価なPアルゴリズムを探索していく記述が書けてしまう。もっとも書けたところでNPがPでなかった場合に止まらずに無限サイズの記述に向かって順に試しつづけるから、停止問題に帰着しちゃったりするのだが。
＃ あれ？ これはもしかして重要な発見？？？
――――――――――――――――
話を変えて、狭い領域からのアプローチ、
即ちインストラクションメモリのパターンを
0 -> 1 -> 01 -> 10 -> 11 -> 100 -> .....
のように順番に試して最適値を探せばいいようにも思えるが、そもそも試すには停止問題を解くアルゴリズムが存在しないので、あるビットパターンが、終了しないのか、それとも実は無限に近い果てに最適値を出すかの判定が不可能である。
よってこの手も使えない。
（おもいっきり余談だが、有限なメモリの状態はやっぱり有限で、例えばVRAMを順番にインクリメントしていけばいつかは偶然「モナリザの微笑み」なみの名画が出来るかも。そういう意味ではすべての状態を重ねて計算できる量子コンピュータはすごい。でも評価関数をどうするかはやっぱり問題）。
この証明がもし正しかったとすれば、メモリ／プロセッサパワーの進化に合わせて、コンパイラ等のアルゴリズムの優越競争は永遠に続くことを意味し、ある意味工学的には夢を追いつづけることが出来るとも言えるのかもしれない
あと、この証明が正しければ、世の中には、妥協解は求まるが最適解が求まらない問題クラス(写像)が少なくとも存在することを示す。
証明途中で用いている、最悪の最小値を持つ写像だが、これは多分bitの対応関係がもっとも純乱数に近い（エントロピーが高い）ではないかと思う。コンピュータでは擬似乱数は短い表現が可能だが、本物の乱数は定義すら出来ないってとこに帰着する気がする。（これまた余談だが、熱雑音とかでペタバイト級の乱数を作って暗号鍵にすれば、鍵は圧縮できないので持ち運びがとても大変で、盗みにくくて超巨大ストレージをトラックで運ぶしかない、セキュアな設備が作れそうな気がします）。
といって思い出すのはNP完全問題である。
例えばTSPのアルゴリズムはどんどん最適化されている。だが「これが最適解！」というのはまだ無い。それがPなのかNPなのか証明できればチューリング賞ものだと聞く。
が、ここで、TSPを、nビット入力と置けることに気が付く。
出力の巡回ルートもmビット出力と定義できる。
この写像の最適化限界点が、PかNPか分かればいいはずだ。
なんだがその前にこの最適問題自体は計算可能なクラスなのか、不可能なクラスなのか？（まあ、「最適ではないけどP」ってのが見つかる落ちもあるからアレだけど）。
チューリングマシンで解けるものを「計算可能」と定義するのならば、そして更に後者とするならば、TSPがNPかPでないかを判別するチューリング記述が存在しない。すなわちPかNPかを計算すること自体が不可能という結論になりはしないだろうか？とりあえずここまでの自分の証明を信じて、最適化問題に計算不可能な対象があることを前提に話を進めてみる。TSPは少なくとも総当りで解ける（先の任意の写像だってテーブル化すればとりあえず何でも解ける）。問題は「Pになるか否か判定がつくまで最適化」する方法があるか否かである
最適化可能／不可能のクラスわけを明確化する必要がある
この証明は「最小数の表現問題」とよく似ている。問題対象領域の発散が記述領域をそれ以上の速度で発散させることに自己矛盾を発生させている。この辺に鍵があるきがする。
TSPは少なくともバックトラックによる全探索で入力と出力は定義可能である。しかし最適値が見つかっていない。最適値自身の計算可能性自体について切り込んでみたい。
（考え中）
....
故に、TSPがNPかPの何れかであるかを求めるチューリングマシン向けの記述アルゴリズムは存在しない。
もし「数学的に記述可能＝チューリングマシン記述可能」であれば、この問題は解けないことが証明可能である。
↑ 私はこの問題を証明したが、それを記述するには余白が足りない（笑）。
これ書く前に書き始めた駄文（書きかけ）
どんどん脱線なんだが、有限条件で最適が定義できないのだとすると、比較関数も定義できないことになる。どちらがよりベターかの比較を有限状態に適用すればどれがベストか（最適か）が求まってしまう。
ってことは例えば任意の数列において、「どちらがよりランダムか？（エントロピーが高いか？）」を汎用的に判別する関数は記述できないことになるような気がする。
で、エントロピーと言えば圧縮ジャンルなんだが、論理限界が求まらないことになる。だって、チューリングマシンの最小表現＝最高圧縮だから（可逆については）。 （限界はTHcompだったりしてね(笑)）。
まあ、どちらがよりランダムかが比較で来ちゃうと純乱数がコンピュータで作れちゃうという問題が発生するのでたぶん無理でしょう。コンピュータなんてFFとメモリの数分の有限状態オートマトンですから、結局は。そのなかで人間が記述可能な問題領域を実に見事に状態数の少ない方向に論理圧縮して見せたのがチューリングマシンだと思いますよ。
32bitから32bitを求める関数の種類だけで、網羅するには4G×32bitのメモリが必要なんです。でも、これよりもっともっと少ないメモリで、さまざまなことをやってきたじゃないですか？。
これって「人間にとって」有意なものだけを圧縮して少ない状態数に押し込むことをチューリングマシンがやってのけたからなんですよね。究極の圧縮機だと思います。しかもしれは「人間にとっての有意」を起点にしている気がしなくも無いです。数学的なものなのか、人間原理を持ち出さねばならないものなのか、そこは謎ですが、実に興味深い装置です。チューリングマシンってやつは。
有限なチューリングマシン向け記述は不可能だが、無限なチューリングマシン向け記述を吐く、有限のチューリングマシン向け記述は可能とか言われたら私は発狂する(笑)。カントールのアレフ０、１、..... とかわらんではないか！！。
でも数の最小表現とか、それを求める無限な記述はありえるのかも。で円周率でも何でも良いんだけど、その無限のルールは有限で書けちゃったりして。「数の最小表現」って有限なサイズの記述が出来る事は無いことを証明してるだけで無限であれば可能かもしれないし、無限であってもそのルールを別次元で有限記述できる可能性はあるわけで...
＃ 間違ってるのかなぁ。。。
でもまあ、チューリングマシンにしろ、不完全性定理にしろ、記述する側が可加算(アレフ0)なのを前提にしてるところがあるような。それでアンカウンタブルなものを扱うんだから無理ありますよね。
でも、自然界って、紙に鉛筆で書く場合なんか「これぐらい なが〜〜〜〜〜い 距離」とか、定規当てて測らないといけないようなふざけた記述も可能なわけで、そのようなプログラム記述が可能なアナログコンピュータのようなものに対する記述だったらまた話は変わるのかもしれませんよねぇ。
こっちのネタもそうなんですが、そもそもチューリングマシンじゃない計算機どうなるんだろう？。。。