安敦誌


つまらない話など
by antonin
S M T W T F S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30
検索
最新の記事
アキレスと亀
at 2017-05-02 15:44
受想行識亦復如是
at 2017-05-02 03:26
仲介したことはあまりないが
at 2017-04-29 03:36
サンセット・セレナード
at 2017-04-12 23:17
水分子と日本人は似ている
at 2016-06-04 01:49
ほげ
at 2015-06-05 03:46
フリーランチハンター
at 2015-04-17 01:48
アメリカのプロテスタント的な部分
at 2015-04-08 02:23
卯月惚け
at 2015-04-01 02:22
光は本当に量子なのか
at 2015-03-17 23:48
記事ランキング
タグ
(295)
(146)
(122)
(95)
(76)
(65)
(59)
(54)
(45)
(40)
(40)
(39)
(32)
(31)
(28)
(27)
(25)
(24)
(22)
(15)
最新のコメント
>>通りすがり ソ..
by Appleは超絶ブラック企業 at 01:30
>デスクトップ級スマート..
by 通りすがり at 03:27
7年前に書いた駄文が、今..
by antonin at 02:20
助かりました。古典文学の..
by サボり気味の学生さん at 19:45
Appleから金でも貰っ..
by デスクトップ級スマートフォン at 22:10
以前の記事

BFから始まる妄想

睡眠不足のところに深酒をしてしまい、あちこちの電気をつけたまま眠って変な時間に目が覚めてしまった。相変わらずBrainfuckが可愛すぎて生きているのが辛いのだけれども、一時のような過剰集中の時期は去って、興味の対象はいろいろと拡散している。けれども、単純な言語処理系から少しずつ複雑なものに仕上げていく過程を経験してみると、いろいろと得るものがあって面白い。

個体発生は系統発生を繰り返す、という名言があって、多細胞生物が成長する過程というのは、その生物の進化過程となんとなく似ているという説がある。人間も、280日目くらいに生まれてくる頃にはだいたい人間の姿をしているけれども、初期の胎児はシラスみたいな形をしている。そういう時期になると、人間も犬も猫もコウモリも、胎児の形状はだいたい似通ったものになっている。もっと遡れば、自称高等生物である人間も、原始海水を模したと言われる羊水に浮かんだ単細胞の受精卵から始まっている。

進化が漸進的に高度なプロセスを獲得してきた過程だとすると、高等プロセスの動作には低位のプロセスがひと通り動作する環境が必要になるのだから、古いシステムを一度作り上げてから一つだけ新しいシステムを作るということを繰り返すという方式は理にかなっている。あるプロセスのビルドプロセスにのみ必要となり、ビルド後はデストラクトされるプロセスなどというものもあるだろう。進化の過程で退化した仕組みが、個体発生の一時期だけに見られるというのも、理にかなっている。PCなどでも、システム運用中にはもはや使わないような古いシステムを、起動時の貧弱な環境下で利用するためだけに保持しているなんということが見られる。

BFのひどく単純な処理系を少しずつ複雑にして実用度を上げていこうという工夫は、言語処理系の個体発生過程を見ているのだとも言えると思う。それは過去の言語処理系がたどった発展の歴史と完全に一致はしないものの、そういう時代のソフトウェア技術者がどんなことを考えながら現代的な処理系を仕立てあげていったのかという理屈の一端を体感することができる。言語処理系の系統発生をなぞるようにして、自分の言語処理系の個体発生を体験してみるのは楽しい。

BFの言語処理というのは、現代的な機械語よりも一層低水準の記述レベルしか持っていないので、どちらかと言うとソフトウェアの発想よりはハードウェアの発想と親和性が高い。もちろん、基本的な仕組みが並列手法のディジタル回路ではなく逐次手法のチューリングマシンなので、直接の対応は取れないのだけれども、極端に単純な処理を膨大に組み合わせると結局は複雑なこともできるというのは、ハードウェア的な発想だろうと思う。

チャーチ・チューリングのテーゼというのがあって、チューリング完備なマシンがあれば、計算可能などんな問題も解ける。BFというのは、十分な量のメモリと、十分な処理時間があれば、チューリング完備の条件を満たす。それからブール代数系というのがあって、ANDとORとNOTという3種類の論理ゲートがあれば、それらを十分な量だけ用意すれば、計算可能などんな問題も解くことができる。表現方法によると、NANDかNORか、どちらか一つだけあればANDもORもNOTも作れるので、要するにNANDだけがたくさんあれば、どんな計算もできることになる。こういう性質がBFとディジタル回路で似ている。

ディジタル回路の最も基本的な演算はANDとORという二項演算だけれども、BFではインクリメントとデクリメントという単項演算がこれに相当する。以前、加算から乗算、累乗と発展させる方向を延長して、テトレーションとかペンテーションとかいうハイパー演算について考えたことがあったけれども、こういうn階のハイパー演算の最下層は、1階のハイパー演算である加算ではなくて、0階のハイパー演算である、インクリメント演算ということになる。2を1回インクリメントすると3になるが、2をインクリメントするという演算を3回繰り返すというものをマクロ表現した関数が、2+3=5という加算だと定義できる。

加算には逆演算として減算があって、乗算にも逆演算として除算が、同様に累乗にも累乗根がある。この話は後でちょっと別の展開をしたいけれども、今はBFの話に限定すると、デクリメントというのが0階のハイパー演算であるインクリメントの逆演算ということになる。なのでBFは逆演算を持った可逆的な0階ハイパー演算系を完備していて、その単純な繰り返しによって加減算でも乗除算でも累乗でもテトレーションでも、初等関数の範囲に収まるどんなハイパー演算でも(膨大な繰り返し回数さえ実行できれば)実行できる。

整数の集合と0階ハイパー演算の組はある種の代数的構造を構成するはずなんだけれども、普通の数論で使われる代数的構造は加算のような2項演算を持つようなものしか想定していないので、単項演算しか存在しないような自明な代数系については、代数系の範疇には入らずに単に全順序集合という性質を持つ集合の一種として分類される。一方ブール代数の方は、数値の集合は0と1の2要素しかないが、演算の方は一応ANDやORという二項演算を備えているので、束(lattice)という代数構造が定義されていて、ブール代数はその一種であるとされている。

現代的な文法を持った高水準言語でソフトウェアを書いている感覚では、加減算とか乗除算はアプリオリな基本演算であって、それ以上は分解不可能なものなのだけれども、基本論理しか持たないディジタル回路だとか、インクリメントとデクリメントしか持たないBFなんかを扱っていると、乗算や加算それ自体がハイパー演算であり、その実装というのも素朴なものと高度なものでは効率が随分と変わってくるということを体感できる。足し算の方法にも工夫の余地がある、なんてことに気づくのには、このレベルまで降りないといけないのかもしれないと思うと面白い。

BFでは一応8bit整数を要素として持っているので、インクリメントから加算を生み出すことにそれほど選択の幅はないのだけれども、これがディジタル回路になってくると随分と様子が変わってきて、マルチビットの加算器だとか、そもそも全加算器や半加算器の設計ひとつ取ってみても、いろいろなトレードオフを持った複数の設計が考えうる。しかも、論理ゲートよりもう一段下層レベルにある、MOS-FETと配線のレイアウトあたりまで視点を下げると、さらに工夫の余地は広がってくる。

現代的な半導体設計では、その機能のほとんどはHDLで記述されるのだけれども、ソフトウェアの世界にもアプリケーションを書く人とコンパイラそのものを書く人がいるように、ハードウェアの世界にもHDLで機能を書く人と、HDL処理系を書く人がいる。そしてソフトウェアの世界にライブラリやデバイスドライバを提供する仕事があるように、ハードウェアの世界にもRTLレベルでHDL用のライブラリ機能を記述したり、マスクパターンレベルでフィンゲートなどの最新リソグラフィ技術に対応した論理ブロック設計をしたりする仕事が存在する。

そういう水準の仕事を勉強している学生の論文がときどきネット上に転がっていたりして、よくまとまっているので読んでみると面白い。そういうものを読むと、プレーナICの世界ではたった32ビット整数の加算ひとつでも、要求性能によっていろいろな回路を書き分けられるということがわかる。そういう単純な回路を積み上げていくことで、スマートフォン用の省電力型マイクロプロセッサやメディアプロセッサ、それからPC用のハイパフォーマンスプロセッサやGPUが作られる。そういうものに乗っかって、本来効率の悪いLLインタプリタがラムダ式などの抽象プロセスを含むコードを解釈しながら、実用アプリケーションをゴリゴリと実行している。気の遠くなる話だが、部分部分はそれぞれ理解できるような気がして楽しい。


で、数論の話に移る。インクリメント、加算、乗算、累乗というように、一方向のみのハイパー演算をどんなに積み上げていっても、それらは全て自然数の中で閉じた演算になる。ところが、インクリメントの逆演算であるデクリメントであるとか、加算の逆演算である減算を定義した途端に、負数というものの存在が要請されてしまって、演算は自然数の範疇を食い破って、整数の世界に飛び出す。同様に、乗算の逆演算である除算を考えてしまうと、有理数という集合が要請されるし、累乗に対して累乗根を考えてしまうと、実数集合が要請されて、そうやって算術の拡張が数そのものの世界を拡張してしまう。

