flat assembler
Message board for the users of flat assembler.

 Index > Heap > What is the best pie you can get with 9 digits? Goto page Previous  1, 2, 3 ... 12, 13, 14 ... 27, 28, 29  Next
Author
r22

Joined: 27 Dec 2004
Posts: 805
r22
(BB^G)(G)
09 Mar 2008, 17:42
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
revolution
r22 wrote:
(BB^G)(G)
Accept, it will be either number 2 or number 3 on the finites list. I'm not sure how to compare it.
09 Mar 2008, 18:21
victor

Joined: 31 Dec 2005
Posts: 126
Location: Utopia
victor
Even though I am the leader in the "Finites" section, I am here challenging the validity of the S function.

Refer to this.
Quote:
...but there remain about 40 machines with nonregular behavior which are believed to never halt, but which have not yet been proven to run infinitely...

Since S(n) is defined to be the largest number of steps taken by any n-state 2-symbol Turing machine, S(n) may be infinity for some n!

As infinity is not acceptable, it seems that we need to reconsider the validity of the S function and all BB-related functions!

10 Mar 2008, 03:33
bitRAKE

Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
That is okay because the BB function is defined as:
Quote:
The n-state busy beaver (BB-n) game is a competition to find an n-state Turing machine which leaves the largest number of 1s on its tape before halting.
...excluding non-halting machines. Obviously, a non-halting machine could easily produce infinite 1s.

_________________
10 Mar 2008, 04:03
victor

Joined: 31 Dec 2005
Posts: 126
Location: Utopia
victor
Ok, I found this:
Quote:
Lin, Shen and Radó, Tibor (1965), ''Computer Studies of Turing Machine Problems'', Journal of the Association for Computing Machinery, Vol. 12, No. 2 (April 1965), pp. 196-212. Lin was a doctoral student under Radó. This paper appeared in part of Lin's thesis. Lin proves that Σ(3) = 6 and S(3) = 21 by proving that all 3-state 2-symbol Turing Machines which don't halt after 21 steps will never halt (Most are proven automatically by a computer program, however 40 are proven by human inspection).

The definition seems to exclude all TMs that don't halt.

Fine, I'm still the leader in the "Finites" section!
10 Mar 2008, 04:35
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
revolution
Yes indeed, creating a non-halting machine is of course exceedingly easy and would be rather pointless trying to count the transitions.

No need to panic victor, I think your current position is quite safe. But I'm not guaranteeing it, 'cause ya just never know if/when someone will find a larger value that can be squeezed into 9 characters.
10 Mar 2008, 06:57
bitRAKE

Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Community Beaver, CB(n) is equal to the sum of all one bits generated by all halting n-state Turing machines. C(n) is the steps taken by all n-state Turing machines to reach CB(n).

_________________
10 Mar 2008, 15:54
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
revolution
bitRAKE wrote:
Community Beaver, CB(n) is equal to the sum of all one bits generated by all halting n-state Turing machines. C(n) is the steps taken by all n-state Turing machines to reach CB(n).
I will accept if you can provide an external citation to back it up.

Sounds interesting, what are the first three values?
10 Mar 2008, 16:00
r22

Joined: 27 Dec 2004
Posts: 805
r22
(CB^G)(G)
Will assume bitRAKE isn't making it up, but you know what they say about assuming
10 Mar 2008, 17:25
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
revolution
r22 wrote:
(CB^G)(G)
I think bitRAKE would be implying (C^G\$)(G)
r22 wrote:
Will assume bitRAKE isn't making it up, but you know what they say about assuming
Somehow I think you ass-u-me too much in this instance
10 Mar 2008, 17:33
bitRAKE

Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Guess it sounded better than I thought. Ya'd want to go right for (C^G\$)(G) if it wasn't made up.

_________________
10 Mar 2008, 17:34
r22

Joined: 27 Dec 2004
Posts: 805
r22
You can never be too sure with obscure math functions.

I don't think we spent enough time with Graham's number though

Quote:

Graham's Number

This number is an upper bound for a problem in Ramsey theory, (graph coloring, combinatorics). The problem is to determine the lowest dimension of a hypercube such that if the lines joining all pairs of corners are two-colored, a planar graph K4 of one color will be forced. (K4 is a totally-connected graph with 4 edges, topologically equivalent to the 4 vertices and 6 edges of a tetrahedron). Graham and Rothschild proved that an answer exists and the best upper bound they could find is Graham's Number. Graham's Number is gn(64), where gn() is defined as follows:

gn(n) = { hy(3,6,3) for n = 1 { { hy(3, gn(n-1)+2, 3) for n > 1

Todd Cesere and Tim Chow have both proven that Graham's Number is bigger than the Moser, and in fact even gn(2) is much bigger than the Moser. Tim's proof is outlined on a page by Susan Stepney, here.

Using gn() we can make a number much larger than Graham's number which is gn(64)

So the largest number possible in 9 ASCII characters is...

gn(gn(G))
10 Mar 2008, 20:09
r22

Joined: 27 Dec 2004
Posts: 805
r22
BB(gn(G))

(gn^G)(G)

S(gn(G\$))

For completeness
10 Mar 2008, 20:16
bitRAKE

Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
revolution wrote:
Sounds interesting, what are the first three values?
Using BB() and S() the answer can be brute forced up to CB(4) and C(4). Still trying to think of a use for the sequence - beyond the big question.

r22, unfortunately, all those values are smaller. The composite application of S() is just staggering. If a more compact notation can be found for composite then you'd have a winner - five characters are currently devoted to it: (^)()

_________________
10 Mar 2008, 21:07
r22

Joined: 27 Dec 2004
Posts: 805
r22
(gn^G)(G)

Is it greater than (S^G)(G\$), I don't know. Is S(64) > G and as n -> INF does this hold true?

Quote:
five characters are currently devoted to it: (^)()

F^X_(Y)
^_() 4 characters? Using _ to negate the superscript to regular script.

S^G\$_(G\$)

gn^G_(G\$)

Last edited by r22 on 11 Mar 2008, 01:08; edited 1 time in total
10 Mar 2008, 21:58
bitRAKE

Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
r22 wrote:
Is S(64) > G and as n -> INF does this hold true?
Oh, yeah. Even BB() would be larger. It would be interesting to determine the smallest Turing machine to compute gn().

_________________
11 Mar 2008, 00:23
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
revolution
The BB function is that fastest growing function known to date. Even the graham's number function, while it looks like a candidate for huge numbers, will grow slower.

But, BB(X) > gn(X) where X = unknown_value.

We don't know where the point is that BB will overtake gn. Maybe at X~10 or so will do it, but how to compute it?
11 Mar 2008, 01:35
r22

Joined: 27 Dec 2004
Posts: 805
r22
***EDIT*** will take the combined words of Rev & bitRake that BB() grows faster

re bitRAKE
I have a hard time beleiving that S() > gn()

S(1)=1; S(2)=6; S(3)=21; S(4)=107; S(5)=134,467
BB(1)=1; BB(2)=4; BB(3)=6; BB(4)=13

gn(1) >= 27; gn(2) >= 7,625,597,484,987; gn(3) >= 3^(7,625,597,484,987); hy(3, gn(n-1)+2, 3)
11 Mar 2008, 02:23
r22

Joined: 27 Dec 2004
Posts: 805
r22
http://en.wikipedia.org/wiki/Conway_chained_arrow_notation

G->G\$\$->G - G UpArrow^G\$\$ G

3→3→64→2 < Graham's number < 3→3→65→2
Not enough characters to get a 4 arrow chain in, I don't have a clue on how to check if 3 arrows using Graham's and superfactorials is enough.

re: revolution

Whats the ruling on my alternate composite function notation?
(F^x)(y) == F^x_(y) == F^x (y)
5 chars 4 chars
I think a subscript (_) or evena space ( ) is valid for negating the superscript (^) notation.
11 Mar 2008, 02:53
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
revolution
r22 wrote:
http://en.wikipedia.org/wiki/Conway_chained_arrow_notation

G->G\$\$->G - G UpArrow^G\$\$ G

3→3→64→2 < Graham's number < 3→3→65→2
Not enough characters to get a 4 arrow chain in, I don't have a clue on how to check if 3 arrows using Graham's and superfactorials is enough.

I specified ASCII because it eliminates things like arrows. I think it makes it more interesting to limit it that way.

r22 wrote:
Whats the ruling on my alternate composite function notation?
(F^x)(y) == F^x_(y) == F^x (y)
5 chars 4 chars
I think a subscript (_) or evena space ( ) is valid for negating the superscript (^) notation.
I have never seen the underscore used in this way before. I don't want to be defining new uses for characters. Use just what is generally accepted in the wider mathematics community.

Your point with the space (and even without the space) I have seen in things like tan²(x), and I guess it could be extended to tan^2(x). But rather than meaning tan(tan(x)) it means (tan(x))^2

But, just for interest sake, perhaps the construction S^n(x) can be accommodated to mean S(S(S...(x))). In which case a class of new leaders can be constructed. I don't mind keeping this open, so I have constructed a new top value, anyone care to make a new entry?
11 Mar 2008, 03:38
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2, 3 ... 12, 13, 14 ... 27, 28, 29  Next

Forum Rules:
 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 forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum