ゆるゆる べんきょう

暇だから哲学・数学・物理学をゆるく勉強しているよ

ビットコインにおけるブロックチェーン(続き)

ブロックチェーンというが実際はブロックヘッダチェーンといったほうが正しいように思われる。各マイナーは、ブロックヘッダのsha254のチェックサムがターゲット数以下になるように、様々なブロックヘッダを試行する。この時に変化させるのはnounceと呼ばれるフィールドであり、任意の整数値でよいためこれをパラメータとする。最近では一秒以内にすべてのnounceをすべて使い切ってしまうASICがある(ブロックヘッダには時刻のフィールドがあるため、これもパラメータとなりうる)。その場合は、ブロック生成報酬であるcoinbaseトランザクションのエクストラフィールドを使うことがある。

 

上記に見るようにビットコインの動力源は、新たに追加する際の計算リソースであることがわかる。

ビットコインにおけるブロックチェーン

各ノードが保有しているほぼ同一な元帳が、ビットコインの価値である。元帳には「価値の移動」を意味するトランザクションが記載されている。すなわちビットコインが最初に生成された時から現在に至るまでのすべて価値の移動(基本的にはビットコインの授受と考えてよい)をトラッキングすることで価値の分布(ビットコインディストリビューション)がわかる。

 

この元帳は、ブロックチェーンという技術によって実装されている。ナカモトサトシが最初に作成したジェネシスブロックを第一ブロックとして、チェーン状にブロックをつなげることで、大きなサイズの元帳を生成するためのデータ領域が確保される

(注:新たに生成されたトランザクションを元帳に書き込むことができる)。ブロックサイズは1MBであり、ブロックにはおおよそ500程度のトランザクションを含めることができる。ブロックは10分に1回程度の割合で生成される。

 

新たに生成されるブロックは、検証はすぐに終わるが作成には大量の計算リソースを要するようなルールがなされており、誰かが新たにブロックを作った際にそれをブロードキャストすることで、各ノードの元帳はほぼ同期する。

 

このような形でビットコインブロックチェーン技術を使って、ビットコインの分布を表現する。

2017-05: 古典論理を学んで

--- 古典論理を学んでいたということですが

はい。論理学の基本ですね。アリストテレスの時代から進歩がなかった学問ですが、19世紀末から20世紀で一気に開花した学問です。数学基礎論とか数理論理学と呼ばれている分野です。

 

---数学と論理学に関係があるのですか

はい。論理学は数学の基礎としてとらえられています。数学は、証明なしで受け入れる概念である公理を定め、そこから証明・演繹を繰り返すことにより、定理を導くというゲームであるとみなせます。この言語となるのが論理と言われます。具体的には演繹や証明といった道具立てについて、より詳細に調べる学問といえます。

 

---それでは論理学は数学のための学問ということですか?

それは違います。確かに論理学の発展は数学の基礎付けという側面で爆発的に発展をしたのですが、より一般的に我々の理性や思考に関する一般的な命題を扱うことができます。ただ現時点で一番成功しているのが、数学に代表される命題、すなわち、「・・・である」というタイプの命題のみを扱う古典論理だということです。

 

---古典論理以外にもあるというわけですね

はい。「・・・・は必然的に真である」というタイプの命題や「・・・・するべきだ」というタイプの命題などを扱う論理学(様相論理学)も発展してきています。これらと対比する意味で、数学の基礎づけに関する論理を古典論理と呼んでいます。

 

---古典論理の知見を教えて下さい

数学の基礎付けを果たしました。具体的には公理的集合論の整備です。これは論理学の言葉で数学の集合論を構成したものです。公理的集合論の概念ZFCを使うと現代数学のほぼすべての分野を包含できます。そのため、論理学の言葉で数学が記述されることが明らかとなり、数学の方法論(推論や証明に使ってよい道具立て)が正当化されたことが言えます。一方、否定的な意味で数学に寄与した部分もあります。

 

---否定的な意味での寄与とは?

いわゆるヒルベルトプログラムが実現できないということを証明してしまったことです。ヒルベルトプログラムとは、「有限の方法で数学が無矛盾であることを示す」というものです。簡単に言えば数学で使っている推論や証明方法を使えば変なことは起きない、ということのお墨付きを論理学が与えたいというものです。それができないとゲーデルが証明してしまったのです。ある意味数学者は、自分の使っている道具が正当なものかわからない状態になってしまったのです。もちろん数学が間違っているとか、矛盾しているというわけではありませんし、数学の無矛盾性が「有限の方法で」示されないだけであり、べつの道具立てを使えば無矛盾性を示すことができます。「数学は自己完結した絶対的なものだ」という幻想が崩れただけです。

 

---古典論理の概要を教えてください

ざっくりいって論理の種類は、「命題論理⊂1階述語論理⊂数学の論理」という形で表せます。それぞれの論理で、統語論と呼ばれる用語の定義と、構文論と呼ばれる公理と推論のルール、意味論と呼ばれる論理の具体化からなります。論理学では、各論理内でどのように推論するか・どのような定理が得られるかというようなオブジェクトレベルの話と、各論理がどれぐらいまともか、というようなメタレベルの話の両方を射程にします。オブジェクトレベルの話は、いわゆる計算方法や証明手順に関する議論をし、メタレベルの話では健全性・無矛盾性・完全性などを議論します。

 

