Timeline for A simple language and systematic computations
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 3, 2013 at 16:27 | comment | added | Emil Jeřábek | BTW, you can get a slightly better upper bound (but still with exponent 2) as follows. For any $0<v\le n$, there are $\le((n+1)v)^n$ programs using $n$ lines and $v$ variables, assuming these variables are $a_0,\dots,a_{v-1}$. However, any permutation of variable labels (except 0) yields a different program with the same exit value, hence such programs can output only $((n+1)v)^n/(v-1)!$ different integers. This expression is maximized when $n\sim v\log v$, in which case Stirling’s approximation yields $M(n)\le\left(\frac{n^2}{(e-o(1))\log n}\right)^n$. (All $\log$’s are natural here.) | |
| Oct 3, 2013 at 15:33 | comment | added | Emil Jeřábek | Your argument saves a factor roughly $e^n$, but the bound is still $M(n)\le n^{(2-o(1))n}$. I didn’t bother explicitly optimizing constants in the argument above, but using the proof of Lupanov’s theorem such as in www2.cs.uni-paderborn.de/cs/ag-madh/WWW/Teaching/2005WS/… and adopting it directly for SL instead of going through circuit simulation, one can actually push it to $M(n)\ge n^{(1-o(1))n}$. So, the constant in the exponent is between 1 and 2. It's not clear to me what should be the right value. | |
| Oct 3, 2013 at 14:32 | comment | added | Emil Jeřábek | The easy way to avoid tipping is to make the answer community wiki. | |
| Oct 3, 2013 at 5:16 | history | edited | Włodzimierz Holsztyński | CC BY-SA 3.0 |
English
|
| Oct 3, 2013 at 5:15 | comment | added | Włodzimierz Holsztyński | Some variations of the above proof are possible. One could consider just n-instruction proofs, and with an arbitrary output but it would have to be indicated as the output. The enumeration of the variables would be similar: $v\lt t$ whenever the variable index v would be less or equal the line number t. (The bound would be the same). | |
| Oct 3, 2013 at 4:39 | history | edited | Włodzimierz Holsztyński | CC BY-SA 3.0 |
typo
|
| Oct 3, 2013 at 4:34 | history | edited | Włodzimierz Holsztyński | CC BY-SA 3.0 |
simpler English
|
| Oct 3, 2013 at 4:19 | history | answered | Włodzimierz Holsztyński | CC BY-SA 3.0 |