MetaNest あねっくす このページをアンテナに追加 RSSフィード

平和でなく▽静かではある
生きて行くうちに▽出会ったとしたら▽こんな時間帯を▽信じてはならぬ
「赤々丸」(内田 美奈子)拾伍・平和でなく静かであり より
Squipper ( http://metanest.jp/squipper/squipper.xhtml ) のサンプルに使う画像を募集しています。詳細はリンク先を
「彁」の用例をもしご存知のかた、おられましたらご一報を(コメント欄でもなんでもいいです)

プロフィール

はてなアイデア提案中。よろしく
i:21132 i:22380
1970 | 01 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
2008 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 |
2016 | 07 | 10 |

2007/Apr/25(水) 2007/Apr/25(水)

更新情報

更新情報を含むブックマーク 更新情報のブックマークコメント

特報!

パーソナルメディア(株) にて、「μTRONキーボード」発売開始

画面の権利

画面の権利を含むブックマーク 画面の権利のブックマークコメント

セキュホmemo経由でITpro - 意匠法改正の波紋---ゲームの一画面は知財保護の対象になるのか?

うっわ。プログラムの動作画面って昔っから情報誌出してる出版社ソフト屋が圧力掛ける手段にしたり、いわゆる「ルックアンドフィール」訴訟ネタになったりと、コンピュータ業界のロクでもない波風の原因になってきたのに、ここへ来てそういうことをしやがりますか

しかもこの記事の結論だと、インタフェイスデザイン排他的に独占する根拠を与えることになるみたいだけど、それってユーザロックインされて完全に一方的に不利益を被るんじゃないか?

次もしこのへんのパブコメの機会があったらきっちり盛り込もう

文部省ってさ

文部省ってさを含むブックマーク 文部省ってさのブックマークコメント

全国学力テスト、参加しません。

全国学力テスト、参加しません。

なんかこう地方の事情って奴を無視して、とにかくひたすら何かを全国的にゴリ押しってのが得意技だよね

チューリングマシン語り 後半

チューリングマシン語り 後半を含むブックマーク チューリングマシン語り 後半のブックマークコメント

http://metanest.jp/tm/tm.xhtml にまとめました

id:metanest:20070424#turing の続き

停止問題

あるチューリング機械についてテープ記述すること、あるいはその記述を入力として受け取るようなチューリング機械が存在することから、次の議論を始めることができる

「あるチューリング機械に、ある入力を与えた時、停止するかしないかを判定するチューリング機械は可能か?」

これが「チューリング機械の停止問題」である

答えは「否、存在しない」で、おおざっぱに説明すると以下のようになる

(疑似言語として Ruby 風の表記を使っていますが Ruby ではありませんので注意)

(1) 仮に、そのような機械が存在するとする。すなわち、機械の記述を m、その機械への入力を i として、以下のような関数 terminate? が存在するとする

terminate?(m, i)  # m(i) が停止するならば true 、しないならば false を返す

(2) この terminate? を使った、以下のような関数 t を考える

def t(x)
  if terminate?(x, x) then
    loop {}  # 無限ループ
  else
    stop  # 停止
  end
end

(3) この t に t 自身を入力として与えた場合を考えてみる

t(t)  # ???
  • t(t) が停止すると仮定 → terminate? の定義により true が返る → 無限ループで停止しない
  • t(t) が停止しないと仮定 → terminate? の定義により false が返る → 停止する

という矛盾する結果が導き出される。よって、(1) のような terminate? は存在しない //

チューリング完全

チューリング機械で、なんであれシミュレーションできる、ということから、例えばプログラミング言語において、任意のチューリング機械を記述できる能力があれば、なんであれ記述できる、ということになる

(その結果がわかりやすいか、効率的か、といった点を無視すれば。また、無限の長さのテープについては、適当な長さでよいとする)

そのような「任意のチューリング機械(万能チューリング機械、と言い替えることもできる)を記述できる能力がある」ことを、「チューリング完全」という

どれくらい単純なプリミティブで、チューリング完全を達成できるか、という問題が注目された時期もあった

http://esoteric.voxelperfect.net/wiki/Turing_tarpit

また、現代でも、何らかのメカニズムがチューリング完全か否かという問題は時に面白い議論となる

参考文献他

ファインマン計算機科学

ファインマン計算機科学

物理学者ファインマンさんによる計算機科学の教科書

「計算可能性」の導入からはじまり、有限状態機械、チューリング機械、万能チューリング機械、停止問題が説明され、最後に計算可能性に関わる問題が提示されている

ミンスキーさんによる万能チューリング機械が示されている

NACSIS Webcat BN00375778

古い教科書だが、大学図書館などにはあると思う

チューリング機械についての紹介。高橋秀俊さんによる万能チューリング機械が示されている

(未確認)

目次 http://www.saiensu.co.jp/?page=book_details&ISBN=ISBN978-4-7819-1104-5 によると万能チューリング機械の解説がある模様

コンウェイさんのライフゲームで、万能チューリングマシンが実現可能との記述があったように思うのだけれど手元に無くて確認できず...

ライフゲイムの宇宙

ライフゲイムの宇宙

これも手元になくて確認できないのだけど、チューリング完全に関する話がもしかしたらあったかも

(非参考文献)

長門有希も読んでた本書には、まさしくこの分厚い中のどこかにありそうなテーマであるにもかかわらず、万能チューリング機械についての直接の説明は見つからず(索引に「チューリング・マシン」はあるが、「万能――」はなく、関係のありそうな語のあたりをいくつか探してみるもありませんでした)。停止問題は関数で説明されている

トラックバック - http://d.hatena.ne.jp/metanest/20070425