  |
はてなキーワード: 同値とは
皆様は @mt25pot というTwitterアカウントをご存知だろうか？
現在は「 🙃@飲みサー画像売って下さい」というハンドルネームで運営しているこのアカウント、アカウントの名前通り飲みサー画像の”買い取り”をしている人である。
私が彼に初めて遭遇したのは昨年(2018年)の夏〜秋頃、丁度彼が飲みサー画像を買い取り始めた頃である。
当時より彼は「SEX経験者」に対する糾弾と「陽キャの異常性」について熱く語っていたことを鮮明に覚えている。
彼の実態についてはTwitterアカウント (https://twitter.com/mt25pot) を参照するのが最も早いだろう。
彼の呟きの数々は不思議と人を寄せ付ける魅力がある。かく言う私も彼に魅せられし者の一人なのだ。
では、本題に移ろう。
「ブロックチェーン」と「ビットコイン」というバズワードからこの記事を見に来た方々、何やねんコレは？と思わず是非最後までご覧頂きたい。ここからが本質である。
ブロックチェーンやビットコイン（ブロックチェーンはビットコインの中核をなす技術である）について詳しくない読者の方々（@mt25pot氏のファン層）に向けて説明すると、
ビットコインが生まれた動機とは『権威からの解放』である。かのビットコインが初め発展途上国を中心に流行りはじめたのも『自分たちの国の指導者が信頼できない』からである。
『権威が信頼出来ない』から『集権的な信頼を必要としない分散型システムによる統治』を望んだのであり、それを実現したのがビットコインだったのだ。
では @mt25pot 氏が飲みサー画像を集めたキッカケは何か。それについては彼の note によるとこう述べられている。
> 最初のキッカケとしては、どうしても抑えられない負の感情を抑える事が主目的。更に結果として、嫉妬や嫌悪感がズバズバとエロに変換されてった興奮を覚えている
（引用元：https://note.mu/mt25pot/n/nd179303f789e)
負の感情=陽キャさん達に対する不信感が飲みサー画像の公開要求に繋がったと言い換えてもよいだろう。
彼の中でこの負の感情を性欲変換するプロセスの発現はまさにパラダイム・シフトであったに違いない。
これはビットコインが生まれた理由である『社会的強者への不信感』が『透明性の高い分散型システム』を生み出したパラダイム・シフトと完全に一致する。
ビットコインは『相互監視による透明で匿名なトラストレスな社会』を実現させた。彼らは通貨の交換、取引の履歴を全て『公開』することで高い信頼性と公共性を実現したのだ。
一方で @mt25pot 氏の『透明性』についての主張は非常にこれにシンパシーを感じる。例えば以下の主張を見てみよう。
「今回の住友商事の一連騒動で、”より一層”飲みサー及びそれに準ずる行為集団は、イカれた日常を公開(最低でも欲しがる人に提供)すべきというワレの主張の『正論レベル』が上がった件。どこまで極まってしまうのか……」
(引用元：https://twitter.com/mt25pot/status/1110882509359902720)
A.普段全くリア垢を稼働させてない飲みサー所属の女さんが、嵐解散に関するツイートをわざわざ行ってる光景。滅茶苦茶モヤモヤする。
嵐解散に関する貴女の一感想なんかより、貴女が歩んでる異次元人生を世に公開していくべきじゃん………」
(引用元：https://twitter.com/mt25pot/status/1090587050779103232)
「陽キャさんのクソな所
・異性への肩組み・握手はボディータッチに含まれないwと思ってる
・イカた日常の数々を隠しに隠した上で、のうのうと生きてる(⇦犯罪者と同じ)
・そして綺麗事を連発する
・私生活と仕事での顔を分けれてる事を『素晴らしい事』だと思ってる
(引用元：https://twitter.com/mt25pot/status/1110118424217174016)
一見ネタ（明確な笑いどころを作っている）かのようにも見えるこの一連のツイートにはそれ以上に確かな彼の主義主張を含んでいることが分かる。
特に最後の「イカれた日常の数々を隠しに隠した上で、のうのうと生きてる(⇦犯罪者と同じ)」「そして綺麗事を連発する」は政府への不信感を爆発させてビットコインの初出論文を匿名で公開すること至った「Satoshi Nakamoto」の思想そのものと言えよう。
政治的な『裏の根回し』『賄賂』『利権』などのイカれた汚行を隠した上で、のうのうと『国民のため』と綺麗事を連発する現代国家に対する憂いと同値なのだ。
そして、それを解決するための策としてビットコインは全ての取引を全世界の誰もが監視できるシステムを作り上げた。
無論、そこにはプライバシーが存在する。故にビットコインでは匿名のアドレスを用いて取引を行っている。本人とこのアドレスを紐付けなければプライバシーは保たれると言ってもよいだろう。
しかし、そこに『本人であることの信頼』が必要とされた時はどうするか。
ブロックチェーン技術の応用先として金融機関のKYC(顧客の身元確認を行う仕組み)があげられているが、その実現には『本人』と『匿名のアドレス』の紐づけが不可欠である。
つまり、『社会的信頼を得る』には『常にオープンな取引を強制させられる』社会の実現こそが彼らの真の目的といえよう。
そう、これは @mt25pot 氏が提唱する『社会的強者である陽キャさん達』は『己のイカれた日常を全公開しろ』という主張と完全に一致する。
人類の平等を求める行為は人類に進化をもたらすために存在する個体差という矛盾との戦いだ。
だが、この矛盾に真っ向から立ち向かい解決する主張こそが @mt25pot 氏の主張でありブロックチェーンを用いて実現しようとしている社会なのだ。
最後に我々が目指すべき社会は何かについて述べよう。といっても “あたりまえ” のことを今から書くだけだが…。
社会的成功とプライバシーはトレードオフになるべきであり、これこそが陽キャへの抑止力にもなる。これが原則である。
“仮に” 陰キャである我々の『シコって寝る』日常を公開したところで何のデメリットにもならない。故にこの原則が試行されたとしても困らないのだ。
彼らが己のイカれた日常を隠しておきながら表立ってのうのうと意見を言っていることにこそが社会の理不尽/不条理の顕現なのだ。
それらを解決する技術の一つとして我々はブロックチェーンを提唱する。
『中央集権的第三者の信頼に頼らず』『公開された情報を相互監視することで』『在るべき社会』を実現することが可能になる。
技術の発展は常に人類の在り方を変え続けた。新たなるパラダイム・シフトは陰陽の概念そのものを破壊することを願う。私からは以上である。
P.S これを見て少しでも “理解” していただいた飲み会画像保持者は @mt25pot までご連絡いただければ幸いです。
ソシャゲーは人の金を奪う．
この糞煮込み鍋の如きソフトウェアどもはプレイするためにあらゆる手段でリアルマネーを使わせる．基本無料だから云々という文句は受け付けない．なぜならこいつらが行っているのは実質第一種価格差別であり，それは最も効率よく企業が金を吸い上げるシステムであるからだ．
要するに500円で売り切れば500円以上出してもいいと思う人だけがきっちり500円払うのに対して，基本無料で無限に課金させるようにしておけば，100円くらいなら払ってもいいかなという人が0円ではなく100円払ってくれ，5000兆円課金して全部の絵柄が欲しいとぬかす豚は500円でなくちゃんと5000兆円払ってくれるのだ．500円の価値のものに5000兆円．そういうことだ．
おれはゲームが大好きだ．これまでの人生の少なくとも1割はゲームをしている時間だと思う．それくらいに好きだ．
ゲームのプラットフォームは時代とともに移り変わってきた．昔と比べればPCでゲームをするという行為も日本に馴染んできたと思う．しかしそれ以上に，スマートフォンでゲームをするという文化は日本の奥深くまで浸透している．
おれはスマホゲーを批判したいわけじゃあない．スマートフォンの携帯性や利便性とちょっとしたミニゲームの相性は抜群だし，指一本でプレイできる戦略性の高いゲームもたくさんある．
しかしスマートフォンというハードウェアの制約上，そこには間違いなく限界がある．全てのゲームが，スマホがスマホである範疇で快適にプレイできるわけではないのだ．少なくとも今の技術では．格ゲーやFPSをタッチパネルと指でまともに操作できるとは思えない．おまえらはどうせこの一文に対して「ボクたちはできるもん！ぷんぷん！」などと怒りを顕わにするだろうが，トッププレイヤーがスマホ対CS，スマホ対PCで同じゲームを対戦してスマホプレイヤーが勝つと本気で思っているなら病院に行った方が良い．プレイヤースキルは操作性の不自由を絶対に覆さない．
要するに，スマホでゲームを作る以上実現可能なことには限界があって，それを逸脱しようとしてもまがい物にしかならないということだ．
問題は，この国ではまがい物の方が売れてしまうということである．
ソシャゲー．他のゲームから丸パクリした取ってつけたようなゲームに，いつでも制作サイドで換装可能な絵を適当にひっつけ，あとは0.00000000001%の当たりを仕込んだゴミのような宝くじを実装した，それはもうまがい物としか言いようのない廃棄物に対して消費者が金を払うというシステムがこの国では完成している．笑えるような低コストで笑えるほどに利潤が得られるのだから，近視眼的に金を得たい企業が飛びつくのは必然である．
だがそれは逆に，真にゲームを愛し，真にクオリティの高い作品を世に送ろうとする者を殺す．苦労して作ったゲームが売れない．ふざけんじゃねぇよ．
おまえらがドブに捨てた金で本当に楽しく価値のあるゲームをプレイしようという気になっていたならば，もっとたくさんのゲームがその価値を認められていたに違いない．その機会を奪ったのはソシャゲーという巨悪であり，頭を使わず楽して金儲けをする企業であり，それに金を垂れ流すおまえらだ．
ここ数年この国では毎年E-Sports元年を迎えている．競技的にゲームをすることが毎年毎年毎年毎年ちょっとずつちょっとずつちょっとずつちょっとずつ市民権を得てきた．プロゲーマーの処遇に関してもまあ色々と問題があると思うが，それはまあ本題ではないので誰か詳しい人が語ればよい．
何がダメなのか．ソシャゲーとゲームが同値であるこの国において，ゲームの競技性が向上する余地が存在しないということである．
この存在する価値のないデジタルデブリ達は金さえ払えばゲームをクリアさせてくれる．意味が分からない．お前らは何のためにゲームをしているのか．
おれは人生において金に物を言わせショートカットをすることを批判したいんじゃあない．だがこれはゲームである．敢えて言うがたかがゲームである．たかがゲームで楽をして何が嬉しいんだ．
ゲームの目的は何だ．ゲーム体験の楽しさ，クリアによる達成感，ライバルとの切磋琢磨，プレイヤー内でのランキング，そういったものだろう．その過程にリアルマネーの入る余地があってはいけない．Pay2Winはゲームバランスを崩壊させるし，課金による近道はゲームというシステム自体を否定する．金を払うことが気持ちいいなら募金でもしてろ．
しかしながら，金を払うことでゲームをクリアするのが常識になったこの国では「自らの技を磨き，実力一本で強くなろう，人に勝とう」という意識が欠如してしまうのは必然である．
実際には，日本でも少なくない数のプレイヤーが上のようなマインドでゲームをプレイしているだろう．だがその数は，日本という国のゲーム人口や市場規模と比べると驚くほどに矮小だ．なぜなら未だに大多数が，げーむにまじになることを貶め，金の力で達成感を得ることを生業にしているからだ．これでは優秀な競技プレイヤーが一向に増えないのも当たり前だ．どれだけよい品種でも，畑が干からびているなら育つべくもない．
それでもお前らはお目当てのかわいいおんなのこのために金を貢ぎたいと言うかもしれない．だがその貢いだ金はどこに行くのか．クリエイターではない．制作会社だ．お前がかわいいおんなのこにいくら払おうが，そのかわいいおんなのこに魂を吹き込んだ偉大なるクリエイターはびた一文も儲からない．お前がこれまでに失ってきた巨額の資産は，直接クリエイターに絵を描いてもらうために使ったほうが良かったんじゃないか？
はっきり言って，ソシャゲーを根こそぎ刈り取るのは不可能と言っていい．パチンコに貧乏人どもが狂喜乱舞する国で，ソシャゲーとかいう脳を眠らせたまま金を垂れ流しているだけで快楽を得られるカスのような娯楽が流行るのは致し方ない．
ならばギャンブルに倣って規制を行ってはどうか，となるわけだが，ソシャゲーに対してそれを実行するのは非常に難しい．なぜならソシャゲーとそれ以外のゲームの線引きは非常に難しいからだ．
おれは課金制度を批判したいわけじゃあない．世の中には優良な有料DLC（）が多数存在するし，それらには追加的に私財を投じる価値がある．だがそれらとソシャゲーの区別は余りに曖昧だ．個々のゲームを見て「これはソシャゲー」「これはソシャゲーではない」を論ずることはできるが，演繹的にソシャゲーの定義付けを行ったとして多数の例外が出ることはまず間違いない．結果的に課金制度そのものの規制につながりかねない．それはよくない．
そもそも一部を除いてソシャゲーは法に背いていない．お前らは自らの意思で合法的にじゃぶじゃぶ金を落としているのであって，それを理に適った大義名分で規制する術などありはしない．そしてそれらと優良なゲームの追加DLCとの間に線を引くことは，実質不可能である．
ご覧の通り，ソシャゲーはまごうことなきクソである．しかしそれと同時に，おれはそのクソをどうにかする術を何一つ提示できなかった．
結局，ソシャゲーという日本にはびこる病霜に対して，おれはほとんど無力だ．だからこうやって叫ぶしかない．
おまえらは、
今すぐ、
ソシャゲーをやめろ。
＞その結果、全体の生産性が今より落ちる可能性はあるかもしれないが
今の日本の社会・組織が抱えている問題は「過適応」。環境に適応して連続的に効率を上げていく営みは人間の本能だと自分は思うのだけど、適応が行きすぎるとそれ以上適応しなくて良くなるので、しばらくすると「筋力」を失う。『逆説的ではあるが、「適応は適応能力を締め出す」（「失敗の本質」より）』。そうすると「今いるこの局所最適点」から動けなくなってしまう。外的要因によって環境は時とともに常に変わっていくから、いまいる最適点がどんどん悪化していっても、他の場所にあるより良い最適点へ行くための山を越える力を失ってしまえば、もう身動きが取れなくなる（＝茹でガエル）。
適応力を失わないようにするには、非適応状態を意図的に注入しなければならない。（つまり筋トレ）
今叫ばれている「ダイバーシティ」「インクルーシブ」はマジョリティに対しての「非適応の注入」という捉え方もできるでしょ？どんな種類の社会の「ズレ」も、これまでの社会で最適化されて生産性に貢献してきた人達にとって生産性は下げるものになるだろう（これは最適点の定義と同値だ）。だから、「生産性下がるのが問題でしょ？」というけど下がるのは当たり前。短絡的すぎてなんの反論にもならない。大事なのは、ダイバーシティが伴う「痛み」を超えて、その山の向こうにある生産性の高い別の状態へ社会が向かえるか、そのビジョンが描けるかということだろうと思う。
https://ja.m.wikipedia.org/wiki/ガロア理論
グロタンディークのガロア理論において古典的なガロア理論は次のように理解される。K上のエタール代数はアフィンスキームSpec(K) の上のエタール層を表しており、
埋め込みK → K sep に対応する射 Spec(K sep) → Spec(K) が表す「点」でのファイバーをとることに対応する関手 FK sep: A → HomK(A, K sep)が、
圏同値 : Spec(K) 上のエタール層の圏 EtK≡ G が連続的に作用する集合の圏 BG をひき起こしている。また、絶対ガロア群はこのファイバー関手の自己同型群として実現されており、
特定の公理を満たしている関手 {\displaystyle \operatorname {F} _{K^{\mathrm {sep} }}:\operatorname {Et} _{K}\to (\mathrm {Sets} )} からガロア群を復元できることが分かる。
また、上の圏同値によって、体 K上の ガロアコホモロジーは、Spec(K) 上のエタール・コホモロジー理論と同値となる。
新幹線乗ってる間暇だったから中学高校でやってた素数について考えたわけ
そのときさ、「pがp未満かつ1でない全ての自然数に対して割り切れない」って考えたんだけど
「pがp未満の全ての素数に対して割り切れない」って同じじゃねーかなみたいなことふと思ったの
んで同値であることを証明しようと思って、んでたぶん最初の命題から次の命題を証明するのは簡単じゃん
ｐ未満の全ての素数も自然数なんだから自然数で割り切れないんだったら素数でも割り切れないじゃん
でも二番目の命題から一番目の命題のやつだとなんとなく背理法でしかわかんないのね
pがp未満の全ての素数に対して割り切れないとき、pがp未満の1以外の自然数で割り切れるとすると
その自然数がもし素数なら、全ての素数に対して割り切れないことと矛盾するじゃん
この場合素数で割り切れることになってやっぱり全ての素数に対して割り切れないことと矛盾するじゃん
だからp未満の全ての素数で割り切れないならやっぱり1以外の全ての自然数でも割り切れないんじゃね？
ってなったのね。間違ってたらすんまそん
「1以外の全ての自然数で割り切れない」ことと「全ての素数で割り切れない」ことが一緒になるって普通におかしくね？
どう見ても自然数と素数って定義違うし集合も違うのにこのことが同じになったらおかしいじゃん
命題の使い方間違ってそう
https://anond.hatelabo.jp/20180225105423
曰く、２つのグループをただ分けるのが区別。その分けた２つのグループに扱いの差を与えると差別であると。しかし、その「差別」の定義は間違っている。
差別とは、２つのグループが存在した時に、何らかの社会的／政治的／経済的／文化的な理由から、グループ１がグループ２を抑圧しているケース（＝グループ２の自由な行動が支障をきたすケース）において、グループ１がグループ２に対して行う抑圧の行為を「差別」という。
白人が黒人を抑圧しているケースにおいて、黒人を抑圧すべく、黒人専用車両を設けた場合（または逆に白人専用車両を設けた場合も）これは差別である。
一方で、黒人をその抑圧から守るために黒人専用車両を設けた場合には差別とはなりえない。
この主張は男性から女性への差別は存在するが、女性から男性への差別は原理的にありえないという主張と同値である
しかし、間違えてほしくないのは、男は常に加害者の立場の悪であり、女は常に善であると主張しているわけではないことだ（この辺りを間違えている自称フェミニストは多い）。
この話に悪も善もない。あるのは、社会規範と抑圧の事実だけだ。重要なことは、その社会的規範を認識した上で、抑圧のない誰もが生きやすい社会ルールや規範を作り上げることだ。
真木よう子の冬コミ参加に対するバッシングは、理性的に擁護できるものではない。
http://b.dlsite.net/RG11464/archives/52529122.html
コミックマーケットとは何か？ 同人誌とは何か？ というのを歴史的に詳しく紐解くのは難しいのでしない。
が、これらの意味が本質的に「アニメやゲームの二次創作」に限られないのは明確なことである。実際コミケにはまだ評論や文学、実写といった分野が生きている。
しかしながら、コミケにおけるオタクの大半は「アニメやゲームの二次創作」に興味があるし、実質的にコミケや同人誌がそういうものと同値である、とするのはもはや否定できない。
そして、今回真木よう子が出展しようとしていたものは、「アニメやゲームの二次創作」ではない。
考慮すべきは、コミックマーケットや同人誌というのは、初期の形からとっくに変質しつつあるということである。
オタクの興味がアニメやゲーム文化の隆盛とともに移り変わり、オタクの興味の代名詞が同人誌として現れているだけに過ぎず、その意味はけっして多数派が「アニメやゲームの二次創作」に興味があるから、というだけで済まされるものではない。
コミケや同人誌というのは、もっと広い範囲を許容する形式だったはずだ。
今回の真木よう子の一件は、多数派のオタクが、「今の自分のコミケや同人誌の定義や主義にふさわしくないもの」と勝手に決めつけた結果起こった悲劇に違いない。
一般のマジョリティから排除されたオタクたちの楽園がコミケであるとするならば、今のコミケはオタクのマジョリティに支配されつつある。
今後も、「アニメやゲームの二次創作」以外は、コミケのスタンスにそぐわないとか、あるいは単に売れないから、という情報や言い訳や批判が飛び交い、淘汰される危険にさらされている。
多様なジャンルの新参が二の足を踏むような状況を作ってしまえば、今勢いのある「アニメやゲームの二次創作」の有名サークルが同人誌からいつか撤退したとき、そこに何かが残るだろうか？
なんか思いついたので書く
所謂ノイジーマイノリティは静かにしとけ的な
3.9+5.1の答えが9なのか9.0なのかという問題がTV番組で取り上げられたらしく、再び話題となっているようだ。
9も9.0も数学的には同値なのでどちらでも正解なのだが、Twitterやはてなでの反応を見ていると有効数字的には9.0が正しいと主張している奴が結構いる。お前らちゃんと有効数字のことをわかって言ってるの？
有効数字を考慮しないといけないのは物理などで不確かさが発生する場合であって、こういう算数や数学の問題で有効数字を持ち出すのは明らかに間違っている。
有効数字派の人たちは3.9+5.1=9.000000000と書いたらバツにするのか？
仮に問題が3+5.1だったとすると答えは何になるのか？
有効数字を学習するのは中学校か高校くらいだと思うが、小学校教育だけでなくその上の教育も駄目だということがこの問題からわかってしまうのである。
掛け算も足し算も順序はある派。
x+dxをdx+xとか書かれたらキレる。
掛け算も、小学校のルールと逆順に書くときは、「掛ける数は演算子」だと認識するようにしている。
「3.9＋5.1＝9.0」は減点対象 小学校算数の“奇習”が議論に
これも「9.0は減点」に賛成派。「有効数字ガー」とか言ってるバカがいるが、有効数字を考えるなら、例えば「3.9＋5.01」なら8.9を正解にして8.91は不正解にしないと整合性が取れない。算数じゃなくなる。
畢竟これらの議論は、「数学的に同値だが形式的に異なる記述について、それらに異なる文脈的意味を持たせたり、一方のみを「適切」とすることにどれほどの理があるか？」という問題に帰着する。この観点を持つと、「理あり」とされているものは実は多くあることに気づく。
たとえば分数の約分。ふつう最終的な解に「2/6」と書けば減点対象だ。（でも、この書き方だって有用性はある。ピザを6等分した後なら「ああ二切れ分だな」とすぐわかるが、「1/3」だとわからない。）
小学校なら「帯分数」とかいう謎の書き方もあった。あんな奇妙な書き方、中学校以降で書いた覚えがないのだが、小学校少なくともある時期は「5/3」というような答えは減点対象だったと記憶している。
こういった「既約分数で答えよ」「帯分数で答えよ」という暗黙ルールは、「足し算・掛け算はこの順序で書け」「小数点以下の0は省略せよ」というのと本質的に同じだ。数学的に同値な書き方のうち、一方をなんらかの意図で強制させているのだ。
どのルールにも、それを強制する意図がある。「約分できることに気づかせる」「5/3は1+2/3であることを理解させる」「かける数とかけられる数、という役割の異なる数字があることを認識させる」「なるべくシンプルな形で書くことを心がけさせる」など。それに意味があるかないかは、教わった小学生たちが決めることだ。小学生たちから「自分で判断する」ことを奪っちゃいけない。
ネットに渦巻く算数教育への批判には、なんというか愛がない。小学校教員の知性への信頼も、小学生たちの知性への信頼も、全然ない。「こんなことを教える先生は頭がおかしい」「小学生にはこんな教育は混乱を招くだけだ」。そんなはずはない。先生だって交換法則くらい知っている。
小学生にも、もっと自分で考える力があるはずだ。「掛け算は交換法則が成り立つが、割り算では成り立たない。なぜか？」「かける数とかけられる数には違いがあるのか？」こういった問いかけに、自ら考えさせることこそ教育だ。子供が持ってきた答案用紙に×がついているのを見て、「先生が間違っている」という「答え」を教えてはいけない。「君はどう思う？」と問いかけることから教育が始まる。
この記事は Competitive Programming （その2） Advent Calendar 2015の12月20日の分です．12月19日はhadroriさんの競技プログラマー入門者用単語集，12月21日はroiti46さんです．
皆さんこんばんは．Mです．Advent Calendarを書くのは初めてなのでドキドキしていますが，どうぞよろしくおねがいします．普段あまり記事を書かないので anond を使わせてもらっています．
ここでは，ちょっと役立つ小ネタとして，今年書いたコードを１つ紹介します．「ビット行列を高速に乗算するコード」です．ごく簡単なコードですが定数倍効率化効果が大きいので嘘解法に使えます．
要素がブール値（True/False）であるような行列をビット行列と呼ぶことにします．このような行列に対する演算（特に乗算）はアルゴリズム理論ではよく出てきます．最も有名な例はグラフの推移包閉（各点から行ける点を全部求める）です；行列 A をグラフの隣接行列とし，和をbit-or, 積をbit-and で定義すると，行列のべき乗和「A^0 + A^1 + ... + A^{n-1}」の (i,j) 要素が True であることと，j から i に到達可能であることが同値になります．なお，このべき乗和は (I + A)^{n-1} と等しいので，高速べき乗で一発で求めることが可能です．グラフの推移包閉を求める現在（理論的に）最速の手法はこのアプローチに基づいており，計算量 O(n^\omega / log n) を達成します．O(n^\omega) は行列乗算の計算量で，現時点では \omega = 2.3728639... が最良です（Francois 2014）．また，log n は Method of Four Russians と呼ばれるビット演算を高速化する一般的なテクニックで，サイズ log n までの演算結果を全部ハッシュに突っ込んでおくものです．
さて，この Method of Four Russian というテクニックは，実際に実装してもあまり早くないことが知られています（テーブル引きが遅い・単純なループが早い）．ただし「いくつかのビットをブロック単位で計算する」というアイデアは実用的にも有用です．ブロック単位の演算をビット演算で実装できるとき，そのアルゴリズムは「ビットパラレルアルゴリズム」と呼ばれています．編集距離などの例が有名です．
ここでは，ビット行列に対するビットパラレル行列乗算を実装してみました．
A^n を計算するプログラムを書きました．実測結果を以下に示します．MacBook Pro; 2.8GHz Intel Core i7; 16GB 1600 MHz DDR3; g++ -std=c++11 -O3．実装は http://ideone.com/8AsuI2 にあります．
| n | 提案手法[s] | 通常手法[s] |
|---|---|---|
| 16 | 0.000014 | 0.000082 |
| 32 | 0.000025 | 0.000602 |
| 64 | 0.000074 | 0.004485 |
| 128 | 0.000440 | 0.036760 |
| 256 | 0.002757 | 0.311192 |
| 512 | 0.020163 | 2.847787 |
| 1024 | 0.200556 | 24.648609 |
| 2048 | 1.567657 | 205.503351 |
| 4096 | 13.894987 | --- |
| 8196 | 124.414617 | --- |
それなりに大きな n について 120倍くらい高速化しました．これだけ差があると嘘解法が通るようになります．
ビット行列を 8×8 のブロックに分割し，それぞれを unsigned long long (64bit) 1つで保存します．64が平方数というのが美しいですね．全体の乗算は8×8ブロックの乗算を普通に行えばよいので，結局 unsigned long longで表現された２つの8×8行列の積を考えれば十分です．
ここでは8×8行列の積を外積形式で実装します．外積形式というのは C = A B という積を C = (Aの1列目×Bの1行目) + ... + (Aのn列目×Bのn行目) という外積の和の形で表現するものです．各外積は，すべての列がAのk列目と等しい8×8行列とすべての行がBのk行目と等しい8×8行列の bit andに等しいので，Aからすべての列がAのk列目と等しい行列を作る方法とBからすべての行がBのk行目に等しい行列を作る方法を考えれば十分ですが，これはビットマスクして定数乗算すれば実装できます．
このコードはとある問題に対する嘘解法用に作成したものですが，結局普通のほうでも通るようになってしまったので，オフィシャルにお披露目する機会がありませんでした．
↑new
「対象を具体的に構成することによって証明可能ならば, 存在しないと仮定して云々ではなく, 実際に構成したほうがよい」あるいは「(最狭義の)背理法なしでいけるならそうすべきだ」(これらは別の主張である)という主張なら意味は通りますが. もっともこの種の議論も教育云々に属すので.
彼の意味の非背理法証明は古典論理に従う通常の証明であり構成的証明や直観主義的な証明などとは異なる. だから直観主義的型理論の証明からrealizerとしてプログラムと正当性証明を抽出する話とか, 直観主義論理の存在具体化性なんかの話とは全く関係がない.
「機械的に書き換え可能なら情報量は変わらないのでは」という簡単な突っ込みもできる. 幾らかの人達は「とはいえ計算数学なんかでは背理法に依らない証明を考えるのは意味があるのでは」といったことを述べているが
件の著書の内容紹介に【「背理法による証明」を、格段に情報量の多い「背理法によらない証明」に機械的に書き換えることができる】とある. これは, 彼の意味の背理法による/よらない証明と, 古典論理/非古典論理による証明, または非構成的/構成的証明, との対比を混同している.
---
「LKもcut-free LKも非背理法的ということではないのか. そうだとするとカット除去定理は背理法除去とは無関係ではないのか.」
他方で彼の著書では竹内・八杉『証明論入門』を引用してカット除去定理が背理法除去を一般化した定理だとも主張している. ここでひとつ反論ができるとすれば「sequent calc.も非背理法的な証明体系ではないか. 証明に現れるsequentは全てvalidではないか.」
---
他方で彼のいう非背理法証明というのはそういう状況が起こらない証明をいう. Hilbert流の証明体系では途中にprovableなformulaしか現れないことを想像せよ. したがって彼の数学としての主張は「自然演繹とHilbert流の体系は同値. よって背理法は除去できる」
実際efqを用いた証明ではefqの適用の直前に矛盾が導かれているはずだから「途中に正しくない主張が現れる」という状況に適合している.
だから彼の拒否する証明法は広義の背理法よりももう少し広いものと考えられる. 例えばex falso quodlibetがnonsenseな証明法だと捉えていることは彼のサイトの記述から明らか.
正確にいうと彼のいう背理法は「否定導入と最狭義の背理法」を合わせたもの. 背理法を拒否する根拠は「背理法を用いた証明では途中に正しくない主張が現れる」こと. 自然演繹の証明図は途中にunprovableなformulaが現れることを想像せよ.
また「背理法を用いて証明できるなら用いないでも出来る」というのは彼の言葉の定義では正しいので「直観主義論理が云々, 派生規則だから暗黙に背理法が使われてる云々」は反駁にならない.
「教育の話だろ」という人間には「教育論の補強に数学を濫用しているし, 数理論理学の教科書まで出版している」と反駁しましょう.「それでも教育的な価値は云々」という人間には「教育論として批判しているのではなく数学として批判しているのだ」と反論しましょう.
適切に批判しないと「(最狭義の)背理法なしでは(通常の述語論理の形式的体系において)証明できない命題があるなどという人間は(彼の意味では背理法なしでも証明できるので)数理論理学を理解していない初心者である」などと云われて, 傾げる首を切り取られてしまった人間が賛同するので
