I'm making a program that involves making models of and working with arbitrary systems (or programs). What is the most computationally efficient Turing complete system to model these in?

By "arbitrary system", I mean anything with inputs and outputs. It could be anything from a function that adds 1 to the input to a complicated video game.

What is the most computationally efficient (or fastest) Turing complete system to simulate these arbitrary systems in?

For example, if you were to simulate any program as a test (for example, a 4-bit adder) in some Turing complete system, what system would result in that test program getting simulated the fastest?

User D.W. suggested using asymptotic worst-case runtime as the metric for evaluating the different systems' computational efficiency.

  • 1
    $\begingroup$ I think you're going to have to expand on what you mean. How do you measure the computational efficiency of a system? It's not clear what you mean by "arbitrary systems" (what kinds of systems?) or by "making models of them" (what do you want to do with these models? what capabilities do you want to have?) What approaches have you considered? $\endgroup$
    – D.W.
    Apr 19, 2022 at 4:47
  • $\begingroup$ @D.W. I've edited the question, thanks $\endgroup$
    – user149991
    Apr 20, 2022 at 0:45
  • $\begingroup$ Thanks for answering some of the questions I raised. However, I think we need clarity on them all. I still don't understand what you mean by "computationally efficient" or how you will evaluate proposed answers. I suggest you define the metrics you use to evaluate answers. It might also help to share with us what approaches you've considered and how you evaluate them (how computationally efficient do you consider they are?) $\endgroup$
    – D.W.
    Apr 20, 2022 at 1:40
  • $\begingroup$ @D.W. I've edited the question again. The metric is just the speed at which the model is simulated. I don't know where to begin with finding the most efficient Turing complete system, so I haven't considered any approaches yet. For clarity: to find how "computationally efficient" a Turing complete system is, write any program and check how fast it runs compared to the same program in any other system. $\endgroup$
    – user149991
    Apr 21, 2022 at 0:29
  • $\begingroup$ I don't really understand the question. Suppose I was considering "Turing machines" or "word-RAM machines" as my two candidate systems. How would I measure which one is more computationally efficient? $\endgroup$
    – D.W.
    Apr 21, 2022 at 2:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.