tag:blogger.com,1999:blog-3722233.post3507110503322010708..comments2019-05-21T08:49:40.578-04:00Comments on Computational Complexity: Ronald Graham's other large number. Well---- it was large in 1964 anyway.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-71518748008223443132019-05-15T14:02:04.518-04:002019-05-15T14:02:04.518-04:00thanks.
Fixed.thanks.<br />Fixed.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63060830489849094462019-05-15T13:49:47.678-04:002019-05-15T13:49:47.678-04:00Bill, the link that you gave to the Erdos-Graham p...Bill, the link that you gave to the Erdos-Graham paper is off.<br />:)<br />Try this:http://www.math.ucsd.edu/~ronspubs/79_09_combinatorial_number_theory.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71030636970400453342019-05-13T15:01:20.405-04:002019-05-13T15:01:20.405-04:00AH-
Vinogradovs theorem:
Every SUFF LARGE odd num...AH- <br />Vinogradovs theorem:<br />Every SUFF LARGE odd numbers can be written as the sum of<br />three primes.<br /><br />I asked a number theorist how large suff large was. He said `prob 10^{80} but I haven't bothered to check'<br />I wonder if anyone had bothered to check.<br /><br />Later it was shown for all odds \ge 5.<br /><br />But YES- there could be a theorem like this where the number, if someone bothered to find it, would be bigger than GN or other large numbers in math.<br /><br /><br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69600096513330147832019-05-13T04:07:03.840-04:002019-05-13T04:07:03.840-04:00I think that definition requires some qualificatio...I think that definition requires some qualification. For instance it's not uncommon in computability theory to just say things like "let s be greater than the largest use of any function on any inputs below a number mentioned so far in this proof." Usually, these are just one part in an infinite construction so don't really count but I bet if you looked carefully you'd find a proof where some lemma in computability theory was implicitly using something that was effectively applying the busy beaver to the busy beaver of some huge number.<br /><br />I mean morally it shouldn't really count because whenever it's really a specific number being used it's usually a result of pure laziness. Ehh, it just needs to be finite and I've only executed finitely many partial functions on finitely many inputs so let's just say the bound is the max of the results of Turing machines with index less than the largest number used so far in this proof with input less than the largest number used so far in this proof.TruePathhttps://www.blogger.com/profile/00124043164362758796noreply@blogger.com