1
$\begingroup$

To define time complexity the Turing machine model with only one tape (for input, work and output) is used. This TMM is also used to define the $s(n)$-space complexity for $s(n) \ge n$.

But if $s(n)$ is sublinear e.g. $s(n)=\log(n)$ this TMM does not work. So usually a new TMM is used: the Turing machine get a new tape, the input tape where only reading is allowed (nor deleting or writing).

  1. Is there a computation model which is suitable to define time complexity and space complexity (even if the space function is sublinear)?
  2. Is it possible to find a "global" $s(n)$-space complexity definition for the "classical" Turing machines with only one tape?
$\endgroup$

closed as off-topic by Emil Jeřábek, Jan Johannsen, Damiano Mazza, Kaveh, Mohammad Al-Turkistany Jul 25 '17 at 13:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Jan Johannsen, Damiano Mazza, Kaveh, Mohammad Al-Turkistany
If this question can be reworded to fit the rules in the help center, please edit the question.