My number is bigger!

For all your silly time-killing forum games.

Moderators: jestingrabbit, Moderators General, Prelates

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Thu Jun 30, 2016 12:26 am UTC

I only disagree with the version of the statement that applies to the unrestricted form of "Can be known".
I agree with the existance of a minimal n for which BB(n) = independent of ZFC.

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Thu Jun 30, 2016 2:02 am UTC

To be honest, I don't really see any relation - either way - between "being independent of ZFC" and "being unknowable".

ZFC is so complex and it's proof theoretic ordinal is so large, that the question of whether a specific TM's halting problem is decidable in ZFC has exactly zero practical value. While it is true that the BB(1919) example gives us an absolute upper bound for what BB values can be practically proven with ZFC, it is an incredibly bad upper bound.

Remember that:

(1) Most proofs (in fact, exactly 100% of them) are too long for humans to write down.
(2) Even if we limit ourselves to - say - proofs under a trillion symbols, there's no systematic way to find the correct one for a given TM in any reasonable amount of time.
(3) Even if we could fetch all these proofs magically, there are lots of turing machines to test. For n=50 there are about 10231 turing machines with 50 states. How do you plan to list them all, let alone find the correct behavior for each one?

To summarize the bad news: If you try to solve the BB problem by looking for proofs in ZFC, you'll hit a snag long before n=1919.

The flip side of this coin, is that ZFC may not be the right tool for this job. It is obvious that in order to attack the Busy Beaver problem for even n=6, we'll need radically new techniques. Who knows what we''ll be using to calculate BB(100) or BB(1000)? And since we don't know what these techniques will be, there's little point in trying to guess their limits.


To summarize the good news: If you can calculate BB(1000) then the "independent of ZFC" thing at n=1919 probably won't stop you from calculating BB(1919).
Image

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Thu Jun 30, 2016 2:18 am UTC

Just to add a specific example:

Consider the difficulty of calculating BB(6).

There are 232,218,265,089,212,416 six-state turing machines. That's 232 quadrillion machines, whose status must be resolved in order to obtain the value of BB(6).

What are the chances that among all these quadrillions of TM's, there isn't even one which is hopelessly difficult to analyze? Very slim, I think.
Image

User avatar
r.e.s.
Posts: 0
Joined: Mon Jun 14, 2010 2:49 pm UTC

Re: My number is bigger!

Postby r.e.s. » Thu Jun 30, 2016 5:30 am UTC

@PsiCubed -- To quote from Machlin & Stout, "The Complex Behavior of Simple Machines":
Brady predicted that there will never be a proof of the values of Σ(5) and S(5). We are just slightly more optimistic, and are lead (sic) to recast a parable due to Erdös (who spoke in the context of determining Ramsey numbers): suppose a vastly superior alien force lands and announces that they will destroy the planet unless we provide a value of the S function, along with a proof of its correctness. If they ask for S(5) we should put all of our mathematicians, computer scientists, and computers to the task, but if they ask for S(6) we should immediately attack because the task is hopeless.

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Thu Jun 30, 2016 1:17 pm UTC

I love that story, but I'm more optimistic than either of them (depending on how much time these aliens give us to come up with the solution).

The biggest obstacle to progress on the BB problem is lack of motivation. How many articles have been published in the last 10 years regarding Busy Beavers? I think that the only reason we don't have the value of BB(5) right now is that the amount of resources we've aimed at the problem was minimal.

As for BB(6): I agree that it is probably beyond the reach of our current methods. But I also think that the problem is objectively less difficult than people think it is: If we had the best human minds focusing on finding alternative ways to crack BB(6) and we had a reasonable deadline (say - 10 years), we would get an answer.

At least that's what I think.
Image

Desiato
Posts: 42
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: My number is bigger!

Postby Desiato » Thu Jun 30, 2016 7:57 pm UTC

PsiCubed wrote:To be honest, I don't really see any relation - either way - between "being independent of ZFC" and "being unknowable".

I should clarify that this is not about "being independant of ZFC".

The 1919 state Turing machine mentioned above does the following: It enumerates proofs in ZFC and halts if it finds a contradction.