ただ、実数というのはちょっと大雑把すぎる分類で、円周率πというのは実数だけれども、自然数や有理数の累乗根としては表すことができなくて、こういうものは超越数と呼び、累乗根が要請する数の集合からははみ出している。一方で、負数の累乗根というのはすでに実数範囲に収まらなくなっていて、虚数が要請される。演算を累乗に限定せずに多項式演算を考えると、逆演算は多項式解を求める演算になって、値域は複素数集合に広がる。

複素平面にベクトルやテンソルのような積演算を定義すると、その逆演算は四元数のようなより複雑な集合を要請するけれども、こういうものは複数の実数の直積とそれを対象とする演算が定義された代数系を構成するだけであって、直積の個々の要素が実数より広い集合を要請するということはない。そこで思うのだけれど、もしテトレーションの逆演算みたいなものを導入するとすれば、ひょっとしてその値域というのは実数より本質的に広い集合に拡張されるんだろうか。そんなことを思った。

xとyのテトレーションを演算子「丁」を使って「x 丁 y」と書くものと定義する。同様にテトレーションの逆演算も演算子「卯」を使って「x 卯 y」と書くものと定義する。すると、1 丁 2 = 1 となり、2 丁 2 = 16、3 丁 2 = 7625597484987となる。n 丁 2のnを自然数に限定すると、解の集合は小さい順に1, 16, 7625597484987と並んで、2 卯 2 から 15 卯 2 までと、17 卯 2 から 7625597484986 卯 2 は自然数には収まらないということになる。この一部は複素数に落ち着くかもしれないが、別の一部は複素数をはみ出してしまうかもしれない。

負数というのは-2というように書くけれども、これは「0 - 2 の解」ということを表す記号であり、 5 - 7 = -2 というのも、5から7を引いた解は 0 - 2 の解と同値であるということを表現しているに過ぎない。分数というものも同じような表現で、2/3 というのは「2 ÷ 3 の解」というのを表す記号で、それ以外に表現のしようがないということを意味している。2/3にはいろいろの性質があって、0.66666...という循環小数で記述できたり、「4 ÷ 6 の解」と同値であることなどが知られているけれども、値そのものの表現としては、「2 ÷ 3 の解」という方法しかできない。

√2 は「2の平方根のうち正値」という意味だし、これこれこういう逆演算の答え、という身も蓋もない表記という意味では、-2 や 2/3 と同じということになる。「x 卯 2 の解」という記号を「兎x」と定義してやれば、新しい数を記述することができるようになる。あとは、その値が複素数の範囲におさまるのか、あるいは実数の直積として表現できるのか、ということを調べていくことになる。で、もしそれが既知の集合とは別のものになるとしたら、新しい数論的集合が構成されるということになる。単純に予想すれば、たぶん複素数とは別のものになっているだろう。

そして、その新しく定義された集合が「有限個の実数の直積」として表現可能ならば、集合の濃度は実数濃度と等しくなる。ただ、無限階のハイパー演算とその逆演算が構成する代数系なんてものが無矛盾性を満たしてしまったりすると、その代数系が逆演算の方についても閉じるような数の集合というのは、果たして実数濃度に収まるんだろうか、という疑問がある。

小数記法で、桁数が有限ならば必ず有理数の範囲に収まるが、無限桁で循環しない場合には、無理数になる。同じように、有限個の実数の直積として表現できる数の集合は実数濃度を持つけれども、無限個の繰り返しのない実数の直積として表現される数を定義すると、それは実数濃度では収まらないんじゃないかという気がしている。

連続体仮説というと、可算濃度と連続体濃度の中間濃度の無限というものは存在するか、という話になっているけれども、連続体濃度の上、というのはどういう議論になっているのだろうか。21世紀にもなると、このあたりは数学的に解析が済んでいたりするのだろうか。どうだろう。


参考:
冗長2進加算器と乗算器の性能評価
無限のステップ
[PR]
by antonin | 2012-11-02 06:22 | Trackback | Comments(0)
トラックバックURL : http://antonin.exblog.jp/tb/19415374
トラックバックする(会員専用) [ヘルプ]
※このブログはトラックバック承認制を適用しています。 ブログの持ち主が承認するまでトラックバックは表示されません。
<< 補遺:1と9/9が等しくないこ... Brainfuckが可愛すぎて... >>


フォロー中のブログ
外部リンク
外部リンク
ライフログ
ブログパーツ
Notesを使いこなす
ブログジャンル