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
Thread Post new topic Reply to topic
r22



Joined: 27 Dec 2004
Posts: 805
r22
(BB^G)(G)
Post 09 Mar 2008, 17:42
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
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. Confused
Post 09 Mar 2008, 18:21
View user's profile Send private message Visit poster's website Reply with quote
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!

Confused
Post 10 Mar 2008, 03:33
View user's profile Send private message Reply with quote
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.

_________________
¯\(°_o)/¯ unlicense.org
Post 10 Mar 2008, 04:03
View user's profile Send private message Visit poster's website Reply with quote
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! Razz
Post 10 Mar 2008, 04:35
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
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.
Post 10 Mar 2008, 06:57
View user's profile Send private message Visit poster's website Reply with quote
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).

Laughing

_________________
¯\(°_o)/¯ unlicense.org
Post 10 Mar 2008, 15:54
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
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?
Post 10 Mar 2008, 16:00
View user's profile Send private message Visit poster's website Reply with quote
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 Smile
Post 10 Mar 2008, 17:25
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
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 Smile
Somehow I think you ass-u-me too much in this instance Wink
Post 10 Mar 2008, 17:33
View user's profile Send private message Visit poster's website Reply with quote
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.

_________________
¯\(°_o)/¯ unlicense.org
Post 10 Mar 2008, 17:34
View user's profile Send private message Visit poster's website Reply with quote
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.

http://home.earthlink.net/~mrob/pub/math/largenum-4.html

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))
Post 10 Mar 2008, 20:09
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
r22



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

(gn^G)(G)

S(gn(G$))

For completeness
Post 10 Mar 2008, 20:16
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
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: (^)()

_________________
¯\(°_o)/¯ unlicense.org
Post 10 Mar 2008, 21:07
View user's profile Send private message Visit poster's website Reply with quote
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
Post 10 Mar 2008, 21:58
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
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().

_________________
¯\(°_o)/¯ unlicense.org
Post 11 Mar 2008, 00:23
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
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?
Post 11 Mar 2008, 01:35
View user's profile Send private message Visit poster's website Reply with quote
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)
Post 11 Mar 2008, 02:23
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
How about chained arrow notation
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.
Post 11 Mar 2008, 02:53
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
revolution
r22 wrote:
How about chained arrow notation
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?
Post 11 Mar 2008, 03:38
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3 ... 12, 13, 14 ... 27, 28, 29  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.