Timeline for Does there exist a general theory of "arithmetic complexity"/"arithmetic height"?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9, 2010 at 0:29 | comment | added | Joel David Hamkins | Sam, if you restrict the programs to have a particularly simple form, such as "the 3rd solution of such-and-such equation" (as in Kevin's answer), then it becomes decidable, but still retains the essence of the Kolmogorov idea. | |
| Mar 9, 2010 at 0:01 | comment | added | Sam Derbyshire | The issue I have with this answer (and Joel's) is that it involves doing a lot of work on the computational side, and often (as you mention), you end up with something uncomputable. But it seems like you can do something very explicit, similar to the height function used for elliptic curves (I edited this in the first post), and avoid having to do much work about computation. | |
| Mar 8, 2010 at 23:37 | history | answered | Neel Krishnaswami | CC BY-SA 2.5 |