  |
はてなキーワード: チューリングマシンとは
カーネルコミッターでも、処理系実装者でも無さそうな人達が、「Cは滅びず！」と叫んでいる不思議な光景。
http://b.hatena.ne.jp/entry/shyouhei.tumblr.com/post/5545216280/c
http://b.hatena.ne.jp/entry/shyouhei.tumblr.com/post/5603961294/c
Linuxカーネル（せめてPOSIX互換品)を手前が思う言語にさっさと移植すれ。さすればCを滅ぼせん。（ちなみに高機能アセンブラの最適解がCとは俺も思っちゃいない。）
最後のＣの牙城、Linux（ＵＮＩＸ）をＪａｖａなり何なりベターな言語にさくっと移植してくれ。それともgoogleビッグブラザー様がクラウドでＵＮＩX鯖を駆逐してくれるのを祈ってればいいのか？
JavaもC#も，それにPerlもRubyもPythonも，実行環境自体はCで書かれている件。コンピューターが「シリコンを基材としたチューリングマシン」であるかぎり，アセンブラとCは滅びない。
手順を考えて、その手順を書くだけ。
言語もあらかじめ決められた手順に沿って解析されて実行されるから、オートマトンやBNF記法、構文木などの仕組みを一通り覚えてどういう機構でチューリングマシンが原理的に実行可能なコードへと落とされるかを理解すれば言語自体も覚えるのなんてそんなに難しくない。
手順を考えるなんて、人間が生活する上でいつもやっていること。
プログラムを走らせるためのデータ構造を考えるのに苦労するという話も聞くけど、プリミティブな要素が数値、型へのリファレンス値しかないんだから大体は離散数学で使うグラフの初歩的な知識があれば事足りる。GoFのデザインパターンなんてまさにそう。
これらは、専門用語の知識は知らなくても概念としては理解できて当たり前の事だから書けることもそれほどすごい事ではない。
一部の人には有名なPvsNP(P!=NP)問題の別解をhttp://arxiv.org/abs/1008.2247でまとめたのですが、twitter弄っていたらなんかまとまったのでこちらにも転載しておきます。
誰か突っ込みをお願いします。
まずチューリングマシン(TM)の大きな特徴を考えます。TMの計算力の源として「複数ある入力をまとめていくつかの計算結果にする」というものがあります。
例えば足し算 1+2+3+4+5 は、あらかじめ定められた計算によって15という計算結果となります。 10+5, 1+14, 5+5+5 なんかも同様ですね。これらの入力も結局は15という計算結果にまとめられます。
もちろん、人間の別の入力やランダムを活用すれば何とかなりますが、基本は入力だけに依存するという条件になりますので、入力が同じならば結果も同じになります。
「複数ある入力をまとめる」というのがTMの特徴だとすると、その入力同士の関係はどのようになっているのか？というのが http://arxiv.org/abs/1008.2247 の骨子です。
TMの入力と出力の関係が簡単であればあるほど、計算する時間も短くて済みそうです。逆に入力と出力の関係が複雑であればあるほど、逆に計算する時間が長くなるでしょう。
では、TM計算量と入力／出力の関係はどういうものがあるのか？
関係を扱う数学の道具はたくさんありますが、ここで私は大好きな対称性を使ってみました。
複数の入力をまとめる時、決定性TMでは高々1つの文字しか変更することができません。計算途中のテープの文字は一致している必要があります。
しかし、入力／出力の関係が複雑だと、これをまとめあげるのに多大な苦労があります。気を付けないと、間違った入力まで一緒にしてしまう可能性があります。
そこで、http://arxiv.org/abs/1008.2247 で一つ仮説を立てました。 「テープ全体を使って、テープの変更する場所＆文字を1ヶ所以上決定できる」 この関係が常に成り立つのがPではないかと。
HornSATやCNFSATをベースに色々と弄ってみたところ、ビンゴ。あたりのようです。このような問題を秩序問題と名付けました。
秩序問題が来れば今度は混沌問題でしょう。ということで混沌問題を定義して対比させます。
秩序問題は下記の通り「計算結果が対称となる1文字を活用して虱潰しに可能性を制限することができる」という特徴があります。
ならば、混沌問題は「複数の文字がセットでないと計算結果が対称にならない」ということでしょう。この複数の文字を拡張文字と名付けます。
こちらもビンゴ。あたりです。CNFSATやSATでは、拡張文字の長さに上限がありません。つまり、拡張文字は無数にあることがわかりました。
それでは、拡張文字とは何でしょう？ 「0,1,2……を使った数の表記みたいなもの」です。文字を組合せて使うことで、その部品だけでは表現できなかったたくさんのことを表現する文字です。
秩序問題にはこの拡張文字のような「一つに固まった塊」「どこまでも増えていく塊」という概念はありません。結局文字一つ一つをバラバラに扱えますので、塊として扱う必要がありません。
そして、拡張文字は、長さのべき乗規模で数が増えていきます。 ……ここで「指数規模」というPvsNPに繋がるギャップが出て来ました。
ここまで来ればあと一息です。
秩序問題と混沌問題の違いを浮き彫りにします。 まず、NP完全の混沌問題はP完全の秩序問題そのものでは表現できません。そして、指数規模に膨れ上がった拡張文字のせいで、秩序問題を多項式規模で繋げても混沌問題を計算することはできません。
よって、P(秩序問題=P完全) << 混沌問題=NP完全 となるので、PvsNPはP!=NPとなります。
……という話をhttp://arxiv.org/abs/1008.2247 にまとめています。 誰かコメント貰えると助かります。 もう自分じゃギャップ見付かりません…………
http://arxiv.org/abs/1008.2247 の日本語ファイルはhttp://arxiv.org/e-print/1008.2247v4 にあります。拡張子を.tar.gzに変更して展開して下さい。
この記事にはブクマを見る限りだいぶ懐疑論が集まってるみたいだね。残念ながらWebで資料を探しても見つけることができなかったので、憶測でしか語れないけれども、たぶん大丈夫だと思う。もっとも、「理論的には」の話であって「実用的に」どうかは知らないけどね。
まず、大矢氏はその道では有力な研究者で、名前も売れてます。俺のような門外漢でも知ってるぐらいだから。だから、胡散臭いものに手を出すという動機がまずないんですよ。
ただし学者というのは自分の仕事を宣伝してナンボという商売でもあるから、まだ残っている欠点を敢えて黙っているということはあるかもしれない。でも、少なくとも「CABは完璧な暗号である」とは言っていないはず。そういう意味で、嘘はついていないことは信用していいと思います。
次に、大矢氏の発言「鍵空間は無限大ですから、鍵を推定できる確率はゼロ」という発言は数学的に普通かつ真っ当なものであって、レトリックでないことを指摘しておく。
数学では、確率は長さとか面積とか体積とともに「測度」という概念に包含されるんだけれど、「確率0」というのは「『点』は『無』ではない」という話と本質的には同じものだ。例えば、中学校の時「点には大きさがない、長さも幅もない」「直線には幅がない」「平面には厚みがない」と習ったはずだけれど、つまりこれは「点の長さは0」「直線の面積は0」「平面の体積は0」って話なんだよね。点とか直線とか平面というのは「無」ではなくちゃんと存在するものなのに長さとか面積とか体積が0（こういうのは「零集合」なんて名前もついてる重要なものだ）という話、当初違和感をもたなかった？多分、今になってみれば感覚的に「そんなもの」だと理解できているはずだけど。つまり、「長さや面積や体積が0ということと、存在しないということは別物だ」ということ。
確率が0というのもこれと同じなんだ。例えば、0<x<1を満たすxを全くのランダム（あるxが別の数より選ばれやすいということはないものとしよう）に選んでくることを考えよう。これはまさに「数直線0<x<1上、x=0.5という一点の長さはいくつ？」と聞いているのと同じことで、答えは0になる。別に変なことではないでしょ？
もっとも確かに、「現実のコンピュータ上で、鍵の候補が無限大なんて関数が作れるのか」という疑問があると思う。俺の理解が間違ってなければこれは確かに無理だ。でも、そういう言い方をするのは無理なことではないんだ。
というのは、アルゴリズムの理論を作るときは、暗黙に「コンピュータには無限にメモリがある」と仮定してしまうことがある。もちろん現実にはそんなことはない。でも、必要なだけメモリを増設すればいくらでもその状態に近づけることはできるので、実用はともかく理論としてはそれで十分と考えることがあるんだ。
もう少し詳しくいうと、チューリングマシンっていう数学モデルがあるんだけれども、これはメモリが無限にあるコンピュータと等価な能力を持っている。そして、情報工学の問題はチューリングマシンに対して考えられることが多い。しかし、現実のコンピュータはメモリが有限しかないから、これは本当は「有限オートマトン」（基本情報処理の試験にも出るから知っているはず）とよばれる非常に単純なモデルで表せてしまうものだ。これの能力は余りにも限られているので、たとえばカッコ対応問題（たとえばCやJavaで"{"と"}"の数が釣り合っているかを確かめる問題）すらも一般的には解けない。実際、メモリ内で表現できる最大の数以上のカッコを与えてやればいい。もちろん、そんな沢山のカッコを与えるなんて現実には無理だけどね。
そういう風に、アルゴリズムについて理想と現実の壁は大きく、常に実用化の壁というものがつきまとう。そういう意味で大矢氏の新暗号が本当に画期的なものになるのかどうか、これはやってみないとわからないと思う。今後の展開に期待だね。
生半可な知識で下手なこと書くもんじゃないですね。専門家からのご批判を頂きました。
http://d.hatena.ne.jp/smoking186/20080412/1208008068
というわけで、この記事は反面教師として下さいませ。この記事単独では、間違ったことは書いてないつもりですが、前提を理解していませんでした。
チューリングマシンといえば、オセロは万能チューリングマシンになり得るのだろうか。
オセロの駒が白か黒の状態を表すことは確かなので、１つの駒が１ビットの情報を持っていると考えれられる。だが、最近発表された最小構成の万能チューリングマシンは２つの状態と３つの色を必要として、これ以下ではダメなようだ。
だが、オセロの駒が無い状態を盤面の緑とすれば３つの色が実現できる。ということは、オセロによって万能チューリングマシンを構成することも可能だ。そこに知性が発生することも科学的にあり得なくも無い。
