元のスレッド
【ふぃっしゅ数】巨大数の探索スレ【ばーど数】
- 264 名前:132人目の素数さん
:02/11/07 08:05
- >>241
> 「プログラミング可能であれば、必ず一定の状態数を持つ
> チューリングマシンで表現できる」というのは早計ではないか?
その発言ははっきり早計です。
> もしそうだとすれば、ビジービーバー関数をシミュレーション
> で求めるプログラムを一定の状態数を持つチューリングマシンで
> 表現できることになり、矛盾を生じないか?」
ビジービーバー関数は決してシミュレーションでは求まりません。
つまり一定の状態数を持つチューリングマシンでは表現できません。
この件に関しては、計算論に関する基本的な教科書
"Computability and Logic" Boolos and
Jeffrey (Cambridge Univ. Press)
をお読みください。
- 265 名前:132人目の素数さん
:02/11/07 08:11
- >>245
>ビジービーバー関数の定義を見て、
>なんだ、チューリングマシンにビジービーバー関数を取り込めば
>新しいビジービーバー関数ができて、これはビジービーバー関数から
>formal
systemで定義できないほどの大きさの関数になるんじゃないのか?
>と思って、ロバートさんにメールを送ったのですが、
>ロバートさんは「そんなことはできない」と簡単に否定しました。
当然でしょう。チューリングマシンにビジービーバー関数は取り込めません。
それはビジービーバー関数の定義に反します。あなたの目が節穴でなければ
必ずそのことに気づくはずですから、気づくまで何度でも読み返してください。
貴方の考えに反することだとしても、それにひたすら耐えることが必要です。
- 266 名前:132人目の素数さん
:02/11/07 08:14
- >>245
>「そんなはずはなかろう、同じ発想をしている人は
>いるんじゃないのか?」と思い、よく調べてみると、
>それがまさにO-machinesだったわけです。
その時点で、計算可能関数を超えてしまい、game overです。
>どうも、ロバートさんは
>「ビジービーバー関数よりも大きな関数は定義できない」
>という風に思いこんでしまっていたようです。
>それとも、プログラムで書けるものだけが関数だ、
>と考えているのがプログラム屋さんなのでしょうか。
あなたが定義の意味を明確にしなかったことが問題です。
ロバート氏は、あくまで計算可能関数としてプログラムで
書けるものを「定義」だと明確に考えています。
つまり、ロバート氏のルールでは、貴方の完全な敗北です。
- 267 名前:132人目の素数さん
:02/11/07 08:16
- >>245
>数学的な目から見ると、プログラムで書けようが書けまいが、
>明確に定義されていれば関数なのですが。
それは卑怯な言い訳でしょう。
あなたはゲームのルールを守れない
自分勝手なバカだと自分で言っている
ことになりますよ。
- 268 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/07 10:38
- >>264
はい、早計でした。勉強してみます。
- 269 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/07 10:40
- >>265
>>245が
O-machines と本質的に同じアイディアだということは
無理に否定していただかなくても、ロバートさんも認めていることです。
ロバートさんに、
It is my great honor that I reached the same idea as
Turing before
knowing his work. :-)
というメールを送ったら、
Yes, I
agree (-:
といっていただきました。
O-machinesは、チューリングマシンとは違いますが、チューリング
マシンに計算不可能関数を取り込んだと表現してもそんなに間違い
ないのでは。
- 270 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/07 10:41
- >>266
まずは「定義」の定義ですが、
1. well-defined function という意味での「定義」「関数」
2.
algorithmic definition, computational function
という意味での「定義」「関数」
の2種類があります。
計算可能関数を超えた時点でゲームオーバーだというのであれば、
そもそもビジービーバー関数を出した時点でゲームオーバーです。
- 271 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/07 10:42
- >>267
ご指摘の通り、ゲームのルールをはっきりさせることは大事ですね。
とても貴重な指摘をありがとうございます。
このスレも、計算不可能な数を「なし」とするルールと「あり」と
するルールを明確に分ける必要がありそうです。
計算可能オンリー部門:
グラハム数、バージョン1、チェーン関数、バード数、
バージョン2、バージョン3
計算不可能あり部門:
ビジービーバー関数、O-machines、バージョン4
といった感じで。
もっとも、計算可能というのは理論的な話であって、
現実的にはどの数も計算不可能ですが。
- 272 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/07 10:43
- ただ、あらためて発言を読み返してみると、なんだかロバートさんを
馬鹿にしているようにも読める個所がありますね。
書き方がまずかったようです。その点は大いに反省。
ロバートさんには、とても有意義な議論をしていただきました。感謝。
- 273 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/07 10:54
- >>271
なんだか、こうやって部門を分けてしまうと、バージョン3と
ビジービーバーを比較する気が急激に失せてきたな。
なにしろ、エントリーしている部門が違うわけだし。
- 274 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/07 11:04
- ちなみに、こんな感じのメールを最初は送りました。これは、O-machines
について知る前です。けっこういい発想だったと思うんですが、だめですか?
Busy Fish function was defined
by using Busy Beaver function and
formal system. If we can define "Hyper
Beaver function" such that
any function expressed in terms of Busy Beaver
function and
formal system (including Busy Fish function) is not larger
than
Hyper Beaver function, such function is justified to be called
as
"significantly larger" than Busy Beaver function. The question
is, how can
we define such large function?
Maybe Hyper Beaver function can be
defined by using Hyper Turing
Machine, where Busy Beaver function is
implemented as a built-in
function. Once the protocol of defining higher
rank of function,
f(x) -> g(x), is fixed, such function (or mapping)
from function
to function can be expressed as C(f(x))=g(x), where g(x) is
larger
than any function expressed in terms formal system using f(x).
Defining BB_n(x)=C^n(x+1) gives n-th level of BB function, where
BB_1(x)=BB(x), and increasing the level of BB function significantly
increases the scale of the function. BB_x(x) may be termed as Hyper
Beaver function, and ... (to be continued indefinetely)
- 275 名前:132人目の素数さん
:02/11/07 22:24
- >>267
じゃあ、あなたが我々を圧倒する大きな数・関数を提示してみれば?
少なくともふぃっしゅさんは、このスレで我々をずいぶん楽しませてくれたよ。
は、このスレには以外は本当にいいスレだったんですよ
- 276 名前:132人目の素数さん :02/11/08 01:09
- まあまあ
- 277 名前:名無しのような物体 ◆plq.mziK0E :02/11/08 01:51
>>264-267さんは(おそらく=261でしょう)一見すると荒らしの様にも見えますが、
少なくともチューリングマシンやビジービーバーなどに関しては
このスレにいる誰よりも知識をお持ちのようです。
この分野に関してもう少し詳しいお話を伺いたいものです。
告白しますと、私は当初からふぃっしゅ数(関数)が
ビジービーバー関数を超えると言う話には懐疑的でした。
その最大の理由は、BB(x)がそもそも計算不可能であると言うことです。
(個人的には、定義中に式が一切出てこないようなものを「関数」と呼んで良いのか、とさえ思っています)
しかしながら、前述したように私は数学を専門にしているわけではありませんし、
また英語力の不足もあって、「いかなる関数もBB(x)を超えることはできない」
というMunafo氏の主張を理解する段階でずっと足踏みしたまま、今日に至ったと言う次第です。
また、O-machines、すなわち「オラクルつきチューリング機械」云々に至っては、
感覚的に「そんな馬鹿な」と思ってしまっておりますが、
具体例のようなものが何一つ見当たらず、意見することもままならない状況です。
ふぃっしゅっしゅさんや264さんには、これが全体どんな物なのか
噛み砕いて説明していただきたい次第です。
このスレは数学板屈指の良スレに違いありませんが、いかんせん人材が決定的に不足しております。
(下手するとさくらスレよりも!?)
ですので、機会を見て数学板や情報システム板の他のスレと接触を持ち、
知識ある人々を積極的に集められたら良いな、と考えています。
ただ、264さんも含め、ここではひとつマターリでよろしくおながいしますです。
- 278 名前:264 :02/11/08
07:15
- >>277
>(おそらく=261でしょう)
偽
>私は当初からふぃっしゅ数(関数)が
>ビジービーバー関数を超えると言う話には懐疑的でした。
>その最大の理由は、BB(x)がそもそも計算不可能であると言うことです。
あなたは正しい。
- 279 名前:264 :02/11/08
07:19
- >>277
>O-machines、すなわち「オラクルつきチューリング機械」云々に至っては、
>具体例のようなものが何一つ見当たらず、意見することもままならない状況です。
ここでいう具体例が、実際に動作する機械を指すなら
そのようなものは未だ知られていない。
それは数学的な概念である。
- 280 名前:264 :02/11/08
07:24
- >ここではひとつマターリでよろしくおながいしますです。
そのような無駄口を叩く前に、「ルール」を提案するべきだろう。
「最大数」を競う場合、何らの制限も設けないのでは意味がない。
例えば、「**字以内のプログラムで計算できる」とかいう
制限を設けるべきである。
ちなみに、上記「」の制限はビジービーバーの定義と同等であり
**字という入力から、最大数という出力を導く関数は、計算
不可能である(つまり有限の字数のプログラムとして表現する
ことが不可能)であることは、ふぃっしゅっしゅ氏ならずとも
いわずもがなだろう。
- 281 名前:旧695 :02/11/08 12:14
- ぶっちゃけ馴れ合いスレだと思ってます(´ー`)
- 282 名前:名無しのような物体 ◆plq.mziK0E :02/11/08 12:29
- >>280
やけに文面が荒んでますね・・・・・・このスレの何が癇に障るんでしょう?
と、それはさておき、このスレは「巨大数を探索するスレ」ではありますが、
「最大数を競う」つもりは毛頭ありません。
というのも、ご存知のようにそもそも「最大の数」というものが存在しないからです。
実は前スレが他でもない「最大数を競う」スレだったのですが、
9や^をひたすら書き込む者や>>○○の数+1と書く者が最後まで後を絶ちませんでした。
その反省を基にこのスレでは競争的な要素を排除することにしたのです。
「超える」「超えない」という言葉が出てくることもありますが、それは値がどうのと言うより
その巨大さを生み出す本質的な「概念」を追及しているのだと私は解釈しています。
・・・ちなみに、このスレでも完璧に忘れ去られてますが、字数制限部門、というやつが一応あります。
(>>19-20参照)
>>279
チューリング・マシンがあくまで数学的な概念上の存在であることは存じております。
しかしながら、普通のチューリングマシンについては、具体例をあげて解説しているサイトや
マシンをシミュレートするソフトを配布しているサイトも少なからず存在しています。
とにかく、かの「オラクル付き」を英語の文章だけで理解するのはかなりしんどいです。
図入りで説明してくださるのが理想なのですが、2chでそれは大変でしょうから
せめて日本語で、どんな感じで動くのかだけでも教えていただけると有り難いです。
- 283 名前:ふぃっしゅっしゅ ◆XOeqGyYvc.
:02/11/09 00:07
- O-machines を使った関数を関数の仲間入りさせていいのか?
これはとても興味深い問題ですね。しばらく考えた結果、
私の中で結論が出たので書きます。もちろん、私の結論を
覆す反論は、常に大歓迎です。
計算不可能かつ
well-defined な関数f(x)をオラクルとして
持つ O-machines によって生成されるビジービーバー関数を
g(x)とする。このとき、g(x)は計算不可能かつ well-defined
な関数である。
ビジービーバー関数BB(x)も、g(x)と同様に計算不可能かつ
well-definedな関数である。
したがって、
(1) BB(x)を関数であると認める立場からは、g(x)も関数で
あると認められる。この場合、関数とは well-defined
な
ものである、と定義できる。
(2) BB(x)は関数でないとする立場からは、当然g(x)も関数で
あると認められない。すなわち、関数とは計算可能なもの
である、と定義したことになる。
(3)
BB(x)を関数と認め、g(x)を関数と認めないという立場は、
矛盾している。関数の定義が定まっていないことに気がつく
必要がある。
- 284 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/09 07:14
- >>277
「いかなる関数もBB(x)を超えることはできない」
この点についてロバート氏の主張を一度は理解したものの、
よく考えるとこの表現はおかしいことに気がつきました。
なぜならば、この表現は「BB(x)は最大の関数である」ということと
同値です。ところが、最大の関数は存在しません。
f(x)+1 > f(x)だからです。単調増加関数であれば f(x+1) >
f(x)です。
したがって、必ず
「いかなる計算可能関数もBB(x)を超えることはできない」
と正確に表現する必要があります。
最大の計算可能関数は存在しませんし、最大の計算不可能関数も
存在しません。最大の関数があるがごとき誤解を与える表現は
厳に慎むべきです。
BB(x)関数を定義した時点で、私たちの慣れ親しんでいる
計算可能関数から計算不可能関数の世界へ、関数の世界が拡張
されたことになります。ひとたび計算不可能領域へ関数の世界を
拡張したからには、O-machines は計算不可能だから意味がない、
という主張はナンセンスです。O-machines は計算をさせる
ためにあるのではなく、数や関数を定義をするためにあるのです。
計算機ではなく、定義機とでも言うべきものです。
#
トリップキーを打ち間違えたようですが、>>283は私です。
- 285 名前:264 :02/11/09 09:03
- >>282
君、自意識過剰。
>このスレでは競争的な要素を排除することにしたのです
しかし、そのために目的を排除するのは無意味。
>チューリング・マシンがあくまで数学的な概念上の存在であることは存じております。
君、文章を読み間違っているよ。
僕が数学的な概念だといったのは、「オラクル」のこと。
「オラクル」が英語でどういう意味か知ってるだろ
どうやって動くかわからないから、「オラクル」なんだよ。
- 286 名前:264 :02/11/09 09:07
- >>284
>「いかなる関数もBB(x)を超えることはできない」
ここでいう「関数」はもちろん計算可能な関数のこと。
ロバート氏はBB(x)が計算不可能であることは承知の上で
言っていることはあきらかで、それを否定するのは愚の骨頂。
小学生なみの知識しかないのに、大学生のような態度で
語ることこそ厳に慎むべきだろう。
- 287 名前:264 :02/11/09 09:14
- >>284
>BB(x)関数を定義した時点で、私たちの慣れ親しんでいる
>計算可能関数から計算不可能関数の世界へ、関数の世界が
>拡張されたことになります。
同時にGame Overとなったことも認めざるをえない。
定義ごっこはただの駄弁り。このスレももう終わりだな。
- 291 名前:132人目の素数さん :02/11/09 09:53
- えーと、初めまして。
某大学で計算論を専攻しているD2です。
A先生の下、といえば、どこの大学かわかるかな・・・?
(研究室の人数が少ないので、大学がわかられちゃうと困りますが。(^^;))
このスレを初めて見たのですが、とても興味深いと思います。
私の周りにも定義とかルールが曖昧な土台の上であれこれやるのは無意味、
といった考えの者が多いのですが、私はそんなことはないと思います。
確かにそのままの形で数学に持ち込めるかどうかは疑問ですが,
数学に持ち込めなくても面白ければ有意義だと思うし(別に論文書く
わけじゃなし)、一見「数学的に無意味」そうなものでも、そこから
数学的なエッセンスを抜き出すのが数学的能力の1つでしょうし。
あいにくと私は滅多にインターネットをしませんので、
次に来るまでにこのスレッドが残っているかどうか心配ですが、
残っていれば嬉しいです。ではでは。
- 292 名前:264 :02/11/09 09:58
- >>288
君、Ver3がご自慢のようだね。
でも、残念だけど、もしVer3でいう「一般化」がプログラミング可能なら
まったく陳腐な方法でVer3を超えられるよ。
それは一般化のプログラム自身をS・・・なんたらに組み込んでしまうことだね
それをSωとでもしようか。ま、順序数を拡張する基本だね。
これを際限なく続けて、Ver3.1、Ver3.14・・・と増やすのは随意だけど、
そうしたところで、Verπは超えないな。
実はこのVerπこそ、BB(x)と同じく君らの不遜な試みを打ち砕く壁
なんだ。つまり「究極の一般化」はプログラムとして記述できない
わけだな。
- 296 名前:264 :02/11/09 10:05
- >>292の補足
>>243
>ロバートさんによれば、LISPやSmall Talkには、
>自分自身をコンパイルする能力があるから、
>プログラム可能になるそうです。
>>292でいう拡張は、メタプログラムを用いるから、
上でいうような機能を必要とするだろう。
- 297 名前:264 :02/11/09 10:08
- >>291
D2なら、この手のことは計算論の常識であることは先刻ご承知のはず。
- 301 名前:291 :02/11/09 10:18
- 放置らしいので私も放置しますが。
(と書くのは「放置」の定義に反するのかな?)
まあしかし、このスレッドの趣旨が理解できていないのもさることながら、
的外れな指摘をするために「計算論の常識」を振りかざされるのは、
正直、専門家の卵としては不愉快ですね。
みなさん、計算論を勉強した人が皆ああいう人種だとは思わないでくださいね。
私も徹底放置に賛成しておきます。また逢うときまでごきげんよう。
さて、論文の続きに戻るか・・・。
- 302 名前:291 :02/11/09 10:21
- 念のため言っておきますが、>>301の「専門家の卵」とは、私のことです。
断じてアレのことではありませんので。もし万が一、アレが計算論の専門家を
目指してたり、専門家だったとしても、私は「専門家(の卵)」とは認めませんね。
ではでは、今度こそごきげんよう。
- 338 名前:名無しのような物体 ◆plq.mziK0E :02/11/10 11:02
- ・・・・・・・・・・・・・・・引き続き、良識ある専門家(卵含む(笑))のご意見をお待ちしております。
オラクルの謎は未だ解けず。ふぃっしゅっしゅさんはどこまでご存知なのでしょうか?
- 339 名前:132人目の素数さん :02/11/10 17:18
- >264は、たぶん自分で巨大数を提示するようなことはしないだろうね
それが賢明な態度ですよ。
「一見、順序数から順序数への連鎖におけるそれらの不規則性は、
コンピュータプログラムで処理できるだろうと思われるかも
しれない。すなわち、新しい名前を規則的に生成するプログラム
があって、もしそのガソリンが切れたときは、新しい名前を供給
する「不規則処理業者」を呼び出し、処理がすんだら簡単な
プログラムに仕事を戻す、ということである。しかしこれらは
うまく働かないようである・・・」
- 340 名前:132人目の素数さん :02/11/10 17:24
- 「不規則性は不規則な仕方で起こるので、第二階のプログラム−すなわち
新しい名前を作るプログラムを作り出すプログラムが必要になる。
そしてそれでも不十分なので、いずれは第三階のプログラムが必要になる。
以下同様に続く。
こういうおそらくは奇妙に見える複雑さは、Alonzo ChurchとStephen.C.
Kleeneによる、ある深い定理から派生している。それは「無限順序数」の
構造についての定理で、次のことをいっている。
”すべての構成的順序数に名前を与える、再帰的に関係づけられた記号法は
存在しない”」
- 341 名前:132人目の素数さん :02/11/10 17:59
- >>「264は、たぶん自分で巨大数を提示するようなことはしないだろうね」
>>それが賢明な態度ですよ。
264が言ってることが妥当な考察だとしても、レスする人を馬鹿にする資格は無いと思う。
もし、仮に>>340のような意味を理解して欲しいという「意志」があるなら
それなりの態度でレスをしなければ周囲の反感を買う事くらいは学生でもわかるはず。
ここで言う態度とは、このスレの経過を理解し、その流れをある程度尊重して発言をするという意味です。
絶対的な巨大数が存在しない事やその値を大きく求めれば求めるほど
不確定的要素に支配されていくなんて事はみんな承知の上でレスしている。
はっきり言って264のレスからは「お前らのやってる事は意味が無い早くやめろ」
としか意志が伝わってこない。
つまり、人をこきおろすような大きな態度を取っていながら自分からこのスレのために
時間を裂いたり、検討しようという姿勢が感じられない以上、このスレにおいて賢明な態度
とはとうてい認められない。別に奴を我々が請うて呼んだわけじゃない向こうが勝手にきただけ。
例えて言うと、みんなが一生懸命働いてる職場に来て、あのやり方が悪い、こいつはバカ
だと偉そうに言って何もしない奴が周囲の反感買ったとする。そいつが仕事をやればそれでも
少しずつは認めらるだろう、そしてそいつの仕事のやり方が斬新だったりすれば周囲もそいつの
ことを認め、へらず口に少しは耳を傾けることにもなるだろう。
そういう事を言ってんだよ。
- 342 名前:132人目の素数さん :02/11/10 18:06
- 読者の中には、順序数はこの議論とは関係がないと思う方もいるかもしれないが
決してそうではない。
巨大数の議論は、つまるところ、関数の増大度競争であり、そのランク付けである。
このランク付けが、実は順序数になるのである。
ふぃっしゅ関数の「ヴァージョンアップ」には危険な飛躍が含まれている。
つまり一般化が「プログラミング可能」かどうかの議論が為されていない
ことにある。
もし一般化がプログラミング可能な関数全体に及んでいる場合には、
それ自体はプログラミング可能ではなく、ビジービーバー関数と同じ
「計算可能関数の上限としての計算不能関数」に成り果ててしまう
恐れがある。
- 343 名前:132人目の素数さん :02/11/10 18:15
- >>341
264の発言は、このスレの活動を完全に否定するものではないと思う。
一切の感情を抜きにすれば、264は「プログラミングの可能性」を第一に
考えるべきだといっていると思う。それが皆が無意識のまま看過している
このスレッドの実際の経過と流れを完全に厳密に統制する原理であることは
誰も否定することはできないだろう。
それを理解することなく、ただ自分たちが否定されていると勝手に怒るのは
嵐と同じであって、有害無益の存在である。怒るならこのスレッドから即刻
立ち去るべきだろう。つまり問題なのは264ではなく貴方だということだ。
- 344 名前:132人目の素数さん :02/11/10 18:45
- >>343
あなたのレスは前半はいいとしても、やはりちゃんと意を解してない。
じゃあ聞くが、あなたは「小学生並みの知識で大学生なみに語るな」とか
自分と意見が相違する人に向かって「もうくるなよ」(こいつは、来たばっかりなのに)
あげくの果てには「このスレはもう終わり」とか言ってるんだよ。
(あなたは、264の発言は、このスレの活動を完全に否定するものではないと思う。〜だそうだが)
さんざんスレの存続や保全や数の解析に時間をかけて来た人だっているんだ。(695さんなど)
あなたが、さんざんやってきた事をこのように言われた時に、そいつに不快を催さない
はずは無いと思うよ。
スレの中身の前に、そういう低いレベルの話をしてるんだよ。
- 347 名前:132人目の素数さん :02/11/10 21:19
- >>342
順序数って、なんですか?
ご覧の通りこのスレの常連で数学の専門家はふぃっしゅっしゅさんただ一人です。
専門の知識を披露する際には、素人にも(多少は)分かるように配慮してください。
もし、分かるヤシとしか会話しないと言うなら、良いからとっとと退場してください。
- 348 名前:132人目の素数さん :02/11/10 21:40
- >>346
「いろいろ言われる」のが快感な奴も世の中にはいるんだよ。
そういう奴にいろいろ言うのは、単に餌を与えているだけで、
却って調子に乗って今回のように自作自演でレス付けまくってくるので逆効果。
俺もふぃっしゅ数をつくり出し考察してきたみなさんには敬意を表してるし、
感謝もしている。が、だからこそ文句付けるだけの奴は無視すべきだと思う。
・・・ああしかし、ここで俺とあなたがつまんない喧嘩してしまったら、
それこそ誰かさんの思う壺だな。
まあ、お互い自分のやり方でこのスレを愛していこうぜ、ってことでひとつ円満に。
- 349 名前:旧695 :02/11/10 21:44
- つまり順序数とプログラミング可能かどうかがミソなんですね。
順序数でググルしたら無限の話をしているところだらけでぁぅぁぅして
しまいましたが。プログラム云々はさっぱわかりませんヽ(´ー`)ノ
無駄っつうかこのスレで「すげえ(゚Д゚)でけえ」と何度かカタルシスを
得られたのでそれはそれでオッケー、みたいなヽ(´ー`)ノ
- 350 名前:132人目の素数さん :02/11/10 23:03
- >>まあ、お互い自分のやり方でこのスレを愛していこうぜ、ってことでひとつ円満に。
>>同意
ところで、昨日でかい数つくるからちょっと待っててって言ってた人はどうしたんだろ
今日レスされれんじゃないかと、ちょっとばかし楽しみにしてたんだが‥‥。
- 351 名前:132人目の素数さん :02/11/10 23:23
- レス見ててふと思ったんだが、巨大数巨大関数に大して真正面から取り組んで
バカらしいまでの長い定義を検証したりするのって、数学の専門家じゃない人の
方が向いてるみたい、少なくてもここまでは。 これは予想だが、そういう人の
方が数学の専門の人が持つある種の「恐れ」や「自己規制」や「達観」が無い分
純粋に、あるいは怖いものしらずにその中身に突き進んでいってるのだと思う。
だからこそ、専門知識が他の人よりありそうなふぃっしゅしゅ氏がこのスレに
けっこうマメに情熱を持ってレスしてるのが、すごく意義深い気がする。
ただし、知識の無い我々としては識者の提言に謙虚に耳を傾け、糸を解いてい
くしかないわけで、その姿勢が無くなったら、単なるお遊びになってしまう事も
充分留意しておかねば。
旧695さんが書かれたカタルシスこそ、このスレの目的で醍醐味なんですよね。
また、それを味わってみたいです。
- 352 名前:264 :02/11/11 21:08
- 巨大数に関して、ちょっと調べさせてもらったが、これは私の想像を超える
面白みを持っていることがわかったので、当初の、当スレッドの意義を疑問
とする態度の表明は全面撤回する。
私が興味をもったのは、Bird氏の関数でもFish氏の関数でもなく、
それ以前のConwayのchain関数であった。
Ackermanの関数が自然数の三つ組を引数とするものだとすると
Conwayのchain関数は自然数のリストを引数とするものである。
私が考えるに、上記の関数は自然数そのもの、および自然数の組
による乗法関数の延長線上にあるものと考えられる。
これを踏まえれば、chain関数を拡張する「ある自然な方法」が想定される
のであるが、これに関しては、現在考察中であるので今は発表の段階にない。
- 353 名前:264 :02/11/11 21:15
- (追伸)
>chain関数を拡張する「ある自然な方法」が想定される
これはもちろん、chain関数同様、プログラミング可能な拡張である。
- 354 名前:132人目の素数さん
:02/11/11 22:29
- なんか一気に264キャラ変わったな。(もともとスレに参加したかったんでは?)
まあ、いいことだ。数学的知識豊富そうなので
ところで、324氏の月曜までの、でっかい数はどうしたんだろう?
- 355 名前:132人目の素数さん :02/11/11 22:33
- 結局BB関数は、このスレでは検証不可能ということなのかな。
どれくらいの増大を示すのか、さわりだけでも知りたいなあ。
- 356 名前:132人目の素数さん :02/11/11 22:38
- chain関数って、ちぇ−ん関数とは別のものだよね?
- 357 名前:名無しのような物体 ◆plq.mziK0E :02/11/12 12:51
- >>352
Conway's chain の拡張と言うと、やはりこれをあげないといけないでしょう。
ttp://uglypc.ggh.org.uk/~chrisb/maths.pdf
でも264さんの事だから、これと異なる次元での拡張が期待できる予感。
>>354
・・・まあ、急ぐ旅でもありませんし、のんびり待ってみましょう。
>>355
BBはふぃっしゅ関数などと違って、定義に従って1から計算、というわけには行きませんからね。
現職の数学者が解析している最中な程ですから、このスレでの解析は期待しないほうが・・・。
- 358 名前:264 :02/11/13 07:09
- >>357
Bird氏のMultiple・・・とかRevolving Allow等の拡張はみました
あれはchainが分かってしまえば誰でも思いつくでしょう。
ところで、Conwayの chain
notationのプログラム(?)を
書いてみました。
chain([c0,c1,c2…])
=if
([c1・・・]=nil)
then c0
else if (c0=1)
then chain([c1,c2…])
else
chain([c0-1,chain2(c0,[c1-1,c2…]),c2…])
chain2(c0,[c1,c2…])
=if
([c2…]=nil)
then c1^c0
else if (c1<=1)
then chain([c2…])
else chain([c0-1,chain2(c0,[c1-1,c2…]),c2…])
- 359 名前:264 :02/11/13 07:16
- >>346
>ふぃっしゅ数のヴァ−ジョンアップに対しては
>695さんや名無しの物体氏等が解析している・・・
Fish氏のやり方で、理解できたのは最初のS変換だけ。
その後は、アルゴリズムとして記述しようにも
何がどうなっているのか全く明確でないように思う。
695氏や名無しの物体氏の「計算」も他人には
何をやっているのか分からないように思う。
- 360 名前:264 :02/11/13 07:22
- Fish氏は、自分のアイデアについて、ホームページを立てて、
その定義を、誰にも分かる形で記録する必要があると思う。
また、695氏もしくは名無しの物体氏は、Fish氏の定義について
自分の理解にもとづく計算プログラムを、具体的に明示する
必要があると思う。
- 361 名前:264 :02/11/13 07:28
- >>358
>Conwayの chain notationのプログラム(?)を
>書いてみました。
cn→c(n-1)→・・・c2→c1→c0を、リスト[c0,c1,c2・・・]とあらわしています。
---
chain([c0,c1,c2…])
=if ([c1・・・]=nil)
then c0
else if (c0=1)
then chain([c1,c2…])
else chain([c0-1,chain2(c0,[c1-1,c2…]),c2…])
chain2(c0,[c1,c2…])
=if ([c2…]=nil)
then c1^c0
else if
(c1<=1)
then chain([c2…])
else
chain([c0-1,chain2(c0,[c1-1,c2…]),c2…])
- 362 名前:264 :02/11/13 07:41
- >(BB関数は)どれくらいの増大を示すのか、さわりだけでも知りたいなあ。
今知られている結果についてはこちらを御覧下さい。
ttp://www.drb.insel.de/~heiner/BB/index.html
- 363 名前:264 :02/11/13 07:48
- >>363
ついでにRobert Munafoさんの隠れページも発見
ttp://home.earthlink.net/~mrob/pub/math/ln-notes1.html
- 364 名前:132人目の素数さん :02/11/14 00:23
- なんか別人のようになってしまった264氏
しかし本スレとしては強力な戦力になりそうな予感
Fishさんも入魂の大量レス以来お見かけしないですねえ
- 365 名前:132人目の素数さん :02/11/14 01:02
- >>360
ホムペなんぞ立てんでも前スレで十分。
http://science.2ch.net/test/read.cgi/math/1024311743/320-379
↑この辺でふぃっしゅ数(ver.1)の定義と出だしの計算
http://science.2ch.net/test/read.cgi/math/1024311743/708-724
↑この辺で695さんによる解りやすい解説
ここを何度も繰り返して読めばあんたでも分かるだろ。プログラム「しか」読めんのなら話は別だが。
つーか、このスレの住人でプログラム分かる奴はほとんど居ない。
(いたらこのスレをあんたの好き勝手にはさせないんだが)
「誰にも分かる形で記録する必要がある」のはあんたのほうだと思うんだがな。
- 366 名前:旧695 :02/11/14 01:45
- こんな感じでしょうか。書式めちゃくちゃですが。
毎度ながらミスあるかも。
m[0]=3
f[0](x)=x+1
for n=1 to 63{
g[0](x)=f[n-1](x)
for i=1 to
f[n-1](m[n-1]){
g[i-1](x)=B(0,x)
B(a,0)=B(b-1,1)
B(a,b)=B(a-1,B(a,b-1))
g[i](x)=B(x,x)
f[n](x)=g[i](x)
}next i
m[n]=g[i](g[i-1](g[i-2](…(g[2](g[1](g[0](m[n-1])))…)))
}next n
ふぃっしゅ数Ver.1=m[n]
- 367 名前:264 :02/11/14 07:59
- >>365
DAT落ちしてる。
これでは「誰でも読める」とは言えないゾ。
- 368 名前:132人目の素数さん :02/11/14 18:55
- お望みならコピペするが
- 369 名前:名無しのような物体 ◆plq.mziK0E :02/11/14 20:47
- >>264さん
>Bird氏のMultiple・・・とかRevolving Allow等の拡張はみました
>あれはchainが分かってしまえば誰でも思いつくでしょう。
・・・そりゃそうですよね。失礼しました。でも、これでますます期待が膨らむというものです。
さて、ふぃっしゅっしゅさんのやり方については
前スレを見ていただくのが一番なのですが・・・残念、dat落ちしてましたか。
しかしこちらでも保存してありますので、よろしければいくつかコピペしてみましょう。
それと、私はプログラムに関しては素人同然ですので、
計算(というより近似ですね)のやり方をプログラムで説明というわけにも参りません。
まあ、ぼちぼち順を追って説明していきたいと思いますので、どうぞ気長にお待ちください。
- 370 名前:264 :02/11/14 23:18
- >>366
これって結局、次の関数を計算してるんじゃないのかな?
MultB(n,m) =
if n=0 then m
else
B(MultB(n-1,m),MultB(n-1,m))
MultB(1,n)=B(n,n)=n^[n]n (^[n]=^…^(n個))
MultB(2,n)=B(B(n,n),B(n,n))=(n^[n]n)^[n(n[n]n)](n^[n]n)
…
- 371 名前:264 :02/11/14 23:20
- ところで、ふぃっしゅ法の本質をみるために
Ackermann関数Bを使うのをやめて、
かわりに+でやってみよう。
Mult+(n,m) =
if n=0 then m
else +(Mult+(n-1,m),Mult+(n-1,m))
Mult+(1,n)=n+n=2n
Mult+(2,n)=(n+n)+(n,n)=4n
…
1次関数の係数は増えるけど2次関数を超えない。
もっとも、上で対角線をとると指数関数になる。
Mult+(n,n)=2^n*n
- 372 名前:264 :02/11/14 23:24
- で、もしかして、Ver.2って、MultBをつかって
MultMultB(n,m) =
if n=0 then
MultB(n,m)
else MultB(MultMultB(n-1,m),MultMultB(n-1,m))
をつくっていって・・・とやっていって、どんどん関数の増大度を
大きくしていくやり方なのかな?
これも本質をみるために、Bのかわりに+でやってみよう。
MultMult+(n,m) =
if n=0 then
Mult+(m,m)
else Mult+(MultMult+(n-1,m),MultMult+(n-1,m))
MultMult+(1,n) = 2^(2^n*n)+(2^n*n)
MultMult+(2,n) =
2^(2^(2^n*n)+(2^n*n))+2^(2^(2^n*n)+(2^n*n))
ここでも^が1づつ増える程度の増加。
この上MultMultMult…とかつづけても
できる関数は結局Ackermann関数以下。
なぜなら、これは全て原始帰納法の範囲だから。
- 373 名前:264 :02/11/14 23:46
- >>226
ところで
># 3項以上については、前スレで予想を書いたように2項の
>#
繰り返しで表現できてしまうような気がしていて、1項から
># 2項へ増えたような「革命的な」増加は期待できないのでは
>#
ないのかと思っています。検証は難しそうですが。
Conwayのchain notationは、任意の多重帰納法を含みます。
Ackermannはたかだか2重帰納法でしょう。
これを、3重、4重としたところで、それらで定義される
いかなる関数よりも大きいでしょう。
まさに「超革命的」増加ですね。
- 374 名前:264 :02/11/15 00:02
- >>369
>ますます期待が膨らむというものです。
期待されても困ります。
みなさんはConwayがどういう人かご存知ないかもしれませんけど
・・・天才ですよ。
彼の仕事では、ライフゲームとかモンスター群の解析が
有名かもしれませんが、僕は、超現実数(surreal number)
を挙げたいですね。これは実数の拡張なんですが・・・
まさにシュールリアルな代物です。
- 375 名前:132人目の素数さん :02/11/15 08:16
- >>374
超現実数はもちろん面白いんだけど、それを啓蒙的に紹介した「数学小説」の和訳があまりにも悪訳な気がする。
この和訳のせいで日本での超現実数やコンウェイの印象が悪くなってる気がするんだよなー。
- 376 名前:Fish ◆/T2GtW187g
:02/11/15 09:40
- Uwa, nandaka monosugoku koudo na houkou he hanashi ga
tenkai site
imasu ne. Hitotsu dake gokai wo toite okuto, watashi
wa suugaku no
senmonka dewa arimasen. Senmonka no
kata tachi ga matomo ni kentou wo
hajimeta you de, ureshiku
omoi masu.
Sorekara, Fish suu wa Version
2 ikou ni tsuite wa, kantan ni
program de hyouki dekinai to kangaete
imasu. Dakara koso,
donataka program wo kaite itadake naika? to okiki
shite iru
wake desuga...
Teigi wo wakari yasuku hyougen shiyou
nimo, jitsu wa s(n)
henkan wo sono mama rikai shite itadaku igai niwa
naito
omotte imasu.
- 377 名前:Fish ◆/T2GtW187g
:02/11/15 09:43
- >>342
ふぃっしゅ関数の「ヴァージョンアップ」には危険な飛躍が含まれている。
つまり一般化が「プログラミング可能」かどうかの議論が為されていない
ことにある。
Kono giron ni tsuite wa, watashi niwa doushiyoumo arimasen.
Robert san ga, program kanoude aruto itte imashita kara, tabun
dekiruno darouto wa omoi masuga, mushiro senmonka no kata
ga kite
itadaite imasu node, ketsuron wo dashite itadakereba
ureshiku omoimasu.
もし一般化がプログラミング可能な関数全体に及んでいる場合には、
それ自体はプログラミング可能ではなく、ビジービーバー関数と同じ
「計算可能関数の上限としての計算不能関数」に成り果ててしまう
恐れがある。
Busy Beaver kansuu wa
"keisan kanou kansuu no jougen" nanode
shouka? Watashi wa, BB kansuu wa
keisan kanou kansuu dewa
nakute, keisan fukanou kansuu datoiu rikai nano
desuga.
- 378 名前:Fish ◆/T2GtW187g
:02/11/15 09:51
- >>360
Darenidemo wakaru katachi de kiroku shitai towa omou
no desu ga, dou
sure ba dareni demo wakaru youni naru
noka ga wakaranai no desu. Program
ni kaku toka, gutai
teki ni keisan wo suru, toitta houhou dewa, watashi
jishin
ga dekimasenshi, dekita to shite mo "darenidemo wakaru"
to ieru
mononi naruka douka wa fumei desu.
Gyaku ni, tatoeba s(n) henkan no
teigi no dono atari ga
wakarinikui no ka ga wakare ba, setsumei mo
dekiruno
desuga...
- 379 名前:Fish ◆/T2GtW187g
:02/11/15 09:56
- >>352
Ackermanの関数が自然数の三つ組を引数とするものだとすると
Conwayのchain関数は自然数のリストを引数とするものである。
私が考えるに、上記の関数は自然数そのもの、および自然数の組
による乗法関数の延長線上にあるものと考えられる。
Masa ni
sono toori dato omoi masu.
Soshite, Fish suu wa, Kazu, kansuu, fukusuu
no shazou,
wo kumi to suru "shuugou" kara "shuugou" heno shazou
(kore
wo kansuu to yobe ba kansuu ni narimasu ga) wo
teigi shite iru tokoro ni
sono tokushu sei ga aru wake
desu. Kono gainen ga amari nimo tokushu
sugiru tame
ka, nakanaka rikai shite moraenai noga kanashii tokoro
desu...
- 380 名前:Fish ◆/T2GtW187g
:02/11/15 09:58
- Kako thread wa itsu goro html ka sareru no darouka??
- 381 名前:Fish ◆/T2GtW187g
:02/11/15 10:05
- >>366
>>370-372
Iyoiyo program de hyouki deki mashita ka?
Watashi jishin, korera
no program no ugoki wo rikai shite
Fish suu no teigi to tsukiawaseru
tameni wa, jikan ga
kakari soudesu. Shibaraku omachi kudasai...
- 382 名前:旧695 :02/11/15 13:51
- >>264氏
例えばアッカーマン関数においてB(3,3)=61 など>>370の
B(n,n)=n^[n]n には当てはまらないのですが、
別の関数なのでしょうか。
- 383 名前:132人目の素数さん :02/11/15 15:21
- >>382
どういう計算してるの?
- 384 名前:旧695 :02/11/15 16:23
- >>383
物体氏が>>87で
B(x,y)=(2→(y+3)→(x-2))-3
=(2^^…(x-2個)…^^(y+3))-3
と記しています。これによると
B(3,n)=2^(n+3)-3 よりn=3を代入して得られます。
B(3,3)=2^(3+3)-3=2^6-3=64-3=61
- 385 名前:旧695 :02/11/15 16:32
- っていうかn^[n]nの方が関数としてはでかいですね。
アッカーマンを近似すると2^[n]nぐらいですから。
- 386 名前:132人目の素数さん :02/11/15 17:27
- A=2
B=A*A*A*A*A*A*A......
これで、Bは超巨大数。
- 387 名前:264 :02/11/15 20:13
- >>382
確かに>>366のBの関数
B(0,x)=x+1
B(a,0)=B(b-1,1)
B(a,b)=B(a-1,B(a,b-1))
だとn^[n]nにならないな(w
もっとも、以下の関数
G(1,k,j)=j*k
G(n-1,1,j)=j
G(n+1,k+1,j)=G(n,G(n+1,k,j),j)
を用いて
B(n,m)=G(n,m,n)=n^[n]m
とすればそうなる。
Gも二重帰納法を用いているから、増え方としては同じで、計算も楽。
(どうで細かい端は影響しないのだから、簡単に計算できるほうがいい)
- 388 名前:旧695 :02/11/15 20:26
- なーるほどヽ(´ー`)ノすげえ
- 389 名前:264 :02/11/15 20:43
- >>376
>ふぃっしゅ数はヴァージョン2以降については、
>簡単にプログラムで表記できないと考えています。
>だからこそ、どなたかプログラムを書いていただけないか?
>とお聞きしているわけですが。
それは虫がよすぎるでしょう。
プログラムすることが語ることなんですから。
つまりふぃっしゅさんは何も中身について言及することなく、
誰か俺のいわんとすることを書いてくれ、といっているのに
等しいんですよ。
>定義をわかりやすく表現しようにも、実はs(n)変換を
>そのまま理解していただく以外にはないとおもっています。
「何も書いていない」ことをそのまま理解したら
「何も言っていない」という以外にはありませんよ。
- 390 名前:264 :02/11/15 20:52
- >>377
>ロバートさんが、プログラム可能であるといっていましたから、
>多分できるのだろうとは思いますが。
彼は、真剣に検討した上で返答したのではないと思いますよ。
いっておきますが、いかなる専門家も読心術師ではないので
あなたの心は読めません。
>ビジービーバー関数は「計算可能関数の上限」なのでしょうか?
ビジービーバー関数の定義はご存知ですね?
つまり状態数nのオートマトンで、一番沢山の1を印字するものです。
それぞれのオートマトンはもちろん計算可能であり、その中で、
「一番沢山の1を印字する」というのが、一種の「上限」と
考えられるわけです。
ちなみに上限そのものは、もちろん計算可能ではありませんよ。
上限という言葉の意味を貴方が誤解していなければ、クレームを
つける理由は何ら存在しないでしょう。
- 391 名前:264 :02/11/15 21:03
- >>378
>プログラムに書くとか、具体的に計算をするといった方法では、
>私自身ができませんし
それではふぃっしゅさん、あなたはいったい何をしたのですか?
この場合、定義を書くとは実際に遂行可能なプログラムを書く
ということですよ。そして、それが正しいことは計算によって
のみ確かめることが出来ることですよ。
>できたとしても、「誰にでもわかる」といえるものになるかどうか
>不明です。
はっきりいえば、プログラムも読めず、計算もできない人は、
そもそもこの問題を考えることができないといわざるを得ません。
私はなにも微積分や三角関数や二次方程式の根の公式を
理解しろとは一言もいっていないのですよ。
ただ「言葉」を理解し、「記号の操作」を行うといった、
小学校一年生にもできることを要求しているにすぎないのですよ。
>逆に、例えば、S(n)変換の定義のどのあたりがわかりにくいのかが
>わかれば、説明できるのですが、
あなたは、かくかくしかじかの変換が、チェーンを超えるとか
バードを超えるとかいってますね。
それはいったいいかなる根拠によっていっているのですか?
あなたのいう定義と、あなたのいう成果の間にある筈の論理を
ここで示してください。
- 392 名前:264 :02/11/15 21:18
- >>379
>ふぃっしゅ数は数、関数、複数の写像、を組とする「集合」から
>「集合」への写像(これを関数とよべば関数になりますが)を
>定義しているところにその特殊性があるわけです。
>この概念があまりにも特殊すぎるためか、なかなか
>理解してもらえないのが、かなしいところです。
それだけなら、中身のまったくない夢想といわれても仕方ありませんよ。
求められているのは、上の写像をどう具体的に構成するかです。
それなしには何も語っていないに等しいのです。
ところで、旧695さんや名無しのような物体さんは、
ふぃっしゅ関数のヴァージョン2およびヴァージョン3について、
具体的な計算方法を理解していらっしゃるのでしょうか?
- 393 名前:旧695 :02/11/16 00:11
- PCで処理できるレベルまで寄って書くのは僕には難しいです。
よってこんな出来具合です。こういう場合プログラミング可能と
言えるのかどうかは知りません。
m[0]=3
f[0](x)=x+1
S[0]=B^1:
f(x)=B(0,x)
B(m,0)=B(m-1,1)
B(m,n)=B(m-1,B(m,n-1))
Bf(x)=B(x,x)
for n=1 to
63{
S[n]=S[n-1]^(f[n-1](m[n-1]))=B^k
f[n](x)=B^kx.f[n-1](x)
m[n]=B^k.f[n-1](B^(k-1).f[n-1](B^(k-2).f[n-1](…(B^2f[n-1](Bf[n-1](m[n-1])))…)))
}next n
ふぃっしゅ数Ver.2=m[63]
- 394 名前:Fish ◆/T2GtW187g
:02/11/16 00:31
- >>391
この場合、定義を書くとは実際に遂行可能なプログラムを書く
ということですよ。そして、それが正しいことは計算によって
のみ確かめることが出来ることですよ。
Soreawa chigau to omoimasu. BB(x) wo keisan
suru
program wo kaku koto wa dekimasenga, meikaku ni
teigi sarete
imasu. Souitta teigi mo teigi no uchidesu.
あなたは、かくかくしかじかの変換が、チェーンを超えるとか
バードを超えるとかいってますね。
それはいったいいかなる根拠によっていっているのですか?
あなたのいう定義と、あなたのいう成果の間にある筈の論理を
ここで示してください。
>>225-238
de setsumei shimashita.
Kono setsumei no naka de, wakarinikui tokoro ga
areba
sarani setsumei wo kokoromi masuga, sukunaku tomo
gutaiteki na
keisan nashi ni demo, kansuu ya kazu no
ookisa wo hikaku suru kotoga
dekimasu.
Genjitsu teki ni keisan fukanou na kazu wo kuraberu
toki
niwa, konoyouni shite kuraberu igai niwa houhou wa
arimasen.
Dewa
donoyouni shite, gutaiteki na keisan nashini
ookisa wo kuraberu noka?
Soreniwa, "Kazu to kazu no
ookisa wo kuraberu" "Kansuu to kansuu no ookisa
wo
kuraberu" toitta koto wo seikaku ni rikai suru hituyou ga
arimasu
node, soreni tsuite wa mata gojitsu aratamete.
- 395 名前:旧695 :02/11/16 01:10
- 僕のインチキプログラムは基本的にBASICなので、プログラミングを知らない
方は下記のサイトが分かりやすいです。変数の扱い方、演算、繰り返し、
条件分岐あたりを理解すれば十分だと思います。とりあえずは。
http://www3.plala.or.jp/bountyhunter/lesson01.html
- 396 名前:Fish
◆/T2GtW187g :02/11/16 01:23
- >>394
Ie, chain kansuu tono hikaku no gutaiteki na tokoro wa
mushiro, >>211-214
desune.
BASIC wa wakarimasu. Matomo ni yomeru nowa, BASIC
nomi, to
iu houga iikamo siremasen.
Tsukutte itadaita program no kaidoku wa,
shuumatsu
no shukudai to sasete kudasai.
- 397 名前:132人目の素数さん :02/11/16 07:20
- 初めて書き込みますが、面白そうな話題ですね。
ふぃっしゅ関数の定義とかちゃんと読んでいないのですが、
時間を見つけて挑戦したいです。
>>393
プログラム中に '…' が入っていたら、それはプログラムを
記述したことにはなりません。省略された部分をループや条件分岐を
用いて書くことにより、初めてプログラム(というかアルゴリズム)が
記述できたことになります。
これは計算可能性を論じるとき、もっとも本質的な部分になります。
それともう一つ、これはご存知かもしれませんがプログラム言語の
世界では'='の意味が数学の世界とは全く違います。
BASICを例に取りますと、'A = B' は、
1. A = B
2.
if A = B then 〜
の2種類の使われ方があります。
1. は「A に式の結果を代入する」という意味です。つまり右辺から
左辺への代入を表します。2. は「A = B」という述語の真偽値を返す
式です。つまり左辺と右辺の比較を表します。
他の言語では定義が微妙に異なる場合がありますが、本質的にはこの
2種類のいずれかしかありません。この定義からすると、
>S[n]=S[n-1]^(f[n-1](m[n-1]))=B^k
という一行は何をやっているのかわかりません。
- 398 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 09:40
- >>371
ところで、ふぃっしゅ法の本質をみるために
Ackermann関数Bを使うのをやめて、
かわりに+でやってみよう。
これは、秀逸なアイディアですね。なぜ、今まで気づかなかったんだろう。
それでは、S変換を g(x)=f(x)+1
に格下げすることで、ふぃっしゅ数の
定義を順に検討していこうと思います。これで、かなりわかりやすくなる
はずです。
- 399 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 09:43
- Version 3 の検討に入ります。まずs(1)の定義から。
英語表記は >>188
日本語表記は >>203
です。
s(1)の定義がこのままだと計算不可能になるので、これを以下のように
変えてみます。
(1) s(1)写像の定義
S(1)写像は、自然数と関数のペアから自然数と関数のペアへの写像です。
S(1)写像のひとつであるs(1)写像は次のように定義されます。
s(1):[m,f(x)] -->
[g(m),g(x)] ただし
g(x)=f(x)+1
- 400 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 09:52
- このようにすると、[3,x+1] にs(1)写像を繰り返し適用することで、
[3,x+1] -> [5,x+2] ->
[8,x+3] -> [12,x+4]
といったペアが得られるので、s(1)変換をn回繰り返すことで、
[(n+1)(n+2)/2+2, x+n-1]
が得られます。
- 401 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:01
- 失礼、>>400の最後は
x+n-1ではなくて、x+n+1です。
さて、ここで問題の s(2) 変換に入ります。
英語は >>189
日本語は >>203
です。
s(2):[m,f(x),s(1)] --> [n,g(x),s'(1)] ただし
s'(1)=s(1)^f(m)
s'(1):[m,f(x)] --> [n,p(x)]
s'(1)^y:[m,f(x)] --> [q(y),r(x,y)]
g(x)=r(x,x)
[3,x+1] に
s(2) 変換を1回施してみます。このとき、
生成される数は s'(1) 変換、すなわち s(1) 変換を
4回繰り返す変換を施して得られる数なので、>>400の
式にn=4を代入した22となります。
関数については、s'(1) 変換を n 回繰り返すことで
x+4n+1が得られるため、x回繰り返すことで、n=x を
代入した 5x+1 が得られます。
したがって、
s(2):[3,x+1,s(1)]->[22,5x+1,s(1)^4]
ということになります。
- 402 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:10
- 続いて、[22,5x+1,s(1)^4]に s(2) 変換を施してみます。
このとき、生成される数は s(1) 変換を 111*4=444
回施して
得られる数なので、>>400
に n=444 を代入した 999235 に
なります。
関数については、s'(1) 変換そのものが初期の s(1) 変換を
444回施す変換になっていますので、s'(1) 変換を n回
繰り返すことで x+444n+1 が得られ、x回繰り返すことで、
445x+1 が得られます。
したがって、s(2)変換2回にして [999235, 445x+1, s(1)^444]
が得られます。
- 403 名前:132人目の素数さん :02/11/16 10:15
- >>393
>S[n]=S[n-1]^(f[n-1](m[n-1]))=B^k
突然、B^kのkが出てきましたよ。
計算機がこのプログラムを実行しようとしたら
kが定義されていないのでエラーとでますよ
変数名には十分注意してください。
これ一つで意味が不明になります。
- 404 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:20
- 続いて、s(2)変換の3回目です。今度は、445x+1にx=999235を
代入した444659576回、s(1)^444を施した変換が新s'(1)変換
ですから、すなわち新s'(1)変換は、s(1)変換を
444659576*444=197428851744回施した変換になります。
生成される数は、>>400にこの値を代入した1.95e+22になります。
関数は、444659577x+1が得られます。
s(2)変換3回にして [1.95e+22, 444659577x+1,
s(1)^197428851744]
が得られました。
- 405 名前:旧695 :02/11/16 10:21
- B^kは表記の簡単のため確信犯的に使いました。
どちらにせよプログラムとしては不完全なので、この際。
- 406 名前:264 :02/11/16 10:21
- ふぃっしゅさん、ゲームのルールは計算可能性です
今後、一切これを逸脱することは許しません。
>BB(x)
を計算するプログラムをかくことはできませんが
>明確に定義されています。そういった定義も定義のうちです。
いいえ、プログラムを書くことができないならば、計算可能な関数としては
全く定義されていません。つまり定義とはみなされません。
今後、このルールに従ってください。いいですね。
- 407 名前:264 :02/11/16 10:23
- >>405
簡略化はこの場合認められません。
省略は一切禁止します。kがいかに計算されるか
完全に書いてください。不完全は無意味と理解してください。
- 408 名前:132人目の素数さん
:02/11/16 10:24
- >ふぃっしゅさん、ゲームのルールは計算可能性です
そうなの?
- 409 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:28
- こうしてみると、s(2)変換をn回繰り返すことで得られる関数は、
f(n)x+1の関係式であらわされ、
f(0)=1,
f(1)=5, f(2)=444, f(3)=444659577
といった値が求まりました。この係数がいかにして増えるかを
追うためには、数が増える様子を追う必要があるので、一般式を
出すのはちょっと複雑になりそうです。そして、一般式を出さないと、
s(3)変換へ進むことができません。
ゆっくりと考えていきたいと思います。
- 410 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:32
- >>406
私は、はなから計算可能な関数に限定する意志はありません。
したがって、そのルールにしたがう意志はありません。
その上で、ふぃっしゅ数が計算可能な関数であるかどうかを
検討することは、とても意義深いことだと思います。
この流れでいくと、きっと計算可能な関数だという結論に
なりそうですが、それはそれでそういった結論が得られたという
意味で満足です。
計算不可能という結論が得られたとしたら、望外の喜びです。
まず、そういった結論にはならないでしょうが。
- 411 名前:264 :02/11/16 10:33
- ふぃっしゅさんの>>394、>>396への返事
>>225-238(および>>211-214)は何の説明にもなっていません。
つまりあなたが正しいと思っていることは、あなただけが
何の根拠もなくそう信じているだけだということです。
つまり、具体的な計算なしには、関数や数の大きさを
比較することはできないのです。
「計算不可能」な数の場合にも、全く計算が為されない
わけではありません。必ず基礎となる数(これ自身は
計算不可能でもよい)が存在し、それを基準とした計算が
為されない限り、大きさを比較することはできないのです。
あなたはその議論を抜きにしています。
- 412 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:35
- >>225-238(および>>211-214)は何の説明にもなっていません。
よくよく読み返してください。具体的な質問であれば返答の
しようもありますが、何の説明にもなっていない、という
指摘に対しては、それはあなたの読解力が足りないだけだ、
とおこたえします。
- 413 名前:264 :02/11/16 10:37
- >>410
従わないのではないでしょう。
従おうにもどうしていいかわからないのではないですか?
あなたには計算可能かどうかすら分からないのだから。
しかし、それではあなたの主張の意義は無に等しい。
- 414 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:38
- 具体的な計算なしには、関数や数の大きさを
比較することはできないのです
これは明らかな間違いです。
極端な例を出しましょう。
BB(BB(100)) > BB(BB(10))
は明らかです。具体的な計算ができないにも関わらず、です。
具体的な計算無しに数の大きさを比較した例です。
十分な推論によって、比較できる場合があるのです。
- 415 名前:264 :02/11/16 10:40
- >>412
「具体的」な質問をするには、あなたの説明は
あまりにも何もなさすぎます。何もないものを
読解する力は誰にもありません。
そんな力はあってはいけないのです。
- 416 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:40
- >>413
計算可能かどうかを検討することが目的ではなく、
大きな数を生成することを目的としているのですから、
意味があります。
計算可能性を検討することの異議を否定しているものでは
ないのですが、その点はわかっていただけますよね。
- 417 名前:132人目の素数さん
:02/11/16 10:43
- >>264
>>414
- 418 名前:264 :02/11/16 10:43
- >>414
>BB(BB(100)) > BB(BB(10))
>は明らかです。
>具体的な計算ができないにも関わらず、です。
いや、具体的な計算はなされていますよ。
100は10より大きいというところです(w
状態数が100以内のオートマトンの中には
当然状態数が10以内のオートマトンが
含まれます。したがって
BB(100)>BB(10)
です。そしてその結果から、
BB(BB(100))>BB(BB(10))
が示されます。
ほら計算しているじゃないですか。
- 419 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:45
- ふむ、では>>414を示しましょう。
BB(x)は単調増加関数である。これは間違いありませんね。
100>10
-> BB(100)>BB(10) -> BB(BB(100))>BB(BB(10))
この推論を「計算不可能だから」という理由で否定すると
したら、もはや数学的な議論ができるとは思えません。
- 420 名前:132人目の素数さん
:02/11/16 10:46
- >>418
それは計算も混じっているが
大部分は推論だと思う。
そして>>211-214はそれと同じような推論によって成り立っているのじゃないかな。
もうちょっとしっかり読めば分かるさ。
- 421 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:47
- >>418
そうではなくて、BB(BB(100))もBB(BB(10))も計算不可能なのに、
両者が比較できるのは、そのような推論によって可能になっている、
ということをいいたいのです。
私が書いたことも、ある種の推論を用いていますので、具体的な
計算をしていないから無意味だ、という主張は成り立たないのです。
- 422 名前:264 :02/11/16 10:48
- >>416
いや、計算可能な関数を生成することが目的です。
よしんば「計算不可能」を認めるとしても、それなら
ビジービーバーのようにオートマトンの状態数を制限するとか
あるいは計算機言語を一つに定めた上で、その言語で**字
以内でプログラムできないとかいう字数制限を設けるとかしないと
なんら意味のある議論にはなりません。
あなたの議論の態度自体に異議を申し立てているのです。
あなたにとってもっとも耐えがたいでしょうが、
私はあなたの個人の面目よりも数学としての意義を優先します。
- 423 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:51
- >>422
つまりあなたが考える「意味のある議論」にはならないという
ことですよね。
そうなってくると、どういった議論を意味のある議論と考えるか、
といった非常に主観的な問題を議論することになりますので、
これ以上は深入りできません。
明らかになったことは、あなたが意味のあると考えていることと、
私が意味のあると考えていることに、違いがあるということです。
- 424 名前:オモー ◆gTZxZ3JNKk
:02/11/16 10:51
- もともとはこんなすれじゃなかった
みんなたのしく
おおきなおおきなかずをもとめて
みんなむじゃきにあそんでいた
それがいまでは・・・
うぅぅ・・・
- 425 名前:264 :02/11/16 10:52
- >>421
>そうではなくて
あなたが推論とよぶものこそが、ここでいう計算なのです。
その意味で、あなたはあなたの主張することに対して
まともな推論すらしていないということです。
- 426 名前:ふぃっしゅっしゅ ◆/T2GtW187g
:02/11/16 10:55
- >>425
あなたが推論とよぶものこそが、ここでいう計算なのです。
あなたのおっしゃることがわからなくなってきました。
なんだかオーバーヒートしてきたので、頭を冷やして後日
出直します。
- 427 名前:264 :02/11/16 10:55
- 推論もまた、規則によりその正しさを「計算」することが
可能でなければなんらの意味も持ちません。
これは誰もが認めることであり、それを認めなくなった人は
「トンデモ」として御三家入りせざるをえなくなるでしょう。
つまり、P=NPの山口人生や、今井数学の今井弘一や、論理改革の
M_SHIRAISHIと同じ仲間になるということです。
- 428 名前:オモー ◆gTZxZ3JNKk
:02/11/16 10:58
- ところで、
>せいぜいSS変換を3回も繰り返せば、バード数を超えることは確実です。
これとふぃっしゅ数の定義を見比べて思ったんだが、
これは264の言う「計算」を暗黙のうちに使っているんじゃないか?(63>3)
間違ってたらゴメソ
- 429 名前:264 :02/11/16 11:00
- >>427の続き、
どのような議論もそれを検証するのに「計算」によらざるを得ない
という事実は、計算不可能なものを、「天下りの原理」として
持ち込むことの不毛性を示しています。
つまりビジービーバーの存在を前提して、その上にちまちま
原始帰納的な拡張を行っても無意味だってことです。
ここでなすべきことは、計算可能性という制約をあくまで維持した上で
どこまで関数の増大度をあげることができるかということです。
- 430 名前:264 :02/11/16 11:03
- ふぃっしゅさんは、ここで無駄な言い訳をすることは一切やめて
>>398-409の計算に専念することが必要だと思います。
- 431 名前:397 :02/11/16 11:09
- 計算可能の定義について少し考えてみましょうよ。
計算不可能な関数とは、平たく言うと、次のようなものですよね。
f(∽)=0, f(x)=f(x+1)
これは単調減少関数ですが計算できません。
直観的にはf(0)は十分小さい数であるよう予想されますが、
しかしどうあがいてもf(0)は具体的な数にはなりえません。
264氏はBB(x)がこの種の関数だと主張しているのでしょうか。
もし、そういう意味で計算可能でない関数を定義してしまったので
あれば、その関数の値域は数直線上にはない事になります。
一方、答えがわかっているにもかかわらず、計算不可能な関数が
存在することは証明されています(この表現は少しあいまいです)。
説明は長くなるので略しますが、Ver.2 あるいは Ver.3がその手の
関数(例えば recursively enumerable 集合に属するもの)であれば、
計算可能でも、値が出る可能性があります。
- 432 名前:397 :02/11/16 11:16
- 最後の行間違えました。
>計算可能でも
計算不可能でも
で、ふぃっしゅ関数が至るところ計算不可能であれば、264氏の言う
通りでそれはもはや意味を持つ関数とは言えないと思います。
少なくともビジービーバー関数と比較する意味はありません。
なぜなら、全く新しい関数の概念だからです。
しかし、ある条件を与えてやるとxに対してyが計算可能になると
すれば、ふぃっしゅ関数は意味を持つものになるかもしれません。
恐らく、その場合はふぃっしゅ関数は rcursive enumerable だと
思うのですが・・・
- 433 名前:オモー ◆gTZxZ3JNKk
:02/11/16 11:16
- ほう、そういう意味だったんですか。>>264
少し納得したような気がします。
ところで、ビジービーバーについてまだ良く分かっていないので、説明していただけます?
- 434 名前:264 :02/11/16 11:17
- >>431
>計算不可能な関数とは、平たく言うと、次のようなものですよね。
>f(∽)=0, f(x)=f(x+1)
違う。そういう意味ではない。
- 435 名前:397 :02/11/16 11:18
- 度々すみません。
>>430ですが
f(∽)=0, f(x)=f(x+1)-1
のまちがいです。
- 436 名前:264 :02/11/16 11:20
- >>431
>一方、答えがわかっているにもかかわらず、計算不可能な関数が
>存在することは証明されています(この表現は少しあいまいです)。
>説明は長くなるので略しますが、Ver.2 あるいは Ver.3がその手の
>関数(例えば recursively enumerable
集合に属するもの)であれば、
>計算不可能でも、値が出る可能性があります。
ちょっと聞きたいのだが、君のいう計算可能の定義は?
- 437 名前:397 :02/11/16 11:22
- >>434
じゃあどういうい意味なのでしょうか。
計算可能 <-> 決定性チューリングマシンで受理可能 <-> 帰納的
ではないのですか?
もしそうでないのでしたら、264氏の主張する計算可能の定義を
教えてください。
- 438 名前:264 :02/11/16 11:22
- >>435
それでも同じ。尻抜けだからね。
そういう尻抜けという意味で、計算不可能といってるわけではない。
- 439 名前:264 :02/11/16 11:25
- >>437
>計算可能 <-> 決定性チューリングマシンで受理可能 <-> 帰納的
>ではないのですか。
ちょっとあいまいだな。
例えば最後の帰納的とはgenerally recursiveという意味で
言ってるのかい?>>436でrecursively
enumerable 集合に
属するようなものは計算可能でないといっている点から
すると、そう取れるのだが(いっておくが、それは、
計算可能性を狭く解釈していると思う)
- 440 名前:397 :02/11/16 11:26
- >>438
なるほど。その点は理解しました。
これから出かけなきゃいけないので、あとは明日以降にならないと
レスできません・・・
- 441 名前: