アカウント名:
パスワード:
まだ実装か実行が完了してないのか、それとも、もう網羅したのか気になります。１５個しかないと証明されちゃったわけではないということならそのプログラムが完成動作したらどんどん見つかるんですかね。それとも、無限に実行時間がかかるようなアルゴリズムなのでしょうか。
無限に実行時間がかかるなら定義上アルゴリズムではありえないと思いますが。アルゴリズムとは必ず停止することが保証された手続きです。
じゃあ、円周率を計算するロジックはアルゴリズムじゃなくてなんて言うんですかね
ソースは 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 に対して定義できるっていえばご満足かしら?)
それを言わなければ満足できたんだけど。再帰的だが原始再帰的でない関数の出力を計算するアルゴリズムは存在する(必ず有限時間で停止する手続きを書ける)が、具体的にいつ停止するか予想することはできない(計算量の上界が存在しない)。証明を一言でいうと、もし予想ができたら、それをもとに停止問題が解けてしまう。
いや上界は定義できる。計算不可能なだけで。計算量の上界はBB(n)以下だが、BB(n)は計算不可能というだけ。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
日本発のオープンソースソフトウェアは42件 -- ある官僚
すべての平面充填五角形を特定できるというアルゴリズム (スコア:2)
まだ実装か実行が完了してないのか、それとも、もう網羅したのか気になります。
１５個しかないと証明されちゃったわけではないということなら
そのプログラムが完成動作したらどんどん見つかるんですかね。
それとも、無限に実行時間がかかるようなアルゴリズムなのでしょうか。
Re: (スコア:0)
無限に実行時間がかかるなら定義上アルゴリズムではありえないと思いますが。アルゴリズムとは必ず停止することが保証された手続きです。
Re: (スコア:0)
じゃあ、円周率を計算するロジックはアルゴリズムじゃなくてなんて言うんですかね
Re: (スコア:1)
ソースは 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 で止めれば停止するとか、そういう条
Re:すべての平面充填五角形を特定できるというアルゴリズム (スコア:0)
> (計算量の上界を n に対して定義できるっていえばご満足かしら?)
それを言わなければ満足できたんだけど。再帰的だが原始再帰的でない関数の出力を計算するアルゴリズムは存在する(必ず有限時間で停止する手続きを書ける)が、具体的にいつ停止するか予想することはできない(計算量の上界が存在しない)。
証明を一言でいうと、もし予想ができたら、それをもとに停止問題が解けてしまう。
Re: (スコア:0)
いや上界は定義できる。計算不可能なだけで。計算量の上界はBB(n)以下だが、BB(n)は計算不可能というだけ。