If BB(1919) is known, you could (*) run that machine for BB(1919) steps. If it halts, ZFC has a contradiction that can be named. However, if it does not halt by then, then it never will and ZFC is free of contradictions. That would not be a proof in ZFC (and cannot be due to Gödel), it would be an absolute proof purely based on the knowledge of BB(1919), with presumably strictly finitary arguments.



(*) of course, that is not a practical proposition - but the fact that it would be possible in theory is amazing enough!

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Thu Jun 30, 2016 9:01 pm UTC

Thanks for the clarification. I guess I was a little confused on the details.

As you said yourself, this nice curio is of exactly zero practical value. You've already stated the obvious fact that we cannot actually run a TM for BB(1919) steps, but there is an even deeper problem here: BB(1919) is an integer so large, that we probably don't yet have the conceptual tools to say anything meaningful about it.

Note that I'm talking here about the integer itself, and not the Busy Beaver problem. If an alien civilization knows the value of BB(1919), they would have no way to communicate that value to us, because the integer itself is way beyond anything our current conceptual framework can handle.

As for the question you've asked me a few posts ago:

Do you find the argument that "A proof of consistency of ZFC based on elementary turing machine mechanics is impossible" is likely to be incorrect?


I think whether such a proof is possible or not, is irelevant. Here's why:

How do we go about finding the value of BB(n) for some n? We research the relevant Turing Machines, finding the running times of some and proving that others never halt.

So to find the value of BB(1919), we'll first need some method to clasify all 1919-state TM's. For those who don't halt, we'll need to prove that they don't halt. Among these machines, of-course, is the ZFC machine. And the only way to prove that the ZFC machine doesn't halt, is to prove that ZFC is consistent.

In other words, you can't fetch the value of BB(1919) without first proving that ZFC is consistent in some other way. Therefore, you cannot use the value of BB(1919) - even in theory - to prove the consistency of ZFC.
Image

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Thu Jun 30, 2016 11:23 pm UTC

Therefore, you cannot use the value of BB(1919) - even in theory - to prove the consistency of ZFC.


Not if you mean Σ(1919) but using S(1919) you can.
A ZFC checking machine halts if it finds an inconsistency in ZFC, so if this machine continues to run after S(1919) steps then it is assumed it will not halt (because not assuming so would mean that the machine halts later on, ergo S(1919) would be greater than itself) and therefore it would prove it is consistent, which is why a properly working ZFC checking TM machine is independent from ZFC. (a theory cant prove itself consistent)

Desiato
Posts: 42
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: My number is bigger!

Postby Desiato » Fri Jul 01, 2016 12:19 am UTC

PsiCubed wrote:So to find the value of BB(1919), we'll first need some method to clasify all 1919-state TM's. For those who don't halt, we'll need to prove that they don't halt. Among these machines, of-course, is the ZFC machine. And the only way to prove that the ZFC machine doesn't halt, is to prove that ZFC is consistent.

In other words, you can't fetch the value of BB(1919) without first proving that ZFC is consistent in some other way. Therefore, you cannot use the value of BB(1919) - even in theory - to prove the consistency of ZFC.

The key point is that currently, the only known way to prove any sort of sufficiently complex axiomatic system consistent typically refers to stronger assumptions than the system itself - stronger in a surprisingly well-defined manner. These assumptions always refer to infinities - tame ones such epsilon_0 for Peano, as an example, or huge ones like the formerly mentioned Mahlo cardinals (the assumption of ZFC + there exists a Mahlo cardinal proves ZFC+Con(ZFC)).

But by their very nature, Turing machines are about finitary processes, and presumably everything that can be proven about them only requires arguments of finitary nature.

Thus, this would be the first case where such finitary argumentations would prove the consistency of an infinitary theory.

Of course, once more, that is all very hypothetical and I completely agree that we will never know BB(1919). In fact, my original argument in the question about the biggest "knowable" BB comes from the very assumption that the above version of a consistency proof is considered impossible.

If you care about the historic dimension of the finitistic argument (which, of course, today is not a problem for mathematicians in a "I don't beleive in infinities"-way), see here for a start.

User avatar
r.e.s.
Posts: 0
Joined: Mon Jun 14, 2010 2:49 pm UTC

Re: My number is bigger!

Postby r.e.s. » Fri Jul 01, 2016 1:31 am UTC

