メモ

アドベントカレンダーを最低5記事、出来れば10記事書くと決めて書き始めたのが11月2～3日。
今が11月14日で書き終えたのは2記事。
急ぎます。
幸いこの記事はそこそこ難しいですがあっさりしてるはずです。
あっさりしているのは自分もまだよく分かっていないことについて書くからです。

「(ステートレスな)計算の結果はあらかじめ決まっている」。
これは誰もが当たり前に信じています。
そうでしょうか？

これが問題となるのは自由意志の文脈です。
世界が決定論であるか、自由意志は存在するか？
そうした問題を議論する場合に往々にして前提とされる「決定論なら結果は決まっている」。
これを否定するのはかなり直感に反しますが、考慮には値します。

ここでは計算結果が決まっていることを「(計算の)既定性」と呼ぶことにします。

以下の議論では結論を出せたとまでは言えません。しかし色々考えながら既定性を否定しようともがく私の思考を辿れます。哲学らしいでしょう？そういうのが好みでない方は読む価値がないかもしれません。

経験的な「既定性」

入力されたプログラムを実行。計算結果を保存。aとする。
入力されたプログラムを実行。計算結果を保存。bとする。
aとbを比較し結果を出力。
停止。

このアルゴリズム(適当に「繰り返し実行比較プログラム」としておきます)は、入力されたプログラムが停止する場合(かつ計算結果の比較が停止する場合？)「一致した」と出力し停止します。停止しない場合はもちろん何も出力せず停止しません。
往々にして比較の段階は人間が自分の目で見て行います。
つまり「同じ計算は、完了し手順さえ間違えなければ必ず同じ結果になる」。
これが我々が経験的に「計算結果が決まっている」と考える理由ではないでしょうか？

このアルゴリズムにプログラムBを入力にとるプログラムAを入力します。
その場合プログラムBは停止しなくてもプログラムAが停止する場合は、比較結果は一致したと出力されます。
実際にそのもの自体は計算できなくとも極限が計算できる関数は無数に存在します。
これは「停止しないプログラムも計算結果は決まっている」という直感を形成します。
円周率が3.14以上3.15未満なら、その範囲内に円周率を示す具体的な実数が存在するかのように感じるのは当然のことです。

この自明な定理は自由意志を否定するようなものではありません。
なぜなら対象の人間による決定に該当するプログラムが過去に実行されたことがあると考える根拠がないからです。

既定性

我々が素朴に期待する計算の既定性は「繰り返し実行比較プログラム」のそれとは別のものです。
なんというか「全てが計算されたことがある」とは違うが、とにかく計算に対してその結果があらかじめ決まっているような…そのままですね。
これを「経験からくる錯覚」で終わらせるのは無理があります。

あえて定義すれば以下のような命題でしょうか。

任意のプログラムには、「計算結果」への自然な対応がある。
そのプログラムを実行すると、何度繰り返しても必ずその結果になる。

2行目は「結果が必ず同じになる」という点までは異存はありません。
1行目は一方で意味不明です。「自然な対応」ってのは謎ですが、しかしより良い表現も思い浮かびません。
数学風に「写像が存在する」としても同じことです。
とりあえずこれで考察を進めます。

停止性

ところで停止性は既定なのでしょうか？
計算可能性理論でもっとも有名な停止性問題から、一般に停止性問題を判定するアルゴリズムが存在しないことは知られています。
この話について少し補足します。

まず「停止性問題を解くアルゴリズムは存在しない」というのは、「どんなチューリングマシンについても、有限時間で停止するか判定するアルゴリズムが存在しない」ということです。
ですのでチューリングマシンの中には実際に実行せずとも停止しないと判断できる場合も、停止すると判断できる場合も割と存在します。
例えば前者は避けられない場所に無限ループが含まれている場合、後者は含まれる全てのループが有限回の場合です。普通に判定できます。
それからそれ以外、つまり一つも停止性問題を解くアルゴリズムが存在しないようなチューリングマシンでも、停止するまで実行することはできます。そして停止することもあります。
当然ですが、停止しないと分かっているなら停止性問題を解けています。

この辺りは分かりづらい、というより私自身いくらか混乱しました。
停止性問題の話だと「でも普通に停止性問題を解ける場合があるよね」と考えがちですが、解けない場合もあるよということです。

では実際に一つも停止性問題を解くアルゴリズムが存在しないチューリングマシンの停止性は既定なのでしょうか、という話です。
それが現実的な時間で停止するなら既定なのはまぁ納得が行きます。実際に実行して有限時間で停止するわけですから、二度目も停止するでしょう。
しかしそれが停止しない場合、それは既定なのでしょうか。
厳密に言えばこの議論自体既定性を前提としていますから、ではこの宇宙で利用可能な全ての計算資源を投入してもまだ停止していないが今後停止しない保証のないアルゴリズム、これが存在したとして今後停止するかは既定なのでしょうか。
既定だというなら、その既定性を与える何かは計算不可能な問題を解いてるんですかと問いたいです。

「既定性」というのは我々が実際に観測する情報というわけではありませんから、どこかで計算が行われていると考える理由はありません。
そもそも記述しうる全ての計算は既に一度行われたことがあるという主張は間違いなく不合理です。
ですが計算不可能な問題の結果があらかじめ決まっているというのも直感に反するところがあります。
というかそんな問題の既定性なんてないでしょう。あったとしても超越的な計算機を持たない我々には、さらにこの宇宙では永久に解くことができないわけです。

では「停止する場合のみ既定である」というものを、停止性の既定性を前提とせずに定義できるとは思えません。
いえ正確には「停止する場合のみ既定である」という定義だという話なら当たり前です。単なる言い換えです。
素朴な「既定性」と呼べるものが具体的に意味がある形で我々と独立に存在し、それが停止するアルゴリズムにのみ値を持っているというイメージでは納得できません。

直感的にはまだ「短い時間で停止する計算は既定である」ような気になりますが、計算時間によって既定性が変わるというのはあり得ません。
実際問題一定時間で停止するようなチューリングマシンは全て既にどこかで計算されているような気もしますが、それは「繰り返し実行比較プログラム」の方の話です。
仮に一度計算済みでそれを参照可能なら、結果が同じになるのは当たり前です。

計算途中について

停止性問題の議論から「任意のプログラムと計算結果の組み合わせ」のようなものは素朴に想定できないというのは、少なくとも私は納得できました。
しかし、既定性自体が否定できたようには思いません。
別のアプローチから考えてみます。

では停止すると分かっている場合、例えば適当な時間$t_1$時点の状態についてはどうでしょうか。
任意のチューリングマシンを、一定時間で計算を打ち切るような処理に書き換えることは可能です。当然必ず停止します。
そしてそれについて開始時間から$t_1$までの振る舞いを有限時間で書き下すことも可能です。
停止時の状態は当然有限時間で計算することもできますし、長い数式(というか論理式)に書き下すこともできます。
これでも既定ではないと言えるでしょうか。

この$t_1$は任意の数字を代入することができます。
$t_1$を増やしその極限がどうなるかは停止性問題となり計算不可能ですが、思いつく限り大きな数字を代入した場合は計算可能。
現実問題として決定論を前提とすれば「人間が一定時間内で行う判断」は具体的な有限時間で計算可能ですから、自由意志に関する議論では有限時間に関し既定なだけで十分です。
直感的にはこうした既定性はありそうです。

我々は定数時間後で強制停止するよう書き換えたチューリングマシンが停止するという知識を持っていますが、我々と独立の既定性という性質が我々の知識によって振る舞いを変えるというのは意味不明です。
一方で計算の途中の状態までなら既定で、停止状態までなら既定ではないというなら、その二つには根本的な違いに思われます。
しかし、ということは「入力されたチューリングマシンを、$t_1$時点の状態を出力し停止するように書き換えるチューリングマシンの停止時の状態」と「チューリングマシンの$t_1$時点の状態」で既定性の挙動が変わるとでも言うのでしょうか。
無理があります。そもそもこの二つは区別できず、どうモデル化するかという話に過ぎません。

