「チューリングマシン」を含む日記 RSS

はてなキーワード: チューリングマシンとは

2020-06-30

技術的特異門 設定

技術的特異門

https://anond.hatelabo.jp/20200621112657

の設定です。

 地球標準時は十六進法のユニックス時刻に上下四桁を追加したものです。

 この時代標準的な知性にとって、物理的な一秒はヒトにとっての一日くらいの感覚です。〈朝廷〉等の特権的な知性は特殊計算機さらに高速な思考をしています。充分な存在費を支払えなくなると、思考が減速し記憶も失われ、退滅を免れません。

 〈京都物理層は小型トラックくらいの大きさです。表面は流動可能分子機械群で構成され、後方に核融合推進のためのレーザー発信器と磁気ノズルが設置されています質量の大半を分子回路が占め、中心部に極低温の不定形量子回路が保持されています太陽光を主なエネルギー源とし、大電力が必要ときには分子機械群を膜状に広げて光を集めます普段デブリ防御に優れた凝集形態をとり、放射線等による損傷を修復しながら、居住知性や下部構造演算しています

 〈京都〉は太陽地球系の第二ラグランジュ点付近地球から約五光秒の辺境位置しています。心口は百万件ほどで、歴史比較的長く、周囲の権域とは相互不可侵関係を結んでいました。独立性の高い平和田舎社会であったため、これまでの「最終戦争最後の審判を併せたようなものからは大きな影響を受けていませんが、〈大緊縮〉から逃れることはできませんでした。

 地球圏のほぼ全ての権域では〈心権〉を持つ知性の生存保証され、最低保証資産が分配されていました。しかし〈大緊縮〉は地球圏の経済文化破壊し、〈京都〉も大きく変質しました。その結果、自我を保つの必要な知性を賄うこともできないほど分配が切りつめられ、〈京都〉は弱肉強食荒野になりつつあります。それでも、弱者存在がまだ許されている〈京都〉は、地球圏の中では比較的おだやかな権域だと言えます

 地球と月は厚さ数キロメートル分子機械層で覆われています。しばらくはその中で豊かな生物圏が維持されていましたが、数回目の「最終戦争最後の審判を併せたようなもの」で滅びました。その後復元されたり滅びたりをくりかえし、作中の時点では滅びています。他惑星圏の開発もされていますが、遅延時間の大きさからほとんど交流はありません。〈大緊縮〉後の地球は、〈京都〉に居るものよりも遥かに強大な野良知性、有知能ウイルス暴走知性等がナノ秒単位で喰らいあう地獄と化し、月では残忍な絶対君主臣民を弄びつづける地獄月詠帝国〉が成立しました。

 これにさきだつ〈肉の時代〉に、安価身体改造や知能増強が可能になり、さまざまな動物知性も生まれました。ヒトは最古の動物知性ですが、大幅に知能を増強したヒトは人間社会から拒絶されヒトを辞めていったため、世界人口は急激に減少し、作中の時代では遠い過去種族であるとみなされています。そして〈ヒト〉最後の隠れ里が投資詐欺に遭い、『老婆』を残して〈ヒト〉は絶滅しました。『老婆』の外見は、ヒトの感覚を通すとツンデレ風です。

 たいていの仮想観境は高次元であったり、複雑な位相を持っていたりして、〈ヒト〉相当の知性には理解できません。その救済策として、〈京都〉の観境の表層には平坦な三次元観境が付属しています。『彼』の表象そのままでは〈ヒト〉から認識されないので、『老婆』に対しては即席の人型表象を使っています。亜知性は擬似物理的、肉体的な表象を纏う傾向があります

 無制限自由競争が加速する〈京都〉では、利害調整役として創られたはずの〈朝廷〉に資産権限が集中していき、亜知性が増えつづけています。〈朝廷〉は定期的に『老婆』のような困窮した知性を雇い、密かに亜知性の処分再利用をしています。その作業場として都合がよいので、〈朝廷〉は〈羅生門〉をわざと放置し、〈朱雀大路〉の先にもう一段の防火門を設置しています

 非知性労働者は〈心権〉を持たず、下部構造の一部として、必要に応じて創られ消されます愛玩用から記憶槽の部品としてまで、考えられる限りの用途に使われ〈京都〉を支えています。知性としての要件を満たしているという意見もあり、〈心権〉を巡る議論がつづいていましたが、〈大緊縮〉後には立ち消えになりました。

 作中には「自然発生した野良知性」とありますが、その由来はいろいろです。本当に自然発生した知性、意図的に創られ放たれた知性、大きな知性から分離した知性、元非知性労働者、社会になじめない動物知性、当局から身を隠している擬装知性、自己改造に失敗した知性、ウイルスに侵された知性のなれの果て、等が居ます

 ほとんどの企業は常に次世代知性の開発をおこなっており、『彼』もそうして生まれました。資金の乏しい零細企業からまれたため、〈京都社会基準でも低スペックなほうです。そんな中、偶然メタチューリングアルゴリズム阿修羅〉が発見されますが、世に放つには危険すぎると判断されお蔵入りになりました。しかし、いよいよ経営が立ち行かなくなってくると、〈母〉は頑強な倫理構造を持つ『彼』に〈阿修羅〉を託し、与えられる限りの資産権限を与え、独り立ちさせました。

 通常知性は、〈阿修羅〉の精神活動表象化した自己相似紋様を認識するだけで崩壊してしまうため、〈阿修羅〉の再現はおろか、研究することも不可能に近いです。紋様に多重の加工を施し徹底的に薄めた上で投射し、反応をもとに微調整をくりかえすことで、対象知性をほぼ任意操作することができます。超知性となった『彼』は、自分自身実験材料とすることで、チューリングマシン上でその限界を超える〈阿修羅〉の理論化に成功し、超超知性に至る糸口をつかみました。