PsiCubed wrote:So to find the value of BB(1919), we'll first need some method to clasify all 1919-state TM's. For those who don't halt, we'll need to prove that they don't halt. Among these machines, of-course, is the ZFC machine. And the only way to prove that the ZFC machine doesn't halt, is to prove that ZFC is consistent.

In other words, you can't fetch the value of BB(1919) without first proving that ZFC is consistent in some other way. Therefore, you cannot use the value of BB(1919) - even in theory - to prove the consistency of ZFC.
[color emphasis added by r.e.s.]

No, it isn't known that machine Z is among the never-halting machines, because it isn't known that ZFC is consistent. It might be the case (however unlikely it might seem) that ZFC is inconsistent, so that machine Z eventually halts. I.e., proving the value of BB(1919) might entail proving the inconsistency of ZFC.

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Sat Jul 02, 2016 3:54 pm UTC

Ive been thinking about PsiCubeds argument for a while now, i think his point is that a ZFC checking machine Z, which is included in the list of 1919 (or possibly less) state TMs would need to be proven not to halt using some method, analytical(?), before we declare the integer BB(1919) a known value, and thus the statement "BB(1919) is usable as proof of the consistency of ZFC" is invalid.

I see it the other way around. Referencing an integer with the notation BB(1919) implies that we have an answer to the question "is ZFC consistent?"

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Sat Jul 02, 2016 11:38 pm UTC

Daggoth wrote:Ive been thinking about PsiCubeds argument for a while now, i think his point is that a ZFC checking machine Z, which is included in the list of 1919 (or possibly less) state TMs would need to be proven not to halt using some method, analytical(?), before we declare the integer BB(1919) a known value, and thus the statement "BB(1919) is usable as proof of the consistency of ZFC" is invalid.


Exactly.

But I think I've finally understood Desiato's point.

What he is saying, is that if we make a couple of assumptions, then it can be proven that the value of S(1919) is theoretically unknowable. Whether these assumptions are actually correct or not, of-course, remains to be seen.




Desiato wrote:But by their very nature, Turing machines are about finitary processes, and presumably everything that can be proven about them only requires arguments of finitary nature.


Do you have proof of the second half of your statement?



Desiato wrote:Of course, once more, that is all very hypothetical and I completely agree that we will never know BB(1919). In fact, my original argument in the question about the biggest "knowable" BB comes from the very assumption that the above version of a consistency proof is considered impossible.


Again, why?

I don't see why it should be "impossible" to have a finitary proof that ZFC is consistent. Especially when the "finitary proof" in question requires no less than S(1919) steps.

Remember that the equivalent FGH level of S(1919) is - in all probablity - much much larger than the proof theoretic strength of ZFC. So why not?

If you're using your intuition here, be careful. Numbers as large as this do not follow the rules of human intuition regarding the finite and the infinite. When numbers get this big, the intuitive differences between "finite" and "infinite" begin to blur.
Image

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Sun Jul 03, 2016 3:30 am UTC

Desiato wrote:If you care about the historic dimension of the finitistic argument (which, of course, today is not a problem for mathematicians in a "I don't beleive in infinities"-way), see here for a start.


I've read the article, and it seems to actually imply that either your first assumption or your second one is wrong (depending on what you meant - exactly - by "finitary means").

The article gives Peano Arithmetic as an example. PA can be proven with transfinite induction up to epsilon-0. Do you regard such a proof as "a proof by finitary means" or not?

If you do, than there's no reason to assume that ZFC can't be proven to be consistent in a similar manner. Since the proof theoretical ordinal of ZFC is countable, there exists a bijection between that ordinal and the positive integers. This mapping will probably have to be completely insane, but it seems theoretically possible.

So in this case, your second assumption would be wrong.

On the other hand, if you don't accept the epsilon-0 proof as finitary, than it is quite easy to create a Turing Machine whose behavior can not be analyzed by finitary means: For example, any Turing Machine that enumerates the ordinals up to epsilon-0 in some pre-defined order.

So in this case, your first assumption would be wrong.

Either way, there seems to be no paradox at all in having a "finitary proof" for ZFC based on the value of S(1919). Even though we all agree that the theoretical existence of such a proof has absolutely no practical value.
Image

Desiato
Posts: 42
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: My number is bigger!

Postby Desiato » Sun Jul 03, 2016 7:20 pm UTC

PsiCubed wrote:
Desiato wrote:But by their very nature, Turing machines are about finitary processes, and presumably everything that can be proven about them only requires arguments of finitary nature.

Do you have proof of the second half of your statement?

No, of course not. It's my intuition, and there's arguments to be made (such as any turing machine just being a finite set of information), but a proof seems rather impossible, at least to me. However - do you have any reasons to expect the opposite?


PsiCubed wrote:
Desiato wrote:Of course, once more, that is all very hypothetical and I completely agree that we will never know BB(1919). In fact, my original argument in the question about the biggest "knowable" BB comes from the very assumption that the above version of a consistency proof is considered impossible.


Again, why?

Again, intuition. Note that I'm less certain on this part, which is why I haven't stated the conclusion that you had correctly understood as a definitive fact!

PsiCubed wrote:Remember that the equivalent FGH level of S(1919) is - in all probablity - much much larger than the proof theoretic strength of ZFC. So why not?

There's no FGH level for a specific number, just for functions. And of course, S itself, being uncomputable, has no corresponding ordinal at all.

PsiCubed wrote:If you're using your intuition here, be careful. Numbers as large as this do not follow the rules of human intuition regarding the finite and the infinite. When numbers get this big, the intuitive differences between "finite" and "infinite" begin to blur.

While I agree that the numbers discussed here are mindbogglingly huge, I disagree with the claim that they have any fundamental difference from 3, 15 or 23283789.

Desiato
Posts: 42
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: My number is bigger!

Postby Desiato » Sun Jul 03, 2016 7:57 pm UTC

PsiCubed wrote:The article gives Peano Arithmetic as an example. PA can be proven with transfinite induction up to epsilon-0. Do you regard such a proof as "a proof by finitary means" or not?

If you do, than there's no reason to assume that ZFC can't be proven to be consistent in a similar manner. Since the proof theoretical ordinal of ZFC is countable, there exists a bijection between that ordinal and the positive integers. This mapping will probably have to be completely insane, but it seems theoretically possible.

How would knowing such a bijection provide a proof of consistency for ZFC?


PsiCubed wrote:On the other hand, if you don't accept the epsilon-0 proof as finitary, than it is quite easy to create a Turing Machine whose behavior can not be analyzed by finitary means: For example, any Turing Machine that enumerates the ordinals up to epsilon-0 in some pre-defined order.

While I don't personally care about "finiteness" beyond the interesting questions that arise in contexts such as this, let's assume "finitary" to mean "not referencing infinite objects". So by that definition, assuming the existance of epsilon_0 or other infinite ordinals would not be finitary.

However, that doesn't invalidate my argument.

First of all, what do you mean by "Turing machine that enumerates ordinals up to epsilon_0"? Clearly, it cannot output a list of all of them.

Secondly and more importantly, just because the assumption "epsilon_0 exists" might prove such a machine to halt (or output whatever you mean), it does not mean the assumption is required for that proof. There might well be an alternative, much less complex proof.

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Mon Jul 04, 2016 4:15 pm UTC

For a random n, (nonzero natural) construct a TM that enumerates the goodstein sequence of n, and returns the length of the sequence.

all goodstein sequences terminate, so the machine will halt. but surely you can't prove this machine to halt only using finite tools. :mrgreen:

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Mon Jul 04, 2016 5:57 pm UTC

Desiato wrote:There's no FGH level for a specific number, just for functions. And of course, S itself, being uncomputable, has no corresponding ordinal at all.


One can speak of the FGH level of a number, which can be defined - roughly - as "the minimal FGH function needed to surpass the number with a small argument".

So the FGH level of Graham's number (for example) is w+1, because f_w+1(64) > G but f_w(n) < G for any reasonable n.

This definition is useful, because it tells us how complicated our recursion can get, if we are limited to N steps.

Desiato wrote:While I agree that the numbers discussed here are mindbogglingly huge, I disagree with the claim that they have any fundamental difference from 3, 15 or 23283789.


Depend on what you mean by "fundamental difference".

As far as pure mathematics is concerned, you are - of-course - correct. A finite number is a finite number.

