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$