---では命題論理についての概要を簡潔に説明ください

まず、統語論です。命題論理では、命題間の接続性に注目します。原子命題は「・・・である」というものを想定し、2値として真か偽かをとるものを考えます。そして原子命題同士の接続性として、否定「¬」、かつ「∧」、または「∨」を用いて命題同士が結合し、より複雑な命題が構成されます。

次に、構文論です。何種類かバリエーションがあるのですが、ゲンツェンの自然演繹が一番わかりやすいです。構文論のバリエーションの違いは、推論規則と公理の選び方の違いだけで、その表現力は同等であることが示すことができます。

最後に意味論です。各種原子命題に真か偽かを割り当てて、複合命題の真偽を問うものです。前提をおいて帰結させるような演繹演算も含まれます。

 

---命題論理の知見を簡潔に説明ください

メタ的な知見としては、命題論理は無矛盾かつ完全です。オブジェクト的な知見としては任意の命題や意味論的帰結に関して、その真偽決定手続きが存在します。また、二値に真偽ではなく、電圧の高低を利用すると、デジタル回路の設計になります。オブジェクトレベルではブール代数と同値です。

 

---続いて1階述語論理の概要を説明ください

述語論理は、命題論理の拡張で、命題、述語と項に分解します。統語論として命題論理のそれに加え、全ての「∀」と、ある「∃」を導入します。構文論としてはゲンツェンの自然演繹を拡張したものを使います。意味論としては構造と割り当てという概念を用います

 

---1階の述語論理の知見を簡潔に説明ください

メタ的な知見としては、1階述語論理は無矛盾かつ完全です。オブジェクト的な知見としては任意の命題や意味論的帰結に関して、その真偽について決定手続きが存在しないことがしられています。アリストテレスが考案したオルガノン(三段論法)を完全に包含しています。

 

---そして数学の論理ですね

はい。数学の論理といっても「PA⊂ZFC」というように大小関係があります。ZFCまで大きいと数学のほぼ全てを射程にできるといわれています。ZFCは公理的集合論ともいわれ、それを学ぶだけでそこそこ時間がかかります。私は2017-04に何冊か参考書を読みました。PAペアノの公理と呼ばれる自然数に関する公理を述語論理に付け加えたもので非常にミニマルです。

 

---不完全性定理が絡んでくるのですね

そうですね。1階述語論理までは完全かつ無矛盾といってもよいのですが、PAおよびZFCに関しては、有限の立場では「矛盾しているか不完全である」ことがゲーデルによって示されました。とはいっても今のところ数学が矛盾しそうな雰囲気もないので数学者はそれほど大きな受け止め方をしていないと思います。また、不完全性に関しても、「この問題は解けない」というのも一つの問題の決着のつけ方ですし、まあこんなものでしょ、という感じだと思いますね。ヒルベルトの「ノン・イグノラビムス」のような原理主義者にとっては耐え難かったでしょうが

 

---最後に残しておきたい言葉はありますか

私は論理学が好きです。勉強してみてつくづく思います。近いうちにまたここに戻ってくると思います。Rautemberg教授の論理学の教科書や、フランセーンの素晴らしい不完全性定理の本は、現時点ではまだ消化しきれていないのですが、いつかは理解できるようになりたいです。様相論理に関しても興味があるものの、手を付けられずじまいでした。残念です。

 

 

 

トートロジーと論理的帰結

モデル・値付けw(wα=1)を充足関係 w|=α と捉えなおす。論理式φ∈Fはモデルによって充足したり、しなかったりするが、任意のモデルに対して充足する論理式があり、トートロジーと呼ぶ。任意のモデルに対して充足しない論理式があり、矛盾と呼ぶ。αを充足する任意のモデルに対してXが充足するとき、論理的帰結と呼び、 α|=X とかく。充足関係と論理的帰結に同じ記号を割り当てるが、特に混乱はないはず。

 

論理的帰結に関し、 X,α |= β ⇒ X |= α→β という演繹定理が成り立つため、これを帰納的に利用することで、任意の論理的帰結の妥当性は、ある種の論理式がトートロジーであるかどうかという問題に帰結し、決定可能である。

 

命題論理: 同値関係と標準形

n個の原子命題からなる論理式は、#Bn = 2^2^n 個あるf: 2^n → 2 なる関数と同一視できる。この同一視(意味論的同値関係)は、数学でいうところの同値関係(同一律、反射律、推移律を満たす)であるため、n個の原子命題からなる論理式全体からなる集合 Fn は意味論的同値関係によってパーティショニングすることができる。そして、各パーティションは、DNFもしくはCNFの形式の論理式で代表させることができる。別の言い方をすると、任意の論理式はDNFもしくはCNFと意味論的同値関係にある。

さらに、意味論的同値関係は、congruenceな関係でもある。それにより、論理式の一部を、意味論的同値関係にある別の論理式に置換してもよいという定理が得られる。

さらにさらに、δ: F→F を、帰納的に以下で定める。すなわち、 π→π, ¬α→¬δ(α), α∧β→δ(α)∨δ(β), α∨β→δ(α)∧δ(β)。このようなδで射影される二つの論理式 φ→ψを双対関係という。DNFとCNFは互いに双対関係であり、また、δδ=1である。