【日記】Miracle sort

ミラクルソートという奇跡に依存するソートがあることを知った。

Miracle sort
A sorting algorithm that checks if the array is sorted until a miracle occurs. It continually checks the array until it is sorted, never changing the order of the array.

https://en.wikipedia.org/wiki/Bogosort

最悪計算量はO(∞)。データの置換は一切せず、正しくソートされているかどうかの比較のみ行う。何かの奇跡が起きてデータが正しくソートされた時点でソートが完了する。

（そりゃ計算量O(∞)にもなるわ）と思ったが、最近の太陽フレアの話を聞いていると、理論上はO(∞)でも現実的にはもっと小さいオーダなんじゃないかと思えてきた。

マリオ64、ＲＴＡの過程で宇宙線を使ったバグが発見される「まず太陽フレアを活性化させます」

太陽フレアというのはまあまあ聞く単語だが、人工衛星の開発分野などではよく考慮されるらしく、何らかの宇宙線がメモリなどに衝突してビットが反転してしまうことを「SEU」と呼んでいるらしい。

ミラクルソートを行うときもSEUを期待し、例えば最小限のデータ比較機能のみを備えたチップを宇宙空間に100万個ぐらい大量に浮かせておき、配列の中身は全て「1、0」の2要素にしたら、100年後ぐらいに回収したとき1つぐらいは正しく昇順にソートされてそうな気がしなくもない。

だからO(∞)というのは強すぎて、地球やその周辺で実行する分にはO(n^1000)だかO(n^1000000)か知らないが、O(∞)よりはずっとずっと弱いんじゃないかと考えていたが、ふと疑問にも感じることがあった。

SEUによるデータ置換を期待するのを奇跡と呼んでしまっているが、原理が分かっていてそれを意図的に引き起こそうとしているのならば、それは奇跡ではなく意図的な置換操作だろうと。であれば、これはミラクルソートではなく、ただの宇宙線を利用したボゴソートであるという気がしてならなくなってきた。

なのでソートが完了したとしても、その原理が後に解明されたとき、奇跡ではなく科学によって説明可能な現象に変わってしまい、すなわちミラクルソートではなくなってしまう。

本当に奇跡が起こったとすれば、未来永劫に渡ってその原理が不明でなければならず、それが奇跡と認められるのは宇宙が完全に終わるような無限に近い時間が経過したあとではないだろうか。

であればやはり、ミラクルソートは奇跡の定義から確かに計算量がO(∞)であると言える気がしてきた。計算機や科学に詳しい人はより適切な結論を導き出せるのだろうが、自分はこのぐらいで今日の日記を終わりとする。