0
$\begingroup$

Meaning for example lower or upper bounds of any kind, possibly concerning time or space complexity?

$\endgroup$
  • $\begingroup$ What do you mean, exactly? A Turing machine obviously simulates itself perfectly, with no slowdown. Given a "reasonable" encoding of a Turing machine, there is a universal Turing machine that simulates any given machine. How long it takes depends on details of the description. There is a famous speedup theorem, if a Turing machine takes $n$ steps, for any constant $k$ there is one that does $n / k$ $\endgroup$ – vonbrand Mar 3 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.