「15番目の平面充填五角形が発見される」記事へのコメント

すべての平面充填五角形を特定できるというアルゴリズム

[kcg (26566)]

まだ実装か実行が完了してないのか、それとも、もう網羅したのか気になります。
１５個しかないと証明されちゃったわけではないということなら
そのプログラムが完成動作したらどんどん見つかるんですかね。
それとも、無限に実行時間がかかるようなアルゴリズムなのでしょうか。

Re:すべての平面充填五角形を特定できるというアルゴリズム

[Anonymous Coward]

無限に実行時間がかかるなら定義上アルゴリズムではありえないと思いますが。アルゴリズムとは必ず停止することが保証された手続きです。

Re:

[Anonymous Coward]

じゃあ、円周率を計算するロジックはアルゴリズムじゃなくてなんて言うんですかね

Re:すべての平面充填五角形を特定できるというアルゴリズム

[Anonymous Coward]

ソースは Wikipedia(笑)
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%... [wikipedia.org]
だけれども、クヌースに従うなら「computational method」らしい。

(さて、ここでアルゴリズムが停止するかどうかを判定しなければならないのだが、判定する前にはアルゴリズムとは呼べないという問題が...)

円周率の計算を n桁目で止めるなら手続きが停止する、とか、"i-block transitive tilings" の列挙(i = 2, 3, ...)を
n で止めれば停止するとか、そういう条件があればアルゴリズムですよね。
(計算量の上界を n に対して定義できるっていえばご満足かしら?)

平面充填五角形が有限個であることが証明されていないのなら、nが無限大のときに「停止しないかもしれない」
アルゴリズムは存在し得るでしょう。

Re:

[Anonymous Coward]

> アルゴリズムは最終的に必ず停止しなければならないとする定義もある。

そのwikipediaさんに「も」って書いてあるじゃねーか。

Re:

[Anonymous Coward]

それこそ[要出典]以外の何物でもない。

Re:

[Anonymous Coward]

> nが無限大のときに

チューリングマシンの空でない入力テープは有限でなければならないから、無限大というのは有効な入力ではないよ。無限に使う可能性があるのはあくまでも作業領域。無限の長さの入力テープが許されるなら、その計算能力は神託機械と同値になる(無限の入力を神託として使える)。

Re:すべての平面充填五角形を特定できるというアルゴリズム

[nim (10479)]

＞神託機械

Exadataが頭によぎるのでホントあの会社やめて欲しい。

Re:

[Anonymous Coward]

> (計算量の上界を n に対して定義できるっていえばご満足かしら?)

それを言わなければ満足できたんだけど。再帰的だが原始再帰的でない関数の出力を計算するアルゴリズムは存在する(必ず有限時間で停止する手続きを書ける)が、具体的にいつ停止するか予想することはできない(計算量の上界が存在しない)。
証明を一言でいうと、もし予想ができたら、それをもとに停止問題が解けてしまう。

Re:

[Anonymous Coward]

いや上界は定義できる。計算不可能なだけで。計算量の上界はBB(n)以下だが、BB(n)は計算不可能というだけ。

Re:

[Anonymous Coward]

「計算可枚挙」の定義に出てくるSの元を枚挙する手続きのことを何て呼ぶのかも知りたい。ていうかウィキペの定義 [wikipedia.org]では

・あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が S の元であることである。
あるいは、これと同値だが、
・S の元を枚挙するアルゴリズムが存在する。つまり、その出力は S の元のリスト s1, s2, s3, ... である。このアルゴリズムは必要ならば無限に動作する。

って思いっきり書かれてるじゃねーか(どっちの定義も「アルゴリズム」が停止しない可能性があることを前提にしている)。