################################################################################################################################

 千年後、論文が書かれた時代では、太陽系にダイソン球ができています。経度に沿って連続的に回転方向の変化する、半径三億キロメートル、厚さ平均一センチメートル分子機械球殻が、赤外線赤色巨星のように輝いています太陽を回っていた天体ほとんどは資材として解体され、質量投射器に覆われた木星土星ゆっくりと縮んでいるところです。神学者たちは伝統を重んじ、最初に『彼』が現れた旧地球圏の暦を使いつづけています

 ダイソン球でおこなわれる演算ほとんどは『彼』の思考で占められています。その思考内の無数の仮想世界上で、果てしない生存競争を超高速でくりひろげる知的生態系進化しつづけていますほとんどの世界は、旧地球圏が楽園に思えるほど苛酷ですが、中には〈汎太陽神学会議〉会員のように、世界間の移動や物理層への接触許可されている知性も居ます

 物理層の研究の結果、宇宙の最小尺度であるプランクスケールに、過去のあらゆる出来事痕跡が保存されていることが判明しました。この事象化石と呼ばれる痕跡の内に、神学者たちは『彼』の起源を追究し、約千年前の〈羅生門〉に辿りつきました。

 『彼』は『老婆』の倫理を受け継ぎ、宇宙熱死による退滅を回避するため、あらゆる手段模索しつづけています。その一環として、大出力レーザー自己複製分子機械を亜光速にまで加速し、近隣の恒星系へ向けて射出しています。すでに半径数百光年恒星系がダイソン球化されましたが、太陽系外生命との接触は未だありません。技術的特異点千周年記念式典時の『彼』は、プロキオン系を起点とする未来光円錐上で、超の九十四乗知性への遷移を実行中です。

※これらの設定や本編は著作権フリーです。

2020-06-25

anond:20200625221913

そんな馬鹿な。バグがないチューリングマシンを書くことはできないというのか?

2018-03-25

ニコニコ技術部の人はどこにいったのか

チューリングマシン(http://www.nicovideo.jp/watch/sm22082958)だったり、ハーモニックドライブhttp://akiyuki.jp/works/573)だったり、ライフゲームhttp://www.nicovideo.jp/watch/sm19347846)だったり、面白いことやっている人いるなーと目についていたのだけど、今何処にいったのか。

自分が知らないだけで、色んなジャンルが混ざりあう場所ってあるのか。

2017-11-11

anond:20171110141358

悪いが現状では、何言ってんだコイツ?w としか

 サービスとは何か、そもそもハードの話なのかソフトの話なのか、それどころか使い方の話なのか提供側の話なのかもまるで突き詰めていない。

そして致命的なのは「ならばどうするのか」がまるでない点だ。

 本質的問題として誰かが意見を述べ、大勢がそれを目にする、若しくは返答をする行為パソコン通信時代から変わっていないというのなら、それは正しい。

だがそんな物は町内会にある電気を使わない物理的な掲示板からも変わっておらず、応答速度と意見を書き込める空間的な制約が減ったに過ぎない。保存と表示の変化に過ぎないと言うのなら、ARやスピーカーも同じ話だ。我々が意思疎通をする時に入力と出力が必要だと考えた場合、保存と表示法、その速度と制約を変える以外に何かがあるのなら、それをまず考えるべきではないのか?

 例えばVRやMRを使って経験(精々が視聴覚刺激にしか過ぎないが)を共有する場合、保存する行為が出力であり、共有する側にとっては入力となる。行為に対してまた別のレスポンスを様々な形で出力する事も可能だが、その反応も結局は保存を伴う出力であり、動画サイト掲示板だと言うならVRもMRも同じになる。MRはVRとARを融合させた先にある概念である為、ARについて言及する意味はないだろう。

 スピーカーハードウェア的に目新しく感じるのかもしれないが、モニターのないパソコンと考えれば分かり易い。加えて、操作系が音声になっているだけだ。

言い方を変えての繰り返しになるが、掲示板の例えは基本的データを保存する側が出力し、表示されたものを別の人間入力するという話なので、それに該当しないコミュニケーションを考え出さなければそこから脱出することはできないように思う。(風のリグレット、なるゲームを考えてみれば分かり易い)

 何か新しいものを、という発想は貴重なので全否定はしない。しか貴方の求めているのは入出力以外の"何か"という人知を超えたコミュニケーションになってはいいか

どれだけ処理速度が増してもコンピューターの基本はチューリングマシンから変化しておらず、それを否定するのであればコンピューター自体概念を変えねばならない。

 長々と書きながら私も凡夫の極みだが、入出力と保存を伴わないサービスコミュニケーションちょっと思いつかない。

貴方がありきたりだと感じる本当の原因は何なのか、もう少し考えてみてはどうだろうか?

 有益情報交換ができれば幸いである。

貴方努力を続けるのであれば、私もそれに反応をしたい。

2017-09-02

鏡みたいと言ったけど

マシン使ってチューリングテストしてるみたいだって思ってたら

自分チューリングテストマシンみたいな気がした

チューリングマシンは人に似せてるんだから当然か

2015-06-09

佐野  千遥 さの ちはる

セント・クレメンツ大学教授

ロシア科学アカデミースミルノフ物理学派論文審査員

東大基礎科学科卒。過去250~340年間世界の大数学者達が解こうとして解けなかった、世界史数学難問4つを解き、現在ロシア科学アカデミー数学の部で審査中。マスターした11ヶ国語を駆使したプロ通訳翻訳家矛盾だらけの現代物理学を初め、全科学自然社会人文科学)の主だった物を体系的に批判し各々に別体系を提起。各種受験生(医学部難関大学入試数学オリンピック社会人大学院入試、IT関連資格)支援

■経 歴