But very big finite numbers do not obey our intuitive beliefs about finite numbers. You cannot use your intuition about ordinary numbers to say what can or cannot be done by following the output of a TM for S(1919) steps.

Desiato wrote:How would knowing such a bijection provide a proof of consistency for ZFC?


It doesn't provide a proof on its own. But it lays the background for such a proof being possible. Just like the bijection from epsilon-0 to the integers provides the basis of a finitary proof that PA is consistent (just take Gentzen's proof of consistency for PA, and replace all the ordinals with the appropriate integers, and you're done).

Desiato wrote:While I don't personally care about "finiteness" beyond the interesting questions that arise in contexts such as this, let's assume "finitary" to mean "not referencing infinite objects". So by that definition, assuming the existance of epsilon_0 or other infinite ordinals would not be finitary.


My point is that you don't need to "assume" that epsilon_0 exists. You can create a total order over the integers which is exactly equivalent to the structure of epsilon_0 (there's an example of this in these forums. Search for "pink numbers"). Or alternatively, you can use some other structure like nested arrays or trees or whatever.

And the same is true for any other constructable ordinal. Again, there are actual concrete examples of this in these forums: My own "purple numbers" (whose ordering is equivlaent to the Small Veblen Ordinal) and Emlightened's "blue numbers" (which are equivalent to the Bachmam Howard Ordinal).

In short: Anything you can do with constructable ordinals, you can do with integers. The only catch is that some of these integers will have to be very very big.

Now, let us think for a moment about what the ZFC TM would actually do when we run it for S(1919) steps:

It will output a list of proofs in ZFC. Lots and lots of proofs. Approximately S(1919) proofs, actually.

Remember that S(1919)>>fX+1(n) for any reasonable n (where X is the proof theoretic ordinal of ZFC). So is it really that surprising to you, that a list of S(1919) proofs is enough to settle the question of ZFC's consistency? It stands to reason that if 1=0 didn't appear in the first S(1919) proofs, it will never appear, because such a convoluted path would require an amount of recursion which is beyond the capabilites of the ZFC ordinal (and thus - beyond the capabilities of ZFC itself).

Indeed, we would expect that any provable statement which is subtantially shorter than S(1919) symbols, would be listed in the first S(1919) proofs.
Image

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Mon Jul 04, 2016 6:13 pm UTC

By the way, the same argument - exactly - can be done without referencing busy beavers.

The integer fZFC+1(googolplex) will probably suffice. And unlike S(1919), this integer is definitely computable.

So right there, we have the basis for a finitary proof of ZFC's consistency. Just run the ZFC TM for fZFC+1(googolplex) steps, and if it doesn't halt than ZFC is consistent. And it is a finitary proof, because fZFC+1(googolplex) is a well-defined integer which can (in theory) be calculated by a well-defined terminating algorithm.
Image

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Mon Jul 04, 2016 8:09 pm UTC

Daggoth wrote:For a random n, (nonzero natural) construct a TM that enumerates the goodstein sequence of n, and returns the length of the sequence.

all goodstein sequences terminate, so the machine will halt. but surely you can't prove this machine to halt only using finite tools. :mrgreen:


To be fair, for any specific n, there is a trivial proof of its halting status: Just wait until it halts.

And while you cannot prove that ALL such TM's halt without Goodstein's Theorem (or something equivalent), this doesn't refute Desiato's reasoning because this statement deals with an infinite family of machines (or alternatively: with a single TM that can accept an infinity of different inputs).

What we need here is a single TM that:

(1) Does an e0-level recursion while it is running.
(2) Never halts (because otherwise we could prove its halting status simply by waiting it out).
(3) Can be proven to run forever by infinitary means.

One way to do this, is to create a Peano-Arithmetic analogue of the ZFC machine mentioned earlier:

Suppose we had a TM that enumerates all proofs in PA, and halts if and only if it finds a proof for 0=1. Does this program halt?

This is a simple yes/no question regarding a single well-defined TM. It cannot be answered by what Deisato calls "finitary argumentations", yet it can easily be answered with transfinite induction to epsilon-0.

(Also, it might be interesting to look at the detailed working of this TM, and try to understand why - if it did halt - it would have to do so before the fe0+1(googolplex)-th step)
Image

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Fri Aug 05, 2016 2:48 pm UTC

I've just thought of something:

Yudowsky's number, as he described it, isn't really well-defined.

In order for such a number to be well defined, we must first define - exactly - how the statement "this TM halts" into a statement in ZF.

I suppose that doing this isn't too difficult. But withot this crucial step, Yudowsky's procedure doesn't result in a well-defined integer (indeed, there are many different ways to do this, and each one will result in "Yudowsky's number" being a different integer)
Image

User avatar
ygh
Posts: 4
Joined: Fri Jun 17, 2016 7:22 pm UTC

Re: My number is bigger!

Postby ygh » Wed Aug 10, 2016 6:23 pm UTC

Just wondering, where would Loader's number go in this?
I don't know what I'm doing most of the time.
Example: I often hit "quote" instead of "edit".

User avatar
Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: My number is bigger!

Postby Yakk » Wed Aug 10, 2016 7:38 pm UTC

It calculates D^5(99), where D(N) is the sum of the numbers expressed by the first k expressions in (some reasonably powerful language).

This won't be particularly larger than the largest one for any reasonably powerful language.

It is then iterated 5 times.

I try to use the small/medium/large system to categorize numbers. Small is anything that doesn't use a particularly strong system. Medium uses something as powerful as the fast growing heirarchy and feeds it a reasonable cardinal. Large are some of the computability ones, or proof based ones, or large cardinal fast growing heirarchy ones.

Illegal large numbers for this thread are busy-beaver like ones, where the sequence grows in a non-computably fast manner.

The link talks about it being larger than a number of medium sized numbers. It also states it is smaller than some illegally large number.

So it is somewhere between medium and large in this thread. I'd have to look into how powerful the language it diagonilizes over is. As it won the competition, I assume it is powerful, and maybe it is a large answer.

Then again, many of the large ones are really hard to express exactly. They have perquisits of things like "start with a complete automated proof system", then diagonlize over it. Maybe this won because the programmer found a not that powerful system to diagonilize over it *that could actually be written in brief*.

Or maybe the programmer actually found such a simple system that was also extremely powerful, which is how they beat the competition.

So, medium or large.

...

Wait a second. The system is CoC, the basis of CoQ? Ok, I'd guess the answer is large.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Thu Aug 11, 2016 9:40 am UTC

Yakk wrote:
So it is somewhere between medium and large in this thread. I'd have to look into how powerful the language it diagonilizes over is. As it won the competition, I assume it is powerful, and maybe it is a large answer.


That doesn't really mean anything, since second place is held by a relatively tame number: marxen.c, which came 2nd, is -
at the very most - a very low epsilon-1 level number. The actual ordinal used to decide the winner between marxen.c and loader.c is ε03, which - as far as proof theoretic ordinals go - is laughably small.

So the fact that loader.c won, doesn't really tell us how large it is. I could be relatively small (say f_ε1(3)) or it could be much larger. Without a more specific analysis of how CoC works exactly, it would be impossible to say more. Intuitively, though, it seems to be much larger than anything we could reasonably define recursively.

I'm pretty confident, though, that Yudowsky's ZFC process is much stronger. For one thing, you can't code all the rules of ZFC in anything close to 512 characters. For another thing, the halting problem in CoC is computable, which definitely puts a limit to how strong that system can be.
Image

User avatar
ygh
Posts: 4
Joined: Fri Jun 17, 2016 7:22 pm UTC

Re: My number is bigger!

Postby ygh » Thu Aug 11, 2016 2:24 pm UTC

What about Fish Number 7?
I don't know what I'm doing most of the time.
Example: I often hit "quote" instead of "edit".

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: My number is bigger!

Postby PsiCubed » Thu Aug 11, 2016 3:33 pm UTC

It's uncomputable (It's an extension of Rayo's function)
Image

User avatar
emlightened
Posts: 36
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Re: My number is bigger!

Postby emlightened » Sat Aug 13, 2016 9:35 pm UTC

It's undefined. (Rayo's function is too, and basic extensions like Big Foot.)

For the values of Rayo's number to be defined, you have to work in a specific model (a specific set of first order axioms, which could be a rectification to the system, is not sufficient). For a simple example, suppose that we work in ZFC, and ℶ1 = ℵn is independent of ZFC (proven, but we might be working in an extension) for each n, and the formula which is true for only n requires k symbols (k is likely only a few thousand).