数学・論理学

計算結果に対する既定性は計算機科学に限った話ではありません。
数学や論理学の定理検証は有限時間で計算可能ですから、「数学的命題の真偽は既定か」という問題にもなります。
それは数学においては「数学の定理は発見か、発明か？」という古くからの問いです(既定でも体系の発明の余地はある、というかそういう意味な気はしますが)。
論理学で命題とは真偽が決まっているものだと言われます。
(「数学や論理学」と一々書くのは冗長なので、以下数学で代表させます。)

既定性は「繰り返し実行比較プログラム」からくる錯覚だけではありません。
理由の例を二つ挙げます。
一つは世界が我々が発見する以前に数学に従っているから、一つは数学の世界には様々な一貫性があることです。

前者は我々の世界では様々な計算が行われていて、数学者が言葉にして発見する以前から一度目の計算が行われていることが多々あるというだけです。
世界には計算と呼べるものが存在し、計算はチューリングマシンでモデル化でき、チューリングマシンは数学の言葉で定義される。
だから世界には数学でモデル化できるものが存在し、それらは数学に従う。数学の定理が先に計算されていることもある。
そこまで不思議なことではありません。

しかし我々が定理を発見する前から、世界も発見済みの定理も計算結果もその定理に従っているというのは不思議な話です。
既定性を否定したとして、「量子力学の観測のように計算を行うと計算結果が固定される」ようなものであればそうはなりません。

数学も論理学もある程度の物理法則もチューリングマシンで記述できるので、計算が先にあるという考え方も可能です。
一つの考えは「計算機の挙動にはたまたま偏りがある。数学の定理はその挙動を記述するもの」という考えです。
定理の証明は「たまたま存在する偏りが、条件を満たす全ての場合に成立すると枚挙するもの」だとも言えます。
これなら多少は納得できますが、しかしこのことを数学/論理学に由来する言葉抜きで記述できる自信はありません。
それに全ての数学の定理がそういうものだという確証もありません。
加えて言えばその「偏り」も既定性を前提としているように思えます。
無理がありますね。

数学と論理学という魔境で既定性を議論するのは今回はこの辺りで切り上げます。
手に負える気がしません。

既定性は「無限の存在」のように大変強い魅力があります。
数学でも論理学でも既定性が証明されたことはありませんが、しかし否定するのは余りに困難です。
数学や論理学自体は既定性を前提とせずとも成立するでしょうが、様々な場で既定性は自明な前提として扱われています。
影響の大きさを考えても、この程度の議論で否定や証明ができたとは言えません。
しかし疑う余地は多少あるとは言えるでしょう。
そして「自由意志」という文脈に限定すれば、そこまでの十分な証明は必要ないかもしれません。

ゲーデル文

この議論の都合の良い解決は「ゲーデルの不完全性定理におけるゲーデル文は既定だとは言えない」です。
自然数論の公理系における証明を順番に生成し、ゲーデル文の証明に突き当たった場合には停止するプログラムの既定性を考えます。
「これの停止性が既定であると考えればゲーデル文が真か偽か決まっていることになり直感に反する」と言えれば楽な話です。
しかし実際のところ上のプログラムが停止しないのは明らかなので直感に反するとは言えません。
「ゲーデル文の証明」を「ゲーデル文の反証」にしても停止しません。
停止性の証明や既定性の云々を自然数論の公理系内で証明しなければいけない理由はありません。

ゲーデル文の問題でなくとも、計算不可能性が証明されていて、具体的なプログラムで記述が出来て、それ(その停止性)が既定だとすれば直感に反するような問題があれば都合が良いです。
数学の世界には計算不可能問題がいくつもあるそうです。
しかし既定であることが直感に反する問題は見当たりません、というか下の論文を眺めましたが読む気がしませんでした。