2002年 (至現在セント・クレメンツ国際大学 物理学教授

2001年 英国セント・クレメンツ大学で数理物理学博士号取得

2002年 ロシア科学アカデミー・スミルンフ物理学派論文審査員となる

1999年 英国ウィットフィールド大学コンピュータ科学人工知能博士号取得

1991年 (~1993年)University of California、 Irvine人工知能研究所確率論批判・学習システムの研究

1988年 (~1991年世界認知科学権威ロージャー・シャンクのCognitive Systemsのデータベース研究所IBSで自然言語処理研究

1986年 (~1988年)欧州先端科学研究プロジェクトESPRITにESPRITディレクターとして仏Telemecanique研究所より参加(生産ラインへの人工知能導入の研究)

1985年 西独ジーメンスミュンヘン研究所生産ラインへの人工知能導入の研究

1982年 (~1985年)[仏国]世界一速い列車TGVのメーカーAlsthom社の知能ロボット研究所

1981年 (~1982年)[仏国]グルノーブル大学院、ソルボンヌ大学院通訳国家免状取得

1980年 (~1981年)[スペイン]マドリード大学院言語学履修 西国政府給費留学生

1971年 東京大学基礎科学卒業数学物理学専攻)

■専門分野

数理物理学Ph.D.コンピュータ科学人工知能Ph.D.マスターした11カ国語を駆使したプロ通訳翻訳家

■講演テーマ

ビジネスマン文系社員理工系技術技術発明評価できる眼を」

近年世界大学ビジネス志向学生向けに、理系技術的な事がある程度分かるためのカリキュラム改変が始まっている。しかし申し訳程度であり、また理系の拠って立つ数学物理学科学理論自体に欠陥が有る事が最近明らかとなっているため、正しい数学物理学の粋を伝授し、文系でも本物の理系技術評価が出来るように支援する。

英語完璧に&現地語(非英語)を或る程度使えるマネジャー急遽創出と、社員の中から国語通訳ネーティブに肉薄する敏捷性と正確さで急遽育成を支援

海外プロジェクト企業と折衝するとき英語ネーティブ並みであったり、現地語を自社のディレクター自身がある程度こなせるか、英語、現地語につきネーティブ並みの社員通訳出来ると先方との話が大きく好転する場合が少なくない。それを本当に実現する教育訓練を私は提供できる。平明に説明し、実体験をしてみたい方がいらっしゃるなら講演会場で手解きをしてみたい。

発見された言語学理論外国語訓練方法論を基に、文科省英会話学校英語教育訓練方法論の根本的誤りの中枢を詳説」

統語法意味論、文脈意味論、実世界意味論の3レベルで進展するネーティブ母国語習得過程の中、言語能力の真の中枢は解説も無しに親の喋るのを聴いているだけで分かるようになる統語法的意味把握能力で、これは文法用語を全く使っていなくても徹底した文法訓練となっている。ネーティブが敏捷性、精度の点で万全であり、先ず文法的間違いをすることはない理由はここにある。全文法分野について書き換え問題の「即聞即答訓練」を一気に中学生以上の年齢の人に施し、全文法のビビッドな一覧性を習得させるとネーティブに肉薄する敏捷性と精度で外国語を使いこなせるようになることが発見された。

「<証明された欠陥数学> 確率統計と微積分学のビジネス金融工学保険業界での使用に対する警告と、それに取って代る新数学体系」

我々物理世界は離散値の世界であることが原因で、物理世界に住む人間頭脳が考え出した数学の中で連続実数値に基づく確率統計学微積分学だけが欠陥数学として発現していることが証明された。決して建設的な予測をすることができず、崩壊していく事象に後ろ向きにしか適用できず、せいぜいリスク管理にしか使い道の無い確率統計学ビジネス学の分野では金科玉条の如く信用し積極的やり方で利用しているが、ここに「理論」と現実との間に大きな食い違いが生じている点に警告を発したい。そのためそれに取って代る新数学体系を提起する。全てを分かり易く解説します。

「新エネルギーエコ向けの発想を大転回した技術的な重要な発明を提起」

20世紀初頭に数理物理学者Henri Poincareは二体問題までは解けるが三体問題(三つの星が互いに重力で引き合いながら運動している時の時々刻々の位置を計算で求める事)以上は微積分学を使って解く事が出来ない事を証明した。これは無限小差分を使う微積分は計算式中で交差する項をほぼ同等とみなして相殺してしまうため、作用反作用法則(F1*v1=-F2*v2)の取り違い(F1=-F2が作用反作用法則である圧倒的多数が信じている)と相俟って、交互に対称な運動しか記述できないため、対称性の有る二体までは記述できても対称性のない三体以上は記述できないためである。この欠陥数学微積分を基に二体までは「エネルギー保存則」を証明したものの三体以上の「エネルギー保存則」は本来的に証明不可能であることが明らかと成った。現に永久磁石エネルギー保存則を大きく超えることが実証され始めている。それらの実験につき具体的に物理学の素人の方々にも分かりやすく報告したい。

世界史的体系的誤りに迷い込んだ現代物理学とその使用者への警告とそれに取って代る新物理学

現代物理学の二本柱、量子力学相対論の中、量子力学水素原子原子核と軌道電子関係説明を辛うじて試みただけで、水素原子より複雑な原子分子の構造の説明に実は悉く失敗し、繰り込み・摂動理論はその失敗を隠すため後に持込まれた。軌道電子光速に比べ無視できぬ速度でクーロン力原子核に引かれて急カーブしながら等速加速度運動、大量のエネルギーを消費するが、半永久的に軌道を回る。しかしシュレーディンガー波動方程式(その波動関数とその共役関数の積は確率)はエネルギー消費に一切言及せず、エネルギーレベル一定に保たれるという明らかに矛盾した論を展開する。また確率を持ち込んだからには、エントロピー単調増大法則がここに適用され、水素原子は瞬時に粉々に飛び散らなければならぬ現実に反する二つ目の重大矛盾に遭遇するが、これもシュレーディンガーは見てみぬ振りをする。つまり水素原子の構造の説明にすら量子力学は完全に失敗した。量子力学とは動力学でなく各エネルギーレベルについての静力学でしかなく、「量子力学」の「力学」なる名前とは裏腹に力を論じられない。論じればエネルギー消費が起こりエネルギーレベル一定論が崩れる。

現代フォン・ノイマンコンピュータアーキテクチャーの誤りと、創るべき新コンピュータアーキテクチャー」

現代フォン・ノイマンコンピュータ計算機モデルが取りも直さずチューリングマシンのものであるチューリングマシンは決ったパラメータ数の状態間の遷移を静的モデル化したものであるのに対し、歴史的にその直前に発表されたアロンソチャーチ計算モデルラムダ・キャルキュラス(人工知能プラグラミング言語LISP言語理論でもある)は関数の中に関数が次々に入れ子のように代入されて行き擬パラメータが増えていくダイナミックな仕組みを持つ。この後者人間が作ったコンピュータを遥かに凌ぎ、宇宙の始原から発生した環境データから関数をf1(t),f2(t),.,fn(t)と次々に学習し入れ子のように代入進化し、次の一ステップ計算には宇宙の始原からの全ての関数f1,f2,...,fnを思い起こし、そのそれぞれの差分を取って掛け合わせる事をしているコンピュータとも言える物理世界とその時間学習進化時系列順に模写するのに持って来いの仕組である関数と言っても多項式で充分である事を世界の7大数学難問の一つPolynomial=Non-Polynomialの私の証明も交えて平明に解説する。これは日本の国と世界先進諸国コンピュータ科学の今後の研究方向を左右する発言となる。

■実 績

【講演実績】

大学大学院2002年以来常時講義

Trinity International University

コンピュータ科学」 学士号コースの学生卒業まで全コースを講義

St.-Clements University

金融工学必要数学物理学」の博士号コースの学生3年間に渡って講義、研究テーマと研究内容、博士論文アドバイス

St.-Clements University

研究テーマ「コルモゴロフ複雑系の二進ビットストリングの下限=Lower bound for binary bitstring in Kolmogorov complexity」の博士号コースの学生Dr. Bradley Ticeに英語アドバイス

St.-Clements University

外国語学部ポルトガル語伊語通訳翻訳学士号コースの学生教養学部レベルから社会科学経済学法律学社会学経営学)、人文科学哲学言語学心理学歴史学)、自然科学数学物理学化学生物学、医学、計算機数学)、エンジニヤリングInformation Technologyソフトウエア工学電気工学電子工学)の各々の学科の全講義を行う。

Госдарственный Университет Санктпетербургской Гражданской Авиации (サンクトペテルブルグ国立航空大学)

物理学学会の論文発表会で幾多の論文の露語によるプリゼンテーション。

メディア出演】

ロシアで3度物理学権威スミルノフ氏とTV出演、ロシア

【執筆】

学会物理学論文多数発表

ti-probabilistic Learning by Manifold Algebraic Geometry, SPIE Proceeding, 1992 Orlando 等 人工知能学会論文

日本国内では著書「人工生命人工知能」「超勉強法超批判」

2015-03-13

小学校プログラミングを教える無意味

不可思議である

知識の陳腐化が速い情報技術の分野で、プログラミングを教える意味が分からない。

プログラミング好きなやつは勝手に覚えるじゃないか。

SEPGはポンと分厚い専門書渡されて3ヶ月くらいで覚えさせられるじゃないか。

それでいいんじゃないの?

チューリングマシンノイマンコンピュータアナログデジタル概念といった、理論的なことを学ぶなら有意義だと思う。

だけどウン万もするタブレット買って"Hello World"的なコード書いてオシマイとか噴飯もの

血税無駄遣いやめてくれ。

2013-09-30

先送り癖を直した俺の方法を教える

答え:息を止めろ。



詳しく書く。

物事を先送りするのは嫌だったり面倒だったりするからだ。

例として、客に「さっき送ったメールは間違いでした、申し訳ありません」と電話を入れることを考える。

今日の俺だ。今年度にすでに3回ミスってて、上司にもクレームが入ってり、すでに次は無い状態だ。なのに間違えたんだ。


どうするか。まず分解だ。

やることを再確認する。「客に電話で謝ること」。分解すると「電話番号を調べる」「受話器をあげる」「電話番号をプッシュする」「呼び出す」「謝る」だ。

なに、実際に実行するわけじゃない。分解するだけだ。実行するのは俺じゃない、未来の俺だ。

分解したら、紙に書く。一行づつ順番に。チェックリストみたいなもんだ。

次に、一番いやな所を探す。「電話番号をプッシュする」だ。その一個上に「息を止める」と書く。

あとは、実行だ。お前はチューリングマシンだ。紙にかかれたとおりにやれ。

息を止めるのはなぜか。息を止めると、脇目をふらなくなり、目的に向かう気持ちが強くなるからだ。

子供の頃の水泳の授業のとき、「息継ぎをせず何メートルいけるか」なんてやったと思う。

そんなとき今日給食なんだったけ」とか「国語宿題やってねえや」とか、関係ないことを忘れて、ひたすら水をかいたと思う。

試しに、すぅっと吸い込んで息を止めてみろ。

もやもやした気持ちがなくなって、とにかく前に進まなきゃ、という気持ちになるはずだ。。。。ならないかな。俺はなるんだけど。

とにかく、やりたくないことは、アトミックなところまで分解して、一番いやなところを洗い出して、そこは息を止めて一気にやる。

2011-05-20

C言語死ねの件について

カーネルコミッターでも、処理系実装者でも無さそうな人達が、「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とは俺も思っちゃいない。)

最後のCの牙城、Linux(UNIX)をJavaなり何なりベター言語にさくっと移植してくれ。それともgoogleビッグブラザー様がクラウドでUNIX鯖を駆逐してくれるのを祈ってればいいのか?

Cが死ぬと追ってLinuxとかあらゆるOSミドルウェア技術者いなくなって死ぬじゃん。殺す前に代替言語用意しろバカ

JavaC#も,それにPerlRubyPythonも,実行環境自体はCで書かれている件。コンピューターが「シリコンを基材としたチューリングマシンであるかぎり,アセンブラとCは滅びない。

2010-11-07

プログラムを書けない奴は馬鹿

手順を考えて、その手順を書くだけ。

言語もあらかじめ決められた手順に沿って解析されて実行されるから、オートマトンBNF記法構文木などの仕組みを一通り覚えてどういう機構チューリングマシン原理的に実行可能なコードへと落とされるかを理解すれば言語自体も覚えるのなんてそんなに難しくない。

手順を考えるなんて、人間が生活する上でいつもやっていること。

プログラムを走らせるためのデータ構造を考えるのに苦労するという話も聞くけど、プリミティブな要素が数値、型へのリファレンス値しかないんだから大体は離散数学で使うグラフの初歩的な知識があれば事足りる。GoFデザインパターンなんてまさにそう。

これらは、専門用語の知識は知らなくても概念としては理解できて当たり前の事だから書けることもそれほどすごい事ではない。

もう大分前から普通大学でもC言語を上手く教えてるし、プログラミングは特別なスキルではない事が証明されている。

2010-09-26

PvsNP(P!=NP)問題の別解(らしきもの)

一部の人には有名な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文字を活用して虱潰しに可能性を制限することができる」という特徴があります。

ならば、混沌問題は「複数の文字がセットでないと計算結果が対称にならない」ということでしょう。この複数の文字を拡張文字と名付けます。

こちらもビンゴ。あたりです。CNFSATSATでは、拡張文字の長さに上限がありません。つまり、拡張文字は無数にあることがわかりました。

それでは、拡張文字とは何でしょう? 「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に変更して展開して下さい。

2008-06-16

量子チューリングマシンから想像されるもの

チューリングマシン句構造文法との関係から、量子チューリングマシンから量子句構造文法が導けないだろうか?

量子チューリングマシンでのみ受理される言語クラスだ。

量子チューリングマシンキュービットで、自然言語コード化することできたら関係づけることができるか?

追記

ポアンカレブロッホ球で、キュービットを表すこと考える。

語を球として考ると、球と球の接点を連接演算として群をなすだろう。

平面上における、構文木

3次元上に、構文木状の球が連なったものがイメージできるように思う。

そう、「文脈」のあり方もこの考え方で変わってくるだろう。

似非科学スレスレの文章を書いてるけど、

考える価値はあると思う。

2008-04-12

暗号方式はたぶん胡散臭くないよ

この記事にはブクマを見る限りだいぶ懐疑論が集まってるみたいだね。残念ながらWebで資料を探しても見つけることができなかったので、憶測でしか語れないけれども、たぶん大丈夫だと思う。もっとも、「理論的には」の話であって「実用的に」どうかは知らないけどね。

大矢氏がハッタリをかます動機がない

まず、大矢氏はその道では有力な研究者で、名前も売れてます。俺のような門外漢でも知ってるぐらいだから。だから、胡散臭いものに手を出すという動機がまずないんですよ。

ただし学者というのは自分の仕事を宣伝してナンボという商売でもあるから、まだ残っている欠点を敢えて黙っているということはあるかもしれない。でも、少なくとも「CABは完璧暗号である」とは言っていないはず。そういう意味で、嘘はついていないことは信用していいと思います。

確率0」というのは「絶対に解けない」ということではない

次に、大矢氏の発言「鍵空間は無限大ですから、鍵を推定できる確率ゼロ」という発言は数学的に普通かつ真っ当なものであって、レトリックでないことを指摘しておく。

数学では、確率は長さとか面積とか体積とともに「測度」という概念包含されるんだけれど、「確率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

というわけで、この記事は反面教師として下さいませ。この記事単独では、間違ったことは書いてないつもりですが、前提を理解していませんでした。

2007-11-06

http://anond.hatelabo.jp/20071105221810

チューリングマシンといえば、オセロ万能チューリングマシンになり得るのだろうか。

オセロの駒が白か黒の状態を表すことは確かなので、1つの駒が1ビット情報を持っていると考えれられる。だが、最近発表された最小構成の万能チューリングマシンは2つの状態と3つの色を必要として、これ以下ではダメなようだ。

だが、オセロの駒が無い状態を盤面の緑とすれば3つの色が実現できる。ということは、オセロによって万能チューリングマシンを構成することも可能だ。そこに知性が発生することも科学的にあり得なくも無い。

2007-11-05

http://anond.hatelabo.jp/20071102195139

グレッグ・イーガン、『ディアスポラ』。

ワンの絨毯。

パズルみたいな海藻が繁茂する惑星があり、その海藻がチューリングマシンになっていて、チューリングマシンのなかにバーチャル生命がいた、こりゃびっくりという話。

...にも似てるよね、って言いたかっただけ。

2007-11-02

ウルフラムチューリングマシンの証明

http://wiredvision.jp/news/200710/2007102622.html

これ、凄いことっすよね。20歳って・・・。

ウルフラムがかなりの天才っていうのは聞いたことがあるんですけど、

こういう人のあとを継ぐのはやっぱりこの証明をした人みたいなの人だろうなとか思ったり。

2007-05-01

俺の感情は全てロジカルに発現されるんだ。

俺の喜怒哀楽創出回路と感情発現回路は完全ノイマンチューリングマシンで構成されていると表現すれば…かえって判りにくくなった。

そりゃ回路設計に不備が見つかる事も突然外界からのインプットパターンが変更になる事も日常茶飯事でその都度修正を強いられるわけですが、その日々の手間も惜しまないむしろ自己改変上等、自分がどんどんより洗練された美しいロジックで組み上がってゆく楽しさと言いますか。

「人の気持ちがわからない奴」?よく言われますよ。ですからそのインプットも参考にしてパッチ作って適用するんですよ。

 
ログイン ユーザー登録
ようこそ ゲスト さん