複素数体上の正方行列𝑨はJordan標準形𝑱と相似である、すなわち或る正則行列𝑷が存在して𝑷-1𝑨𝑷＝𝑱となることは線型代数講座の最終目標でもあるから、講座を履修したことがある人なら誰でも御存知でしょう。ところが、私の友人共から言わせれば殆どすべての学生達はJordan標準形の証明を少なくとも講義時点で全く理解していないと言ってました。それが証拠に、Jordan標準形の講義終了後に具体的な正方行列のJordan標準形を求めよと言っても、殆どすべての学生達は出来ないでしょう。また日頃から知ったかぶりで線型代数を環上の加群の一理論に過ぎないと軽視して講義をおろそかにしている学生連中が蓋を開けてみれば全く出来なかったことも言ってました。Jordan標準形の証明は① 広義固有空間に基づくもの(冪零空間を扱っているものも同義)、② 有理標準形を経由するもの、③ 単因子標準形を経由するもの、等があります。どれも長くて決して簡単ではありませんが、分かりやすさの度合いでは①が最低最悪です。①が分かりにくい一つの理由として読者に若干の視覚的直観を強いるからだと私は思います。歴史的に言うと①を避けたくて②又は③が考案されたのでしょう。しかし、①を本当の意味で理解すれば、Jordan標準形の本質も理解したことになり、Jordan標準形の算出も簡単に出来るはずなんです。残念ながら②又は③は間接的なので、それらの証明を理解してもJordan標準形の存在証明を理解したに過ぎず、Jordan標準形の本質を理解したことにはなりません。①は多少の違いや書き方の差はあれど、あれ以上は実質的に簡単になりません。私もかって①の基本線に沿って分かりやすい(自己基準)と思った証明を書いたことがありましたが、友人共から言わせれば返って不透明になったとボロクソに言われました。その時以来、①を改良しようなどと考えたことがありません。要は冪零空間を扱っている限りどれも似たり寄ったりということです。従って、皆さんも講義時点では①を理解出来なくても心の中でいつも①を反芻しておれば、いつかは証明と親密になる時が来るはずです。その時がいつ来るのか個人差があり、そもそもそれではその時までJordan標準形をずっと使えないままになるので、Jordan標準形の算出方法(と言うか、大事なのはJordan標準形そのものと言うよりも正則行列𝑷を成している列ヴェクタの求め方です)を以下に解説しておきます。
以下、具体的に固有値を一つのみ持つ三次正方行列を対象とします。二次正方行列では余りにも簡単過ぎて参考にならないし、四次や五次以上を用いて書くのは(私が)しんどくなるので三次を選びました。断っておきますが、以下の解説で述べることは何次であっても、また複数個の固有値があっても(各固有値に対するJordan細胞を対角線上に並べればいいだけの話)適用出来ます。
三次正方行列𝑨の固有値は𝛼のみと仮定します。先ず、ケイリー-ハミルトンの定理により(𝑨－𝛼𝑬)3＝(零行列)。rank(𝑨－𝛼𝑬)＝3(つまり、(𝑨－𝛼𝑬)は正則行列である)は固有値𝛼の存在の仮定に反するので有り得ない。よって、rank(𝑨－𝛼𝑬)＜3である(つまり、(𝑨－𝛼𝑬)は正則行列ではない)。
⑴ rank(𝑨－𝛼𝑬)＝2の場合。この時、(𝑨－𝛼𝑬)2𝒙≠𝟬となるような𝒙が存在する(何故か？皆さんも少しは頭を働かせて理由を考えてみて下さい。決して意地悪で言ってるのではありません。AIの流行花盛りですが、AIに答えを教えてもらって何が嬉しいのでしょうか。自分の頭で考えないと身に付きませんし、只でさえ頭が悪いのにAIに安易に頼っていたら益々頭が悪くなることでしょう)。この𝒙を𝒑3とし、(𝑨－𝛼𝑬)2𝒑3＝𝒑1, (𝑨－𝛼𝑬)𝒑3＝𝒑2とする。(𝑨－𝛼𝑬)3＝(零行列)だったから、(𝑨－𝛼𝑬)𝒑1＝(𝑨－𝛼𝑬)3𝒑3＝𝟬。よって、𝒑1∊Ker(𝑨－𝛼𝑬)。この𝒑1, 𝒑2, 𝒑3は線型独立である(何故か？)。𝒑1, 𝒑2, 𝒑3をこの順番で列ヴェクタとして持つ正則行列を𝑷とする。(𝑨－𝛼𝑬)𝒑1＝𝟬, (𝑨－𝛼𝑬)𝒑2＝𝒑1, (𝑨－𝛼𝑬)𝒑3＝𝒑2なので、𝑨𝑷＝𝑨(𝒑1, 𝒑2, 𝒑3)＝(𝑨𝒑1, 𝑨𝒑2, 𝑨𝒑3)＝(𝛼𝒑1, 𝒑1＋𝛼𝒑2, 𝒑2＋𝛼𝒑3)＝(𝒑1, 𝒑2, 𝒑3)([𝛼, 0, 0]𝑻, [1, 𝛼, 0]𝑻, [0, 1, 𝛼]𝑻)＝𝑷([𝛼, 0, 0]𝑻, [1, 𝛼, 0]𝑻, [0, 1, 𝛼]𝑻)。ここで𝑻は転置操作(行を列に、列を行にすること)を意味し、[𝛼, 0, 0]𝑻等は列ヴェクタとします。結局、𝑷-1𝑨𝑷＝([𝛼, 0, 0]𝑻, [1, 𝛼, 0]𝑻, [0, 1, 𝛼]𝑻)となる。つまり、一つの三次Jordan細胞から成るJordan標準形ということになります。
⑵ rank(𝑨－𝛼𝑬)＝1の場合。この時、(𝑨－𝛼𝑬)2＝(零行列)となる(何故か？)。そして(𝑨－𝛼𝑬)𝒙≠𝟬となるような𝒙が存在する(何故か？)。この𝒙を𝒑2とし、(𝑨－𝛼𝑬)𝒑2＝𝒑1とする。(𝑨－𝛼𝑬)𝒑1＝(𝑨－𝛼𝑬)2𝒑2＝𝟬だから𝒑1∊Ker(𝑨－𝛼𝑬)。dim Ker(𝑨－𝛼𝑬)＝2なので、Ker(𝑨－𝛼𝑬)の中で𝒑1とは線型独立なヴェクタを選び、それを𝒑3とする。この時𝒑1, 𝒑2, 𝒑3は線型独立である(何故か？)。𝒑1, 𝒑2, 𝒑3をこの順番で列ヴェクタとして持つ正則行列を𝑷とすれば、𝑨𝑷＝𝑨(𝒑1, 𝒑2, 𝒑3)＝(𝑨𝒑1, 𝑨𝒑2, 𝑨𝒑3)＝(𝛼𝒑1, 𝒑1＋𝛼𝒑2, 𝛼𝒑3)＝(𝒑1, 𝒑2, 𝒑3)([𝛼, 0, 0]𝑻, [1, 𝛼, 0]𝑻, [0, 0, 𝛼]𝑻)＝𝑷([𝛼, 0, 0]𝑻, [1, 𝛼, 0]𝑻, [0, 0, 𝛼]𝑻)。結局、𝑷-1𝑨𝑷＝([𝛼, 0, 0]𝑻, [1, 𝛼, 0]𝑻, [0, 0, 𝛼]𝑻)となる。つまり、一つの二次Jordan細胞と一つの一次Jordan細胞から成るJordan標準形ということになります。
⑶ rank(𝑨－𝛼𝑬)＝0の場合。これが最も簡単でJordan標準形と言うよりも、皆さんの大好きな対角標準形です。dim Ker(𝑨－𝛼𝑬)＝3なので、Ker(𝑨－𝛼𝑬)の基底を𝒑1, 𝒑2, 𝒑3とし、この順番でそれらを列ヴェクタとして持つ正則行列を𝑷とする。𝑨𝑷＝𝑨(𝒑1, 𝒑2, 𝒑3)＝(𝑨𝒑1, 𝑨𝒑2, 𝑨𝒑3)＝(𝛼𝒑1, 𝛼𝒑2, 𝛼𝒑3)＝(𝒑1, 𝒑2, 𝒑3)([𝛼, 0, 0]𝑻, [0, 𝛼, 0]𝑻, [0, 0, 𝛼]𝑻)＝𝑷([𝛼, 0, 0]𝑻, [0, 𝛼, 0]𝑻, [0, 0, 𝛼]𝑻)。結局、𝑷-1𝑨𝑷＝([𝛼, 0, 0]𝑻, [0, 𝛼, 0]𝑻, [0, 0, 𝛼]𝑻)となる。つまり、三つの一次Jordan細胞から成るJordan標準形ということになります。(完)
以上で解説は終わりですが、上述の算出法は固有値を一つだけ持つ三次正方行列の場合に限って、それが三次Jordan標準形と相似であることを証明したことにもなります。しかも、上述の考え方は一般次数にも適用出来ることが分かるはずです。一般的に𝑛次複素正方行列において𝑛－rank(𝑨－𝛼𝑬)個のJordan細胞が存在することも推察出来るでしょう。又、最低でも“何故か？”と私が問うている箇所はきちんと理由を説明出来るように自分の頭で考えて下さい。説明を言い淀むようでは理由付けが曖昧か、そこまで考えが至ってない証拠です。そんなことでは分かりにくい①を理解する時なぞ永遠に訪れません。私の“何故か？”に対して理由付けをきちんと自分で考えることが出来れば、上述の算出法も簡単に分かるはずですし、いや①でさえも既に無意識に理解しかけているのかも知れません。私は高校生の時にJordan標準形というものがあることを知り、証明云々の前にJordan標準形そのものが当時の私の直観とは全く相容れなかったので(と言うか、もっとはっきり言えばJordan標準形の形が気持ち悪かったと言う方が正確かも知れません)、心の中で嘘だろうと思いながら反例を見つけるつもりで(当時は数学者Jordanの名前も知らず、当然偉大さも知らなかったので、今から思えば赤面ものです)、行列論に特化した文献を漁っては、一桁次数は勿論のこと二桁次数の正方行列を見つけ次第にJordan標準形を手で算出した(結果のJordan標準形だけではなく、後で結果が正しいことの検証のために正則行列𝑷も勿論残しました)思い出があります。計算と並行して①を(大げさではなく)何百回と読み直し、半年くらい経って“あぁ、こういうことだったのか”と腑に落ちました。それは何百回と手計算したことがあったからなのであって、証明をただ単にぼけっと眺めていただけでは決して腑に落ちることはなかったでしょう。①が腑に落ちない人は、もし若くて体力があり時間もあるのなら、最低でも一か月くらいそういうことをやったらどうでしょうか。学生なら可能でしょう。
Jordan標準形の話はこれくらいにして、今回紹介する記事はQuantaに掲載されたThe Most Important Machine That Was Never Builtです。これを選んだ理由は私の周辺のド素人衆の中にやたらとTuringの生涯に関心を持っている人がいるからです。その人は数学は勿論のこと計算機科学も知りません。ところがTuringを自死に追い込んだ英国のこととなると舌鋒鋭く批判を何回も繰り返しますが、2009年に英国政府は公式に謝罪したのだからもういいのではないかと私は思います。余りにも遅過ぎたと思う人がいるかも知れませんが、終戦直後のあの時代に誰が性の多様性を認識出来たでしょうか。後から見れば偉そうなことを誰でも言えます。時代背景や状況を考えようとしないのは幼稚性のなせる業でしょう。また日本ではやっと最近になってLGBTQ＋関連法案が国会で審議されたばかりで、他国がどうのこうの言う資格はありません。それは兎も角も、その知人にはせめてTuringの功績の一端を知って欲しいので、これを選びました。その私訳を以下に載せておきます。
[追記: 2023年05月29日]
友人共の一人が上述の私の解説を読んだ学生から四次正方行列の場合のJordan標準形について質問を受けたようです。友人は懇切丁寧に説明して納得して貰えたようですが、他にも同じ疑問を持つ学生達がいるかも知れないから四次正方行列の場合にも少しでいいから言及してくれないかと友人から頼まれました。学生の質問がどういう質問だったのか具体的には聞いてませんが、おそらくrank(𝑨－𝛼𝑬)＝2の場合のことだと思います。rank(𝑨－𝛼𝑬)＝3, 1, 0の場合は三次正方行列の場合と全く同じ趣旨ですので、rank(𝑨－𝛼𝑬)＝2の時のみ言及します。この場合、(𝑨－𝛼𝑬)3＝(零行列)となり(何故か？)、(𝑨－𝛼𝑬)2＝(零行列)か否かでJordan標準形が変わります。(𝑨－𝛼𝑬)2＝(零行列)なら、二つの二次Jordan細胞を持つJordan標準形であり、(𝑨－𝛼𝑬)2≠(零行列)なら、一つの三次Jordan細胞と一つの一次Jordan細胞を持つJordan標準形になります。
⑴ (𝑨－𝛼𝑬)2＝(零行列)の場合。rank(𝑨－𝛼𝑬)＝2だからImg(𝑨－𝛼𝑬)には二つの線型独立なヴェクタが存在し、それらを𝒑1, 𝒑3とする。𝒑1, 𝒑3∊Img(𝑨－𝛼𝑬)だから、(𝑨－𝛼𝑬)𝒑2＝𝒑1, (𝑨－𝛼𝑬)𝒑4＝𝒑3となるような𝒑2, 𝒑4が存在する。(𝑨－𝛼𝑬)2＝(零行列)なので、(𝑨－𝛼𝑬)𝒑1＝(𝑨－𝛼𝑬)2𝒑2＝𝟬, (𝑨－𝛼𝑬)𝒑3＝(𝑨－𝛼𝑬)2𝒑4＝𝟬となり、𝒑1, 𝒑3∊Ker(𝑨－𝛼𝑬)。この𝒑1, 𝒑2, 𝒑3, 𝒑4は線型独立である(何故か？)。後は自分で考えて下さい。
⑵ (𝑨－𝛼𝑬)2≠(零行列)の場合。つまり、(𝑨－𝛼𝑬)2𝒙≠𝟬となるような𝒙が存在するから、この𝒙を𝒑3とし、(𝑨－𝛼𝑬)2𝒑3＝𝒑1, (𝑨－𝛼𝑬)𝒑3＝𝒑2とする。(𝑨－𝛼𝑬)3＝(零行列)だったから、(𝑨－𝛼𝑬)𝒑1＝(𝑨－𝛼𝑬)3𝒑3＝𝟬。よって、𝒑1∊Ker(𝑨－𝛼𝑬)。dim Ker(𝑨－𝛼𝑬)＝2なので、Ker(𝑨－𝛼𝑬)の中で𝒑1とは線型独立なヴェクタを選び、それを𝒑4とする。この𝒑1, 𝒑2, 𝒑3, 𝒑4は線型独立である(何故か？)。後は自分で考えて下さい。
[追記: 2023年08月21日]
友人共の話によれば、学生達が上述のJordan標準形に関する私の解説を結構読んでいるらしいです。つまり、世の中にはJordan標準形すらも理解していない人達が如何に多いかを窺えます。だから、友人共の一人は固有値が複数個ある場合、例えば最小多項式が(𝑥－𝛼)2(𝑥－𝛽)(勿論𝛼≠𝛽)のような場合に上述の解説の方法はどうなるのかと訊かれたようです。今どきの学生達は一を聞いて十を知るという訓練を受けていないと言うか、そういう頭の働きを持っていないらしいです。ですから、ほんの少しばかり最小多項式が(𝑥－𝛼)2(𝑥－𝛽)の場合に触れましょう。この場合、三次元複素線型空間は𝛼に関する高さ2の広義固有空間と𝛽に関する普通の固有空間の直和になります(何故か？自分の頭で考えて下さい)。三次元複素線型空間における線型変換を𝛼に関する広義固有空間、及び𝛽に関する固有空間へ制限すれば、それぞれ本質的に二次正方行列(つまり、rank(𝑨－𝛼𝑬)≦1。もっと正確に言えば、最小多項式が(𝑥－𝛼)2ならrank(𝑨－𝛼𝑬)＝1。最小多項式が(𝑥－𝛼)ならrank(𝑨－𝛼𝑬)＝0)と一次正方行列(つまり、rank(𝑨－𝛽𝑬)＝0)の場合の話に還元します。それぞれについて上述の解説の方法に沿って考えればいいだけの話に過ぎません。後は自分で考えて下さい(どうせ学生なんだから暇でしょう？)。
決して構築されることのなかった最も重要なマシーン
Alan Turingが1936年にTuringマシーンを発明した時、現代コンピューティンｸﾞをも発明した。
2023年05月03日 Sheon Han
計算は私達の殆どが直観的に理解している馴染みの概念だ。例えば、函数𝑓(𝑥)＝𝑥＋3を取ろう。𝑥が3の時、𝑓(𝑥)＝3＋3。6である。簡単だ。この函数が計算可能であることは明らかのように思える。だが、いくつかの函数はそれ程簡単ではなく、それが計算され得るかどうか決定することも容易ではない。つまり、それが最終的な答えを出さないかも知れないことを意味する。
1928年、独逸人数学者David HilbertとWilhelm AckermannはEntscheidungsproblem(“決定問題”)と呼ばれる問題を提示した。そのうちに彼等の問題は、計算可能性の形式的定義、すなわち数学者達が新しい問題の主役となることを許し、理論計算機科学に対して基礎付けたものに繋がるであろう。
その定義はAlan Turingという名前の23歳の大学院生から来た。彼は1936年に計算の概念を形式化しただけではなく、数学における根本問題を証明し、電子計算機の発明のための学問的な基礎を造った独創的な論文を書いた。Turingの鋭い洞察力は抽象的なマシーンの形式で計算問題に対する具体的解答を与えることとなった。その抽象的なマシーンは後に彼の博士論文指導教官Alonzo ChurchによりTuringマシーンと命名された。それは確固たる装置として物理的に存在しない(且つ存在するはずがない)から抽象的なのである。代わりに、それは計算の概念的モドゥだ。すなわち、マシーンが函数を計算出来るならば、その函数は計算可能である。
ここにそれがどのように働くのか示そう。Turingマシーンは規則一覧表に厳命され、無限に長いティﾌﾟを読めて、ティﾌﾟ上の記号を変更出来る。そのティﾌﾟは正確に一つの記号を収納出来る“小区画”から成り、マシーンはティﾌﾟ読書き先端部で小区画の内容を読んで書き換える。規則一覧表の各規則は、マシーンの現状と読んでいる記号の両方に基づいてマシーンが何をすべきかを決定する。マシーンは最終状態(“受理状態”又は“却下状態”)に入ることが出来、最終状態で停まって入力を受理するか又は却下する。さもなくば、無限循環に陥り、ティﾌﾟを永遠に読み続ける。
Turingマシーンを理解する最も良い方法は簡単な例を考えることだ。与えられた入力が数字0なのかどうかを私達に告げるように設計されたものを想像しよう。余白記号(“#”)を伴った数字0001を使うので、“#0001#”がティﾌﾟの関連部分である。
マシーンは初期状態で始まるが、それをq0と呼ぼう。マシーンはティﾌﾟ上の最左方の小区画を読み、余白を見つける。規則は“状態q0の時、記号が#ならば何の変更もせずそのまましておき、小区画を一つ右に移動させ、マシーンの状態をq1に変えよ”と言う。この段階の後、マシーンはq1の状態にあり、ティﾌﾟ読書き先端部は二番目の記号0を読んでいる。
これらの条件に適用する規則を探す。“状態q1のままにして、読書き先端部を一つ右の小区画に移動させよ”と言っている規則を見つける。これは同じ立場(状態q1にあって、“0”を読んでいる)のままにするので、読書き先端部が最終的に異なる数字1を読むまで右へ移動を続ける。
再度、規則一覧表を仰ぐ時、“1に遭遇すれば、‘却下状態’q2に変遷せよ”という新しい規則を見つける。マシーンは停止し、元々の質問“‘0001’は0なのか？”に対して“いいえ”と回答する。
代わりに入力が“#0000#”であれば、それらの0全部の後でマシーンは#に遭遇するだろう。規則一覧表を仰ぐ時、これはマシーンが“受理”状態のq3に入っていることを意味する規則を見つける。今やマシーンは質問“‘0000’は0なのか？”に対して“はい”と回答する。
抽象的なマシーンを用いて、TuringはEntscheidungsproblemに答えるために計算モドゥを確立した。Entscheidungsproblemは正式には次のことを問うている。数学公理の集合が与えられた時、提示された命題が真であるかどうかを決定出来る機械的な過程(命令の集合。それを私達は現代においてェアゥゴリズムと呼ぶ)があるのか？
或るチェスの配置が可能かどうかを告げられるェアゥゴリズムを見つけたいとしよう。ここで、公理は合法な動きを統治するチェスの規則である。その配置に辿り着く一歩づつの手続きの有限系列を私達は見守ることが出来るのか？いくつかの配置は分析するのに私達の人生よりも長くかかるかも知れないけれども(一つのェアゥゴリズムが可能な配置すべてを生成し、それらの各々を入力と比較するかも知れない)、そんなェアゥゴリズムはチェスのゲィムにおいて存在する。結果として、私達はチェスは“決定可能”であると言う。
しかしながら、1936年にChurchとTuringは(異なる手法を使用して)別個にEntscheidungsproblemのすべての実例を解く一般的方法が無いことを証明した。例えば、John Conwayのライフゲィムのような、いくつかのゲィムは決定不能である。すなわち、どのェアゥゴリズムも或る型が初期の型から現れるかどうか決定出来ない。
Turingは期待通りの仕事を実行出来るェアゥゴリズムが存在するなら函数は計算可能であることを示した。と同時に、彼はェアゥゴリズムがTuringマシーンによって定義され得る過程だということを示した。従って、計算可能函数はそれを計算するTuringマシーンを持つ函数である。これは計算可能性を定義する回りくどい方法に見えるかも知れないが、私達が持つ最良のものだ。“計算可能性を他の方法で定義する余地が無いのではない。Church-Turing論文は、ェアゥゴリズムの形式ばらない考えが任意の‘妥当’な計算可能モドゥが出来ることに相当すると言っていると一般的に受け止められていると私は思う”とthe Massachusetts Institute of Technologyの理論計算機科学者Michael Sipserは言った。他の数学者達が表面的には全く異なるように見える異なる計算モドゥを思いついて来ているが、実際には同値だ。すなわち、それらの計算モドゥはTuringマシーンが出来る任意の計算を出来るし、逆も然りである。
Kurt Gödelが完全性証明不能定理(もしくは不完全性証明不能定理)[訳注: 原文では数学が不完全云々とありましたが、殆どの日本人は論理的思考をしないと言うか、そこまで知性が無いと言うか、要は出来ないので、数学が不完全だとちょっとでも聞くと本当の意味合いも知らないで鬼の首を取ったかのようにやたらと喜ぶ馬鹿連中がいます。一般的に流布している不完全性定理という名称を避けるため正確性を期して、敢えてこのような名称にしました]を証明した後の、たった数年でChurchとTuringはこの研究で数学におけるいくつかの問題は決定不能であることを示した。すなわち、いくら洗練されていても、答えがyesかnoかェアゥゴリズムは言えない。両方がHilbertにとって壊滅的打撃だった(Hilbertは数学がきちんとした理想的な答えを持つだろうことを望んでいた)。Hilbertが望んだ、きちんとした理想的な答えはおそらく次のようでもある。すなわち、Entscheidungsproblemに対する一般解が存在するなら、数学におけるすべての問題は単なる機械的計算に還元するであろう。
これらの基本的問題に答えることを超えて、Turingのマシーンは普遍Turingマシーンとして知られる異形を通して現代的コンピュータの発展にも直接的に繋がった。普遍Turingマシーンは任意の入力ティﾌﾟ上で任意の他のTuringマシーンの模擬を行える特別な種類のTuringマシーンである。現代のコンピュータが任意のプロゥグラァムを読んで、それを実行出来るように、他のTuringマシーンの記述(その規則と入力ティﾌﾟ)を読み、普遍Turingマシーン自身の入力ティﾌﾟ上で他のTuringマシーンの振舞いの模擬を行えて、模擬をされているマシーンが作製するであろう同じ出力を作製する。1945年、John von Neumannは、普遍Turingマシーンの概念を現実のマシーンで可能にしたコンピュータ構成(von Neumann構成と呼ばれる)を提案した。
Princeton Universityの理論計算機科学者Sanjeev Aroraはこの概念を教えている時、大筋の絵画を強調する。“‘普遍’に関して二つの考えがある。普遍の一つの考えは任意の他のTuringマシーンを走らせることが出来る。しかし、他方のより大きな‘普遍’は宇宙内で思いつく任意の計算を走らせることが出来ることだ”と彼は言った。古典物理学の世界において、任意の物理的過程は模型化されるか、又はェアゥゴリズムを使って模擬され得るが、それは更にTuringマシーンによって模擬され得る。
もう一つの顕著で益々役に立つ異形は確率論的Turingマシーンだ。通常のTuringマシーン(すべての入力に対して明確な反応を持つ)と違って、確率論的Turingマシーンは確率に基づいて多重な反応を持てる。これは同一の入力に対して、異なる回数で異なる結果を生み出せることを意味する。意外にも、この種の確率論的戦略は或る問題に対して、純粋決定論的研究法よりも効率的である。確率論的Turingマシーンからのアィディヤは暗号、最適化、機械学習のような分野において実践的に役立つことを示して来ている。
これらの抽象的マシーンは、おそらく基本的問題を問うことが科学者が出来る最も役立つ事柄の一つである最良な証拠である。
コメント