Bjorn Poonen (2012) "Undecidable problems: a sampler"

実際のところそうした「既定であるとすれば直感に反する問題」があったとして、それに対応するプログラムを実行して停止したらどういうことなんでしょうか。
停止するかしないか既定でないとすれば、実行してみたら停止する場合もあるわけです。
「既定であると直感に反する問題」というのは誤解でしか存在し得ない気もします。

円周率に含まれる数列

個人的に「既定であると直感に反する」と思った例は、Wikipediaの計算可能関数の例にあった、「円周率の十進数列にn個の連続した5が出現する場合1、それ以外は0を返す関数」です。
この関数は何らかの定数kに対し、$n<k$なら$f(n)=1$という単純な関数ということになるのですが、kがどのような数字なのかは既知ではありません。おそらく計算不可能でしょう。
円周率には任意の数列が含まれると証明されるなり、数列から桁数を逆算できるようになるなりということがなければの話ですが。
記事中の一文は既定性を前提に、この関数自体は計算可能な例としています。本当でしょうか？

「n個の連続した5が出現する場合は停止する、それ以外は停止しない関数」なら簡単に作れます。nを増やすごとに計算時間が長くなり、やがて停止しなくなります。
そしてどんな計算資源を費やしたとしても、これが「kだ」と言えるようにはなりません。
そんなkは実在すると言えるのでしょうか？既定だと言えるのでしょうか？

既定性を議論する難しさ

我々は「既定性」を当たり前の前提としています。
そのせいで既定性を議論する際にも、当たり前に既定性を使ってしまいがちです。
あるいは実際は既定性を前提としていないのにそうであるかのように感じてしまうこともあります。
別に既定性を前提に既定性を否定しても良いんですが(矛盾で前提が否定されるので)、できれば避けたいところです。
とはいえ今回はそこまでこだわらずに書くことにしました。

一応、「Aが停止するならBである」のような命題は既定性を前提としていません。
それは単純に論理式であって、「Aが停止すれば初めてBであると分かる」と考えれば良いだけです。

あと「既定性」と入力しようとすると「規定性」で変換される点も地味に鬱陶しいです。
同音の言葉は避けるべきでした。しかし「既定性」がしっくりくるので仕方ないです。
アプリオリは少し意味が違います。「計算結果はアプリオリか？」はとても哲学っぽくて格好いいですが。

ちなみに「直感主義論理」という考え方があって、似たような議論があります。
基本的には推論規則を限定した論理学の手法ですが、ある程度哲学的な主張も関わります。
しかし既定性を疑っているとまでは言えない気はします。
命題の間で排中律が成り立たないというようなことは、命題の真偽判定が計算可能問題ではないこともあると考えれば当たり前ではあります。
あまり詳しくないので触れませんでしたが、ここで書いたようなことは既にこの分野では議論済みとかかもしれませんね。

余談：ラプラスの悪魔

既に議論したように、人間の挙動が決定論的でありかつ既にそのシミュレーションが行われている場合、それを知っている観測者にとって人間の行動は既定です。要するにラプラスの悪魔です。
普通に考えればそれは自由意志の否定を意味します。
しかし必ずしもそうとは限りません。

人間的な意識は計算に伴い発生するという立場があります。
仮にラプラスの悪魔が存在する場合、その悪魔が計算する際にも意識が存在します。
入力を持たない計算から見て、どこにあるどのような計算機で実行されているかを認識し得ません。
ラプラスの悪魔における意識、現時点で発生する意識、この二者を同一視するなら「私が自由意志で決定を行っていること」は否定できません。
ただ別々の場所で行われる計算を同一視するというのがどういう意味なのかは私自身よくわかりません。
仮に別だとしても、自分と同じ名前の全く同じ存在が下した判断なら自由意志がなかったとしても大した問題ではないとも言えます。

なお量子力学における波動関数に関する問題から、現在は決定論が素朴に成立するとは考えられていません。
ですが自由意志の問題にそれほど影響を与えるとは言えません。
計算量を問題にしないならば観測による確定を全パターンでシミュレーションすることが可能です。
量子コンピューターの状態は普通にそういう書き方をしますし、みんなが好きな「シュレディンガーの猫」における語りもそうです。
人間の脳は概ね巨視的挙動をすると言われていますから、大抵の場合はある程度の時間なら行動を高い精度で予測可能なはずです。
例えば電子計算機の挙動ならほぼ完全に予想できるわけです。それは意図して作ったからで、脳はそこまで確実ではありませんが。

不確定性原理もまた問題になりますが、それもまた片っ端から計算すれば良いだけです。思考実験ですし。
物理世界に属する第三者でなく、何か特別なアクセス権を持つ外部世界の存在を仮定しても構いません。
その第三者として精度が高い予測ができるかは疑わしいですが、「あなたがどう行動するかは一度計算済みである」と保証することはできます。
それでも自由意志の否定とある程度言えます。

感想

今回、記事を書きながら色々考えましたがいくらかとっ散らかってますね。
哲学の本にもこういう感じなのがありますし、私としては哲学的な営みっぽい感じがします。
ただその内もう一度きちんと整理してから書き直したいです。
今回はアドベントカレンダーまで記事をそこそこ書かないといけないですし、記録としてもこの記事を残しておきたいのでこのまま出します。
先頭に注意文を書いたのでこれで良いでしょう。

既定性自体は本当に難しい問題です。
正直単なる幻想という気もしますが、しかしどうしても否定しがたいものがそこにあります。
ただ自由意志というテーマに限ればそこそこつけ入る隙がありそうです。

宣伝

最近イヤホンの左右を判別するアプリを作りました。
どっちが右なのかすぐ確認出来て便利なのでお試しください。

補足：エントロピー増大

(以下は本文から2ヶ月後に書いた文章です。)

時間の議論でエントロピー増大則と言うものが知られています。
これは熱力学での断熱系の話ですが、物理法則の(ある程度の)時間反転対称性からすれば不思議です。
我々の主観時間に方向があるのも妙な話です。

ただこの世界の計算機に従わない演算は不可能と考えると当たり前です。
そうでなければ計算せずに結果を導けることになります。
単純に物理法則をシミュレーションする状況を考えれば十分です。
そこから、この世界を計算機と捉えた場合、直感通りの方向で計算されているのも自明です。

ところで人が死んで燃やして灰になった時点から逆順に物理法則を適用することを考えます。
それは量子力学的な問題があって不可能ですが、シミュレーション内で生きた人ならできます。
「既に計算されている灰」と「計算されていないが復元すると人間になる灰」の区別は存在するのでしょうか？

「たまたま時間が遡る」ような現象は現実の物理世界でも起こり得ます。単なる偶然です。ボルツマン脳は有名です。
猿がシェイクスピアの文章を出力する(無限の猿定理)のと同じです。
そこに主観的な経験を想定する必要はありません。
しかしあり得ることです。

ランダムな物理状態(灰)から逆順に物理法則を適用し、それがたまたま(正順に見れば)普通の人生を辿る人間だった場合を考えます。
後に正順で計算した際、彼は受精卵の時点で全ての運命・行動・発言が決定しています。
外部から観測する限り自由意志は存在しません。
そして逆順計算の時点で主観的経験を欠くと考えれば、意識不在で意思決定がなされたことになります。
とはいっても、実際に彼が辿った人生は逆で、しかも全てが偶然だったわけです。

既定性を否定しても自由意志が否定されているような例が出てきてしまいました。
これは少し困りますね。

さらに言えば偶発で計算結果を代替するということもよく考えないといけません。
そもそも情報量(エントロピー)自体がそういうものですが。