Timeline for The max output of 11-line long programs in Minsky computer language
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 6, 2021 at 5:46 | comment | added | Wlod AA | @Carl-FredrikNybergBrodda, I'd present serious problems in consecutive posts, as I had planned, but I am tired of all this... . | |
| Oct 5, 2021 at 10:27 | comment | added | Emil Jeřábek | No need to email me, I have read the post. I was just explaining why I posted the comment here. | |
| Oct 5, 2021 at 5:33 | comment | added | Wlod AA | (@EmilJeřábek, I can email you that last post that I have removed. My email address is [email protected]). | |
| Oct 5, 2021 at 5:25 | comment | added | Wlod AA | @EmilJeřábek, very nice! ##### (An anonymous had to downvote my post, and I am sick of them since this sick procedure goes on like this for years on MO). PS. I patiently reread your comment. This is amazing! (It be so nice if MO were nicer). | |
| Oct 4, 2021 at 11:16 | comment | added | Emil Jeřábek | Your newest post was deleted before I could react, but just a quick comment: using base-$m$ expansion of $n$ with $m\approx\frac{\log n}{\log\log n}$, it is easy to show that $\alpha_k(n)=O\bigl(\frac{\log n}{\log\log n}\bigr)$ for some constant $k$ (I can make do with $k=3$). Thus, the functions $\beta(n)$ and $\beta_k(n)$ for $k\ge3$ have rate of growth $n^{\Theta(n)}$, i.e., your upper bound cannot be significantly improved. | |
| Oct 1, 2021 at 6:54 | comment | added | Wlod AA | @user44191, actually, a simple forward jump (goto) with just one ++ line for that variable can be useful as I've shown for instance on sci.math.research in 1993 (I improved on the classical Minsky 23-line program; in the sportive-naive sense by a lot :) ). | |
| Sep 30, 2021 at 22:35 | comment | added | user44191 | This also might be appropriate on codegolf.stackexchange. | |
| Sep 30, 2021 at 16:33 | comment | added | user44191 | I should add some caveats to the above - it's possible for a variable to usefully act as a "while(true)" control without a "--" line if another variable can "break" out of the loop, or to act as a "jump into a loop" control. I'm somewhat skeptical of the usefulness of those, though. | |
| Sep 30, 2021 at 16:00 | comment | added | user44191 | Quick notes that may help (and which generalize easily): with the exception of the "output" variable, all variables have an overhead of at least one line of each type to be "useful". If they're missing the "++" line, they never go above 0; if they're missing the "if" line, they never affect the "output"; if they're missing the "--" line, they never make the "if" line useful. In this case, that limits us to a maximum of 4 variables. That can probably be improved to needing 2 "++" lines, limiting us to 3 variables at most. | |
| Sep 30, 2021 at 12:55 | review | Close votes | |||
| Oct 6, 2021 at 16:17 | |||||
| Sep 30, 2021 at 11:36 | comment | added | Emil Jeřábek | All right. I have now removed my comments as they served their purpose. | |
| Sep 30, 2021 at 11:17 | comment | added | Carl-Fredrik Nyberg Brodda | I don't really see how this is about research-level mathematics. It seems a better fit for cs.stackexchange. | |
| Sep 30, 2021 at 10:57 | history | edited | Wlod AA | CC BY-SA 4.0 |
typo. It’s “variables”, not “lines” in that one case.
|
| Sep 30, 2021 at 10:51 | comment | added | Wlod AA | @EmilJeřábek, thank you for the info about the 2-register models. I've removed the offensive comment. Sorry. BTW, my 11-line program uses only 2 registers -- it's even hard for 11 lines to use efficiently more than 2 registers. | |
| Sep 30, 2021 at 10:17 | history | edited | Wlod AA | CC BY-SA 4.0 |
general remarks added
|
| Sep 30, 2021 at 9:40 | history | edited | Wlod AA | CC BY-SA 4.0 |
a math typo (variable b rather than a)
|
| Sep 30, 2021 at 9:38 | comment | added | Wlod AA | @PeterTaylor, yes, of course, b. Thank you, I'll correct it in a moment. | |
| Sep 30, 2021 at 9:37 | comment | added | Wlod AA | These kinds of problems were of interest to mathematical logicians. To me, it is about the complexity and fundamental challenges and limitations of computations, and in particular of the recursiveness. | |
| Sep 30, 2021 at 9:31 | history | edited | Wlod AA | CC BY-SA 4.0 |
more explanations
|
| Sep 30, 2021 at 9:16 | history | edited | Wlod AA | CC BY-SA 4.0 |
an explanation was missing
|
| Sep 30, 2021 at 8:21 | comment | added | Wlod AA | I simulate Marvin Minsky language in Perl (one can use about every true computer language). It's a flexible fun toy. I'd add a Perl sample to my answer above or even in a comment if someone is interested, let me know. | |
| Sep 30, 2021 at 8:10 | history | edited | Wlod AA | CC BY-SA 4.0 |
an ommitted phrase inserted
|
| Sep 30, 2021 at 8:04 | history | asked | Wlod AA | CC BY-SA 4.0 |