1
$\begingroup$

This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups.

Another example to what I'm referring to, would be Conway's Game of Life simulating itself.

The first example runs through a bunch of modifications at 0.1fps and the second example is obviously also significantly slower than the original.

Can something be said about the performance/complexity of such systems, besides that they obviously have to be way slower than the original they're simulating?

Bonus question: Maybe the question could be more precise posed as 'How many states does a Turing machine need at minimum, if it simulates another Turing machine with N states?', but I assume if one interprets "simulating" as producing the same output for the same input, the answer is simply N?

(I am not sure that I'm not confusing space- and time complexity with the second question. The main question is about time complexity.)

$\endgroup$

1 Answer 1

2
$\begingroup$

You can build a universal Turing machine with only 7 states, or only 15 states if you require that the tape store binary symbols. See https://en.wikipedia.org/wiki/Universal_Turing_machine#Smallest_machines.

It follows that there is always a way to simulate a Turing machine with N states, using a Turing machine with 15 states. So the minimum is guaranteed to be small, even if N is very large.

As far as your question about the time complexity of simulating a machine of type A with a machine of system B, the answer depends on A and B. Often it will be possible to simulate efficiently (e.g., in linear or quadratic time), but it depends on what A,B are (Turing machines? RAM machines? tag systems? Conway's game of life? Magic the Gathering decks?).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.