Timeline for Does there exist a general theory of "arithmetic complexity"/"arithmetic height"?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9, 2010 at 14:40 | comment | added | kakaz | @Joel: Let's fix representation of a numbers. Information content, or compressibility is defined up to constant, so probably You may easily compare information content within given numbering system, whilst comparison between them require some universal framework for representing different systems. Of course one may use Universal Turing Machine, but even then it may be unintuitive. For example one may introduce symbol s, for some incompressible number. And then You may have very simple description for that number: just s. So "constants are very important here";-) | |
| Mar 9, 2010 at 13:08 | comment | added | Joel David Hamkins | Yes, Kevin, this is Berry's paradox. Let n be the smallest number that cannot be described in a MathOverflow comment field.....Contradiction! | |
| Mar 9, 2010 at 4:40 | comment | added | Kevin O'Bryant | Makes me wonder about "the smallest number that cannot be described in English using exactly eighty nine symbols". Math is so very lovely. | |
| Mar 8, 2010 at 23:44 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 1428 characters in body; deleted 1 characters in body
|
| Mar 8, 2010 at 23:33 | comment | added | Steve Huntsman | Also see PSLQ: en.wikipedia.org/wiki/Integer_relation_algorithm | |
| Mar 8, 2010 at 23:33 | comment | added | Steve Huntsman | For the purposes of the question we can assume that arithmetic operations are given by an oracle that augments the particular universal TM chosen. Of course this doesn't mean the K-complexity would be computable or anything... | |
| Mar 8, 2010 at 23:30 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |