I am looking for bounds - both lower and upper - on the time and spacial complexity of simulating Turing-complete systems with each other. (I am aware that both time and space are ill-defined with many systems. However, I do not know of a better way of describing them.)
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Can you ask a precise question, say, about a single pair of Turing-complete systems? This site is not very good for "I am interested in such-and-such topics"; it's better for a specific, concrete question with a single reasonable-sized answer. As it stands this question seems like it might be too broad, since it asks for people to provide lower and upper bounds for all combinations of pairs of Turing-complete systems, and there's an awful lot of possible combinations. Community votes, anyone? $\endgroup$– D.W. ♦Sep 29, 2015 at 4:03
-
$\begingroup$ If this is not a good place to ask such a question, where is? I am aware that this question is broad - however I do not know of a way that narrows it down that still remains interesting. In particular, with Turing-complete systems you'll occasionally have roundabout layers of emulation being faster than emulating directly. (For instance, it's faster to go tag machine -> clockwise Turing machine -> Turing machine than it is to go tag machine -> Turing machine, as per the proof of the Turing-completeness of Rule 110) $\endgroup$– TLWSep 29, 2015 at 11:44
-
2$\begingroup$ I'm not sure where else you could ask the question but I agree that it's too broad for Stack Exchange. A good answer would, essentially, be a publishable survey paper and that's far too much work for a Stack Exchange answer. $\endgroup$– David RicherbySep 29, 2015 at 13:56
Add a comment
|