Now, as this value is an upper bound for Rayo(k), suppose n, in the model we work in, is larger than that. Contradiction. Note that we've already proven that n is idependent, so either we assume that we can only go off provability in [theory], which is both weak (enumerate all proofs in the theory, assuming Rayo(n) is well defined) and dependent on the theory, or choose a model, which requires choosing a model based on a system where we have no axioms to go off of, which is completely arbitrary.

We can, of course, go one further by noting that the definition of a "natural number" may fail in a non-well founded theory and not fail in a well-founded one. Also, it is quite well known that all first-order theories that have an infinite model have infinitely many (at least one of each infinite cardinality), so even if we added restrictions so that we also have to make an axiomatic system, the idea (at the least, for first-order theories) is failed from the get-go.

Edited to add: Going back to the main point, for Rayo's function to be total, it needs to work in a system of absolute truths, as otherwise there exist sufficiently long formulas (length k and above) which may evaluate to any n (as the result is independent from the system), and this n may be larger than Rayo(k), making Rayo's function undefined for the values >=k. No such system of absolute truths can be formulated in first order logic excepting very basic ones: we either need a complete and consistent axiom system (which we can't have*, due to Gödel's incompleteness theorem), or a theory with a single model (which we can't have**, due to the Löwenheim–Skolem theorem).

If I had to suggest how to "fix" the function, I would say that R(n) is the largest number F(n), such that F can be proven total in a finitely-axiomisable (one-sorted) first-order theory which can be described with at most n symbols [in the way Rayo used]. This function grows faster than any function provably total in ZFC (using a finite axiomisation of the one-sorted variant of NBG), however this might not be the case for stronger theories or second-order theories.

*Unless the theory is very weak i.e. it does not incorporate Robinson Arithmetic.
**As the model must be infinite for our purposes, presumably. It may be possible to measure the size of very large finite models, however this does not seem to hold much promise, and better methods definitely exist.
Bleb. Idk when I'm returning.

User avatar
PTGFlyer
Posts: 12
Joined: Wed Jan 13, 2016 6:15 pm UTC

Re: My number is bigger!

Postby PTGFlyer » Wed Sep 28, 2016 11:00 pm UTC

Has anybody thrown out the xkcd number yet?

User avatar
emlightened
Posts: 36
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Re: My number is bigger!

Postby emlightened » Wed Sep 28, 2016 11:17 pm UTC

What, you mean that number that around g66? Probably on the first page, but I can't be bothered to check. Definitely by page 5.
Bleb. Idk when I'm returning.

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Fri Sep 30, 2016 3:22 am UTC

actually Page 3 surpasses XKCD by alot even if you only consider the first half

MrFroste
Posts: 0
Joined: Tue Feb 21, 2017 6:17 am UTC

Re: My number is bigger!

Postby MrFroste » Tue Feb 21, 2017 6:21 am UTC

Not sure if we've passed it already, but: Graham's number, to the power of Graham's number, to the power of Graham's number, to the power of Graham's number, etc... Graham's number times.

Kotlopou
Posts: 0
Joined: Wed Feb 22, 2017 8:20 pm UTC

Re: My number is bigger!

Postby Kotlopou » Wed Feb 22, 2017 8:29 pm UTC

The imath doesn't work, which makes some posts almost unreadable. How can I read it? I tried the program from gmalivuk's signature, but it doesn't do anything.

Ad previous poster, yes, that was passed by page two or three. Your number is less than g(65).

User avatar
PTGFlyer
Posts: 12
Joined: Wed Jan 13, 2016 6:15 pm UTC

Re: My number is bigger!

Postby PTGFlyer » Fri Feb 24, 2017 6:18 pm UTC

I made it all the way to page 3 before my brain exploded.

User avatar
Freddino18
Posts: 18
Joined: Thu Oct 27, 2016 9:40 pm UTC
Location: E4

Re: My number is bigger!

Postby Freddino18 » Mon Feb 27, 2017 9:04 pm UTC

Prepare yourself:

Spoiler:
BB(A(G,G))
Cautiously pessimistic.
Avatar buddies with Lavender
Tillian wrote:Holy necro!
morriswalters wrote:Low pressure on the balls
Jumble wrote:No, I have testicles, the traditional alternative.
i aint a robot
RAPTOR BLENDERS!

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Tue Feb 28, 2017 11:30 pm UTC

@Freddino18: violates the rules

User avatar
Freddino18
Posts: 18
Joined: Thu Oct 27, 2016 9:40 pm UTC
Location: E4

Re: My number is bigger!

Postby Freddino18 » Tue Feb 28, 2017 11:36 pm UTC

Explain please?
Cautiously pessimistic.
Avatar buddies with Lavender
Tillian wrote:Holy necro!
morriswalters wrote:Low pressure on the balls
Jumble wrote:No, I have testicles, the traditional alternative.
i aint a robot
RAPTOR BLENDERS!

Elmach
Posts: 155
Joined: Sun Mar 13, 2011 7:47 am UTC

Re: My number is bigger!

Postby Elmach » Tue Feb 28, 2017 11:43 pm UTC

The busy beaver function is uncomputable - there is no algorithm to compute it, and there cannot be an algorithm to compute it- as discussed above, BB(1919) is so large that if you have it, you can prove whether or not Peano Arithmetic ZFC is consistent, which is impossible*

*according to my understanding, which I am only 80% confident about.


Nevertheless, if this function were allowed, people would probably have put it inside their recursive functions, and do something larger than
BBBB(A(G,G))(A(G,G)) in one post.
Last edited by Elmach on Tue Feb 28, 2017 11:52 pm UTC, edited 1 time in total.

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Tue Feb 28, 2017 11:43 pm UTC

Almost as pointless as the Count to 1000 thread, this one doesn't require any particular increment between entries. The goal is to come up with a computable, finite, well-defined number that's bigger than the last poster's number


Did you read the rules in the op?

User avatar
Freddino18
Posts: 18
Joined: Thu Oct 27, 2016 9:40 pm UTC
Location: E4

Re: My number is bigger!

Postby Freddino18 » Wed Mar 01, 2017 12:34 am UTC

Fine. The FRED number (defined elsewhere in Forum Games).

Edit: JK, that's the same number :D A(A(A(G,G),A(G,G)),A(A(G,G),A(G,G))) (The new FRED number)
Cautiously pessimistic.
Avatar buddies with Lavender
Tillian wrote:Holy necro!
morriswalters wrote:Low pressure on the balls
Jumble wrote:No, I have testicles, the traditional alternative.
i aint a robot
RAPTOR BLENDERS!

Daggoth
Posts: 50
Joined: Wed Aug 05, 2009 2:37 am UTC

Re: My number is bigger!

Postby Daggoth » Mon Mar 06, 2017 10:29 pm UTC

Your number is beaten in page 1, bottom post

Fejfo
Posts: 0
Joined: Fri Mar 31, 2017 6:51 pm UTC

One upping the One upping of gmalivuk's number

Postby Fejfo » Fri Mar 31, 2017 7:11 pm UTC

Mouffles wrote:I'll go one up on gmalivuk's number.
Define a function f:
f(1)=1
f(2)=2→2
f(3)=3→3→3
etc.

Then the number is f(f(...f(g_64)...)), where the function is applied g_64 times. Beat that!


I know this is a really old post but with the subscript extension of chained arrow noation
a→(n+1)b = a→(n)a→(n)...→(n)a (b a's)
and →(1) = →

The function you defined is actually only:
f(x) = x→(2)x
so your number is defiantly bounded by
g_64→(2)g_64→(2)2
(remember increment an argument in chain arrow notation is iterating in the previous argument)

So with my functions:
f_1(1) = 1
f_1(x) = x →(f_1(x-1)) x

f_2(1) = 1
f_2(x) = f_1^(f_2(x-1)) (x)

f_n(1) = 1
f_n(x) = f_n-1^(f_n(x-1)) (x)


f_1(3) is already much bigger than your number

So my entry is:
f_[f_...f_1(3)...(3)(3)](3) (subscript f_999(3) levels deep)
goes way way beyond your solution

(I'm aware this can all easily be beaten with lamda's,ordinals or probably beaf but this is still a big number with using those)


Return to “Forum Games”

Who is online

Users browsing this forum: Earthling on Mars, Google [Bot], somitomi and 32 guests