S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Mon, 20 May 2013 08:39:17 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 6 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Which function grows quicker?Posted: Sat, 31 Oct 2009 04:09:44 UTC
 S.O.S. Oldtimer

Joined: Fri, 30 Oct 2009 16:33:10 UTC
Posts: 261
I came up with this on my own. I am not sure, maybe someone else has done it too. I do not know the answer. Came up with these while trying to think of functions that grow more quickly than busy beaver functions.

Which, "over the long run," grows more quickly?

1) Not sure how to write this as a function, but you will probably get the idea:

X1= (1!)
X2= (2!)^(2!)
X3= [(3!)^(3!)]^(3!)
X4= {[(4!)^(4!)]^(4!)}^(4!)= 1.097E19080

2) The first term is 3. Xn = (X(n-1))!. So:

X1= 3
X2= 3!=6
X3= 6!=720
X4= 720!=2.60E1746
X5= (X4)!

Also, does anyone know if either or both of these will, in the long run, grow faster than busy beaver functions? If you start working these out, it quickly becomes obvious that they grow at a tremendously fast rate. Also, has anyone seen either of these before, and if so, is there some practical use for them? Thanks and good luck!

Last edited by goteamusa on Sat, 31 Oct 2009 20:01:40 UTC, edited 4 times in total.

Top

 Post subject: Posted: Sat, 31 Oct 2009 04:22:37 UTC
 S.O.S. Oldtimer

Joined: Fri, 30 Oct 2009 16:33:10 UTC
Posts: 261
Of course, if you wanted something that certainly must grow faster than busy beaver functions, just combine the two ideas:

X1= (2!)^(2!)=4
X2= {[(4!)^(4!)]^(4!)}^(4!)= 1.097E19080
X3= [(X2!)^(X2!)]^(X2!)... and so forth with a tower consisting of X2! levels.
X4= [(X3!)^(X3!)]^(X3!)... and so forth with a tower consisting of X3! levels.
Can anyone calculate the value of the 3rd term here? I would be very surprised if it is less than a googolplex (actually I think X3 probably makes a googolplex look tiny). Can anyone come up with a unique, faster growing "function" than this?

Top

 Post subject: Posted: Sat, 31 Oct 2009 04:54:11 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6005
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
goteamusa wrote:
Of course, if you wanted something that certainly must grow faster than busy beaver functions, just combine the two ideas:

X1= (2!)^(2!)=4
X2= {[(4!)^(4!)]^(4!)}^(4!)= 1.097E19080
X3= [(X2!)^(X2!)]^(X2!)... and so forth with a tower consisting of X2! levels.
X4= [(X3!)^(X3!)]^(X3!)... and so forth with a tower consisting of X3! levels.
Can anyone calculate the value of the 3rd term here? I would be very surprised if it is less than a googolplex (actually I think X3 probably makes a googolplex look tiny). Can anyone come up with a unique, faster growing "function" than this?

No! Your function must grow slower (eventually) than busy beavers because your function is computable (it is basically composing the factorial with the Knuth arrow).

_________________

Top

 Post subject: Posted: Sat, 31 Oct 2009 05:05:09 UTC
 S.O.S. Oldtimer

Joined: Fri, 30 Oct 2009 16:33:10 UTC
Posts: 261
It is true that busy beaver functions are noncomputable, but that does not mean that they have an infinite value do they? Does some f(x)=infinity for some beaver function? Doesn't noncomputable just mean that the exact value can not be mathematically determined? Therefore, is it not possible for computable functions, such as the ones I came up with, to grow faster than noncomputable functions, such as busy beaver functions?

Top

 Post subject: Posted: Sat, 31 Oct 2009 06:03:53 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6005
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
goteamusa wrote:
It is true that busy beaver functions are noncomputable, but that does not mean that they have an infinite value do they? Does some f(x)=infinity for some beaver function? Doesn't noncomputable just mean that the exact value can not be mathematically determined? Therefore, is it not possible for computable functions, such as the ones I came up with, to grow faster than noncomputable functions, such as busy beaver functions?

No! Infinity is not a number!

(or partial function ...) is computable means there is a finite state Turing machine (or equivalently a register machine which is usually easier to demonstrate) that will accept any natural number as input and compute f for that input (and in the case of partial functions, need machine halting for those input where f is defined and doesn't halt if f is not defined at the input).

Even if f is noncomputable, any truncation

is computable.

While you can cook up computable functions that beats the busy beavers function for the first N inputs, eventually the busy beavers function will win (see the construction in the other thread). That is why the answer to your initial question (does your function grow faster than the beavers function in the long run) is negative.

_________________

Top

 Post subject: Posted: Mon, 30 Nov 2009 12:31:58 UTC

Joined: Tue, 13 Oct 2009 12:13:31 UTC
Posts: 5
Hi,
You have to find the maximum and minimum values of the first derivative. These values are where the function is increasing or decreasing the fastest.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 6 posts ]

 All times are UTC [ DST ]

Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous