いつの間にか働いて、いつの間にかGoogle Analytics をいじるポジションについていたので、これからはＡｎａｌｙｔｉｃｓ関連の記事（主に他のブログの記事の紹介）を書いていこうと思います。
体力が続く限り。
Why Is Google Analytics Inaccurate?
まずはこの記事。
Ａｎａｌｙｔｉｃｓを使ったことがある人なら誰でも一度は考える内容ですね。
「どこかで、Ａｎａｌｙｔｉｃｓの計測ミスが発生しているっぽい」
その原因について
・Google Analytics Errors You Can Fix：5個
・Google Analytics Errors You Have No Control Over：8個
に分けて解説しています。
雑学的なことですが、一度頭に入れておいて損はないかと。
備忘録のために書いておくと
・Google Analytics Errors You Can Fix
1.タグの埋め込み忘れがある
2.タグの埋め込む場所が間違っている。before the </head> tag です。
3.2つ以上のＡｎａｌｙｔｉｃｓタグが埋まってる（ダブルカウント）
4.そもそものJSがエラー（ＡｎａｌｙｔｉｃｓはJSで動いています）
5.その他細かいこと
・Google Analytics Errors You Have No Control Over
1.ユーザーがブラウザでJSブロックしている
2.クッキーが発行されていない
3.クッキーがタイムアウト
4.同じPC（ブラウザ）で違う人が訪れた（2 vistors にすべきが1 vistor になる）
5.同じ人がクロスデバイスで使用している(1 unique user にすべきが 2unique user になる）
6.後から加工できないデータ（目標は設定してからデータを蓄積しているので、過去のデータに遡れない）
7.まだ加工していない（Google analytics はリアルタイムにデータを反映させるツールではないので）
8.Google によってデータが間引かれている（データ量が多いと、一定数しか算出してくれない）
※元サイトでは7番が抜け、その分9番までありますｗ
8番目の内容については、有料版を導入すればかなりの幅までデータを出してくれるそうです、この前中の人に聞いた話では。
また、6番についてはこちらの記事も参照してみてください。
Deleting Goals in Google Analytics
2013年2月8日金曜日
2012年10月7日日曜日
停止性問題
2日ほど前、会社の同期と「停止性問題って知ってる？」と議論をふっかけてきた。
そこから1時間ほど二人で停止性問題について議論した。
二人とも分からないなりに調べ考え、停止性問題の結論を理解するに至ったが、私はもやもやが晴れずその後いろいろと考えていた。
今回はその考えた内容を書いて行きたい。
停止性問題とは http://ja.wikipedia.org/wiki/%E5%81%9C%E6%AD%A2%E6%80%A7%E5%95%8F%E9%A1%8C
このwikiがわかりづらい。
それぞれの項目が整理されていないからだ。
これを整理して考えよう。 この解説の問題点の一つは、省略すべきでないところを省略してしまっているところだ。
例えば変数と定数についてだ。
＞プログラムAにデータxを入力して実行する事をA(x)と書き、A(x)がyを出力するときy=A(x)と書く。
この表現は変数と定数がごちゃごちゃになっている。
x,yともに変数としよう。yはxによって既定される。
すなわち y=f(x) 例えばxにaという値を代入しよう、
すると (x,y)=(a,f(a)) ←x=a,y=f(a) となるわけだ。
これでx,yは変数であり、aは定数であると分かる。
（一般的にx,y等は変数を表すときに、a,bは定数を表すときに使われる）
これから何が変数で何が定数なのかをハッキリさせながら議論していきたい。
さて、停止性問題について考えよう。
その前にアルゴリズムについて解説する。
アルゴリズムとは一定のルールに従い行われる処理である。
Wikipedia先生は分かりづらいので、goo辞書を引用する。
＞ある特定の問題を解いたり、課題を解決したりするための計算手順や処理手順のこと。これを図式化したものがフローチャートであり、コンピューターで処理するための具体的な手順を記述したものがプログラムである。イランの数学者・天文学者、アル＝フワーリズミーにちなむ。
つまり一定のルールで行われる処理である。
例えばアルゴリズムAを「f(x)にx=aを代入し、算出されたf(a)をyとする」と既定する。
このようにアルゴリズムに必要なのは「一定のルール」であり、アルゴリズムを起動するに必要なのは「そのルールに見合った入力（代入）」である。
（ルールに見合った、とはルール内で必要とされている変数にあったものを入力するという意味である。先の例では変数がxである。この状態で、z=aを代入するとしても、意味がない。
飽くまでルールに見合った値を入力する必要がある）
さて、アルゴリズムによっては永遠に終わらないものも存在する。
例えばアルゴリズムBを以下の用に定義しよう。
「変数xに対して、x>0ならばf(x)=x+1とする。そしてこのf(x)を新しいxとし、再び計算する。
x<=0ならばf(x)=0とする。」
このときx=1という値を代入してみよう。
x=1>0なので、ルールに従いf(1)=2となる。そしてこの"2"を再び代入する。(x=2とする)
x=2>0なので、ルールに従いf(2)=3となる。そしてこの"3"を再び代入する。(x=3とする)
x=3>0なので、ルールに従いf(3)=4となる。そしてこの"4"を再び代入する。(x=4とする)
・
・
・
と、このように何時まで経っても計算し続けるアルゴリズムが存在する。
注意していただきたいのは、アルゴリズムBは無限に終わらない時と、有限で終わる時があるということである。
例えばx=1とすると上記のように無限に続くが、x=-1とするとf(-1)=0となり計算が終了するからである。
これは何を意味するかというと、同じアルゴリズムであっても、代入値によって挙動・結果が異なるということである。
これを覚えていて欲しい。
さて、アルゴリズムについての解説が終わったところで停止性問題について考えよう。
「与えられたアルゴリズムが有限時間で計算が終わるものか、無限に計算し続けるものかを確かめるアルゴリズムは存在するか？」
これが停止性問題である。
WikipediaによるとH(A,x)というアルゴリズムを考えることで証明しようとしている。
すなわちH(A,x)は
＞A(x)が有限時間で停止する ⇒ H(A,x)は有限時間でYESを出力して停止する。
＞A(x)は有限時間では停止しない ⇒ H(A,x)は有限時間でNOを出力して停止する。
と定義される。
ややこしいのが、ここでいうxは定数である。変数ではない。
この表現が誤解を生みやすい。
アルゴリズムHは代入値（入力）に①アルゴリズムと②そのアルゴリズムに必要な代入値を必要とする。
もう少し細かく表現すると、アルゴリズムHは代入値（入力）に①アルゴリズムAlgと②そのアルゴリズムAlgに必要な代入値(例えばx=a)を必要とする。
つまり、アルゴリズムHはアルゴリズムAにx=aを入力したときに、Aが有限時間で計算できるか否かを判断するアルゴリズムなので、必然的に入力としてアルゴリズムAとx=aを必要とする、ということである。
これ以上説明しても分かりやすくする自身はないので、アルゴリズムHの定義に移ろう。
アルゴリズムH(Alg=A(x)|x=a)は、アルゴリズムA(x)とそのアルゴリズムへの代入値x=aとして
・A(a)が有限時間で停止する場合 ⇒ H(Alg=A(x)|x=a)=0を出力して停止する。
・A(a)は有限時間では停止しない場合 ⇒ H(Alg=A(x)|x=a)=1を出力して停止する。
※A(x)とx=aの敷居に","を使わず"|"を使ったのには意味がある。それは後ほど解説する。
表記の問題であるが、Hの特質として()の中に入るものが限定されている。
H(アルゴリズム|アルゴリズムへの代入値) である。
このためH(Alg=A(x)|x=a)と表記した。
つまり「入力するアルゴリズムはA(x)である、そのアルゴリズムA(x)に入力する値はx=a」である、ということを分かりやすくもれなく表現するために、上記のような表記にした。
この表現は「Hは①アルゴリズムと②そのアルゴリズムへの代入値という2つの代入値が無いと計算できない」ということは示している。
代入値が2回出現するのでややこしい（笑）
言い換えると「Hは2つの情報をインプットする必要がある、ひとつは判定すべきアルゴリズムであり、もうひとつはそのアルゴリズムへの代入値である」
先のアルゴリズムの説明でも記したが、同じアルゴリズムであっても、代入値によって挙動が異なる。
Hについて言うとH(Alg=A(x)|x=a)とH(Alg=A(x)|x=b)は違った結果をもたらす可能性がある。
（もちろん同じ結果をもたらす可能性もある）
つまり、同じアルゴリズムであっても、代入値によって挙動・結果が異なるということである。
念を押すがこのことを覚えていて欲しい。
話を戻そう。Wikipediaでは停止性問題を証明するためアルゴリズムMを以下のように定義している。
＞M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとする。(H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。)
この説明、重要なところを省略しているうえに分かりづらい。
アルゴリズムAを使用する場合はその代入値についても言及する必要があり、そこを表記していないのである。
Wikipediaの定義では問題が多そうなのでここでは以下のように定義しよう。
アルゴリズムM(Alg=A(x)|x=a)はアルゴリズムH(Alg=A(x)|x=a)が
・H(Alg=A(x)|x=a)=0の場合（A(a)が有限に計算できる場合）、M(Alg=A(x)|x=a)を再度計算する。
・H(Alg=A(x)|x=a)=1の場合（※A(a)が無限計算になる場合）、M(Alg=A(x)|x=a)=1として計算を終了する。
ここで、前者のA(a)が有限に計算出来る場合は、再度計算させていることに注目して欲しい。
このようにわざとループさせることで「有限時間で計算できない」状況を作り出している。
Wikipediaで
＞H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。
と表記してあるのはこのことである。
分かりづらい。
さて、Wikipediaではこの後M(M)を考えるととで背理法を用いて停止性問題に結論を出そうとしている。
すなわち
＞M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
＞M(M)が停止しないとすると、Mの定義よりH(M,M)=YES。Hの定義より、H(M,M)=YESとなるのはM(M)が停止するときのみなので、矛盾。
＞よって停止性問題を常に正しく解くプログラムHは存在しない。
としている。
Wikipediaでの定義とここでの定義が異なるので、この部分をもう一度考えていきたい。
そもそもM(M)は何を意味しているのであろう？
これはM(M|A,x=a)という表記になる。
ここで"|"を使ったのはH(Alg=A(x)|x=a)の時と同じである。
つまりM(アルゴリズム|代入値)を意味する。
Mに必要な①アルゴリズムと②代入値である。
①アルゴリズム=M
しかしこのアルゴリズムM自体が代入値を必要とする。
ここで必要な代入値は
②-1アルゴリズムA
②-2そのアルゴリズムAに代入する値x=a
である。
M(M|A,x=a)ではまだ必要な情報が省略されている。
より正確な表現をするのであれば、
M(Alg=M(Alg')|Alg'=A(x),x=a) と表記するのが良い。
Alg=M(Alg')は「Mはインプットとしてアルゴリズムが必要です」ということを表している。
Alg'=A(x),x=aは「必要なAlg'をアルゴリズムA(x)、さらにそのアルゴリズムA(x)に必要な代入値xをaとします」ということを表している。
ここまで来てやっとアルゴリズムM(M)を考えることができる。
（正確にはM(Alg=M(Alg')|Alg'=A(x),x=a)を考えることができる）
ここからWikipediaの背理法の展開をなぞっていこう。
M(Alg=M(Alg')|Alg'=A(x),x=a)が停止したとしよう。
Mの定義からこの場合、 H(Alg=M(Alg')|Alg'=A(x),x=a)=1 となる。
これはM(Alg=A(x)|x=a)が有限時間で計算できず、無限に計算することを意味している。
※表記が複雑で頭が混乱するが定義に立ち返りゆっくり考えて欲しい。M(A(a)はアルゴリズムA(x)にx=aを代入したものを有限時間で計算できるかを判定するものである。
ここからが問題である。
Wikipediaによると、
＞M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
となっている。
今回の定義に翻訳し直すと、
M(Alg=M(Alg')|Alg'=A(x),x=a)が停止したとすると、Mの定義よりH(Alg=M(Alg')|Alg'=A(x),x=a)=1。
Hの定義よりH(Alg=M(Alg')|Alg=A(x),x=a)=1となるのはM(Alg=A(x)|x=a)が停止しないときのみなので、矛盾。
となる。
最後に「矛盾」とあるが、これは最初に「停止した」と仮定したのに対し、結論で「停止しない」となったためである。
だが、これは矛盾しない。
主語を入れてもう一度書いてみよう。
最初に停止したと仮定したものは「M(Alg=M(Alg')|Alg=A(x),x=a)」である。
結論で停止しないと出たものは「M(Alg=A(x)|x=a)」である。
矛盾しないではないか。
よくわからない人は、「同じアルゴリズムであっても、代入値によって結論が異なる」ということを思い出して欲しい。
M(Alg=M(Alg')|Alg'=A(x),x=a)とM(Alg=A(x)|x=a)は異なる。
両方とも代入値として①アルゴリズムと②そのアルゴリズムに代入する値を必要とする。
前者は①=M(Alg')、②=Alg'=A(x),x=aであり
後者は①=A(x)、②=x=aである。
代入値が異なるため、それぞれ違う結果が出て良いのである。
従ってWikipediaにある証明法は間違っている。
ここまで頑張ってWikipediaの背理法が間違いであるとこを証明していた。
といっても、所詮素人の主張であり、プロの目から見れば間違いがあるとは思う。
（例えば「M(Alg=M(Alg')|Alg'=A(x),x=a)とM(Alg=A(x)|x=a)はその性質上同じ結論に至らねばならない」などである。それが言えれば「矛盾」が成立する）
また私の主張が合っていたとしても、他の方法で停止性問題が証明されていれば「有限時間に計算できるか否かを判断するアルゴリズムは存在しない」という結論は変わらない（と思われる）。
いずれにせよ、楽しい思考ができた。この機会を与えてくれた同期には感謝する。
そこから1時間ほど二人で停止性問題について議論した。
二人とも分からないなりに調べ考え、停止性問題の結論を理解するに至ったが、私はもやもやが晴れずその後いろいろと考えていた。
今回はその考えた内容を書いて行きたい。
停止性問題とは http://ja.wikipedia.org/wiki/%E5%81%9C%E6%AD%A2%E6%80%A7%E5%95%8F%E9%A1%8C
このwikiがわかりづらい。
それぞれの項目が整理されていないからだ。
これを整理して考えよう。 この解説の問題点の一つは、省略すべきでないところを省略してしまっているところだ。
例えば変数と定数についてだ。
＞プログラムAにデータxを入力して実行する事をA(x)と書き、A(x)がyを出力するときy=A(x)と書く。
この表現は変数と定数がごちゃごちゃになっている。
x,yともに変数としよう。yはxによって既定される。
すなわち y=f(x) 例えばxにaという値を代入しよう、
すると (x,y)=(a,f(a)) ←x=a,y=f(a) となるわけだ。
これでx,yは変数であり、aは定数であると分かる。
（一般的にx,y等は変数を表すときに、a,bは定数を表すときに使われる）
これから何が変数で何が定数なのかをハッキリさせながら議論していきたい。
さて、停止性問題について考えよう。
その前にアルゴリズムについて解説する。
アルゴリズムとは一定のルールに従い行われる処理である。
Wikipedia先生は分かりづらいので、goo辞書を引用する。
＞ある特定の問題を解いたり、課題を解決したりするための計算手順や処理手順のこと。これを図式化したものがフローチャートであり、コンピューターで処理するための具体的な手順を記述したものがプログラムである。イランの数学者・天文学者、アル＝フワーリズミーにちなむ。
つまり一定のルールで行われる処理である。
例えばアルゴリズムAを「f(x)にx=aを代入し、算出されたf(a)をyとする」と既定する。
このようにアルゴリズムに必要なのは「一定のルール」であり、アルゴリズムを起動するに必要なのは「そのルールに見合った入力（代入）」である。
（ルールに見合った、とはルール内で必要とされている変数にあったものを入力するという意味である。先の例では変数がxである。この状態で、z=aを代入するとしても、意味がない。
飽くまでルールに見合った値を入力する必要がある）
さて、アルゴリズムによっては永遠に終わらないものも存在する。
例えばアルゴリズムBを以下の用に定義しよう。
「変数xに対して、x>0ならばf(x)=x+1とする。そしてこのf(x)を新しいxとし、再び計算する。
x<=0ならばf(x)=0とする。」
このときx=1という値を代入してみよう。
x=1>0なので、ルールに従いf(1)=2となる。そしてこの"2"を再び代入する。(x=2とする)
x=2>0なので、ルールに従いf(2)=3となる。そしてこの"3"を再び代入する。(x=3とする)
x=3>0なので、ルールに従いf(3)=4となる。そしてこの"4"を再び代入する。(x=4とする)
・
・
・
と、このように何時まで経っても計算し続けるアルゴリズムが存在する。
注意していただきたいのは、アルゴリズムBは無限に終わらない時と、有限で終わる時があるということである。
例えばx=1とすると上記のように無限に続くが、x=-1とするとf(-1)=0となり計算が終了するからである。
これは何を意味するかというと、同じアルゴリズムであっても、代入値によって挙動・結果が異なるということである。
これを覚えていて欲しい。
さて、アルゴリズムについての解説が終わったところで停止性問題について考えよう。
「与えられたアルゴリズムが有限時間で計算が終わるものか、無限に計算し続けるものかを確かめるアルゴリズムは存在するか？」
これが停止性問題である。
WikipediaによるとH(A,x)というアルゴリズムを考えることで証明しようとしている。
すなわちH(A,x)は
＞A(x)が有限時間で停止する ⇒ H(A,x)は有限時間でYESを出力して停止する。
＞A(x)は有限時間では停止しない ⇒ H(A,x)は有限時間でNOを出力して停止する。
と定義される。
ややこしいのが、ここでいうxは定数である。変数ではない。
この表現が誤解を生みやすい。
アルゴリズムHは代入値（入力）に①アルゴリズムと②そのアルゴリズムに必要な代入値を必要とする。
もう少し細かく表現すると、アルゴリズムHは代入値（入力）に①アルゴリズムAlgと②そのアルゴリズムAlgに必要な代入値(例えばx=a)を必要とする。
つまり、アルゴリズムHはアルゴリズムAにx=aを入力したときに、Aが有限時間で計算できるか否かを判断するアルゴリズムなので、必然的に入力としてアルゴリズムAとx=aを必要とする、ということである。
これ以上説明しても分かりやすくする自身はないので、アルゴリズムHの定義に移ろう。
アルゴリズムH(Alg=A(x)|x=a)は、アルゴリズムA(x)とそのアルゴリズムへの代入値x=aとして
・A(a)が有限時間で停止する場合 ⇒ H(Alg=A(x)|x=a)=0を出力して停止する。
・A(a)は有限時間では停止しない場合 ⇒ H(Alg=A(x)|x=a)=1を出力して停止する。
※A(x)とx=aの敷居に","を使わず"|"を使ったのには意味がある。それは後ほど解説する。
表記の問題であるが、Hの特質として()の中に入るものが限定されている。
H(アルゴリズム|アルゴリズムへの代入値) である。
このためH(Alg=A(x)|x=a)と表記した。
つまり「入力するアルゴリズムはA(x)である、そのアルゴリズムA(x)に入力する値はx=a」である、ということを分かりやすくもれなく表現するために、上記のような表記にした。
この表現は「Hは①アルゴリズムと②そのアルゴリズムへの代入値という2つの代入値が無いと計算できない」ということは示している。
代入値が2回出現するのでややこしい（笑）
言い換えると「Hは2つの情報をインプットする必要がある、ひとつは判定すべきアルゴリズムであり、もうひとつはそのアルゴリズムへの代入値である」
先のアルゴリズムの説明でも記したが、同じアルゴリズムであっても、代入値によって挙動が異なる。
Hについて言うとH(Alg=A(x)|x=a)とH(Alg=A(x)|x=b)は違った結果をもたらす可能性がある。
（もちろん同じ結果をもたらす可能性もある）
つまり、同じアルゴリズムであっても、代入値によって挙動・結果が異なるということである。
念を押すがこのことを覚えていて欲しい。
話を戻そう。Wikipediaでは停止性問題を証明するためアルゴリズムMを以下のように定義している。
＞M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとする。(H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。)
この説明、重要なところを省略しているうえに分かりづらい。
アルゴリズムAを使用する場合はその代入値についても言及する必要があり、そこを表記していないのである。
Wikipediaの定義では問題が多そうなのでここでは以下のように定義しよう。
アルゴリズムM(Alg=A(x)|x=a)はアルゴリズムH(Alg=A(x)|x=a)が
・H(Alg=A(x)|x=a)=0の場合（A(a)が有限に計算できる場合）、M(Alg=A(x)|x=a)を再度計算する。
・H(Alg=A(x)|x=a)=1の場合（※A(a)が無限計算になる場合）、M(Alg=A(x)|x=a)=1として計算を終了する。
ここで、前者のA(a)が有限に計算出来る場合は、再度計算させていることに注目して欲しい。
このようにわざとループさせることで「有限時間で計算できない」状況を作り出している。
Wikipediaで
＞H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。
と表記してあるのはこのことである。
分かりづらい。
さて、Wikipediaではこの後M(M)を考えるととで背理法を用いて停止性問題に結論を出そうとしている。
すなわち
＞M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
＞M(M)が停止しないとすると、Mの定義よりH(M,M)=YES。Hの定義より、H(M,M)=YESとなるのはM(M)が停止するときのみなので、矛盾。
＞よって停止性問題を常に正しく解くプログラムHは存在しない。
としている。
Wikipediaでの定義とここでの定義が異なるので、この部分をもう一度考えていきたい。
そもそもM(M)は何を意味しているのであろう？
これはM(M|A,x=a)という表記になる。
ここで"|"を使ったのはH(Alg=A(x)|x=a)の時と同じである。
つまりM(アルゴリズム|代入値)を意味する。
Mに必要な①アルゴリズムと②代入値である。
①アルゴリズム=M
しかしこのアルゴリズムM自体が代入値を必要とする。
ここで必要な代入値は
②-1アルゴリズムA
②-2そのアルゴリズムAに代入する値x=a
である。
M(M|A,x=a)ではまだ必要な情報が省略されている。
より正確な表現をするのであれば、
M(Alg=M(Alg')|Alg'=A(x),x=a) と表記するのが良い。
Alg=M(Alg')は「Mはインプットとしてアルゴリズムが必要です」ということを表している。
Alg'=A(x),x=aは「必要なAlg'をアルゴリズムA(x)、さらにそのアルゴリズムA(x)に必要な代入値xをaとします」ということを表している。
ここまで来てやっとアルゴリズムM(M)を考えることができる。
（正確にはM(Alg=M(Alg')|Alg'=A(x),x=a)を考えることができる）
ここからWikipediaの背理法の展開をなぞっていこう。
M(Alg=M(Alg')|Alg'=A(x),x=a)が停止したとしよう。
Mの定義からこの場合、 H(Alg=M(Alg')|Alg'=A(x),x=a)=1 となる。
これはM(Alg=A(x)|x=a)が有限時間で計算できず、無限に計算することを意味している。
※表記が複雑で頭が混乱するが定義に立ち返りゆっくり考えて欲しい。M(A(a)はアルゴリズムA(x)にx=aを代入したものを有限時間で計算できるかを判定するものである。
ここからが問題である。
Wikipediaによると、
＞M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
となっている。
今回の定義に翻訳し直すと、
M(Alg=M(Alg')|Alg'=A(x),x=a)が停止したとすると、Mの定義よりH(Alg=M(Alg')|Alg'=A(x),x=a)=1。
Hの定義よりH(Alg=M(Alg')|Alg=A(x),x=a)=1となるのはM(Alg=A(x)|x=a)が停止しないときのみなので、矛盾。
となる。
最後に「矛盾」とあるが、これは最初に「停止した」と仮定したのに対し、結論で「停止しない」となったためである。
だが、これは矛盾しない。
主語を入れてもう一度書いてみよう。
最初に停止したと仮定したものは「M(Alg=M(Alg')|Alg=A(x),x=a)」である。
結論で停止しないと出たものは「M(Alg=A(x)|x=a)」である。
矛盾しないではないか。
よくわからない人は、「同じアルゴリズムであっても、代入値によって結論が異なる」ということを思い出して欲しい。
M(Alg=M(Alg')|Alg'=A(x),x=a)とM(Alg=A(x)|x=a)は異なる。
両方とも代入値として①アルゴリズムと②そのアルゴリズムに代入する値を必要とする。
前者は①=M(Alg')、②=Alg'=A(x),x=aであり
後者は①=A(x)、②=x=aである。
代入値が異なるため、それぞれ違う結果が出て良いのである。
従ってWikipediaにある証明法は間違っている。
ここまで頑張ってWikipediaの背理法が間違いであるとこを証明していた。
といっても、所詮素人の主張であり、プロの目から見れば間違いがあるとは思う。
（例えば「M(Alg=M(Alg')|Alg'=A(x),x=a)とM(Alg=A(x)|x=a)はその性質上同じ結論に至らねばならない」などである。それが言えれば「矛盾」が成立する）
また私の主張が合っていたとしても、他の方法で停止性問題が証明されていれば「有限時間に計算できるか否かを判断するアルゴリズムは存在しない」という結論は変わらない（と思われる）。
いずれにせよ、楽しい思考ができた。この機会を与えてくれた同期には感謝する。
登録:
投稿 (Atom)