A genral Turing model with one tape to define sublinear space (L,NL,..)

Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and a work tape; or often three: with an additional output tape. (We do this because the reading of the input would cost us linear space.)

I'm looking for a general Turing model with just one tape and one consistent definition for space and for complexity that works in all the cases, inclusively the sub-linear case of L (Logspace), NL (NLogspace).. and the more famous P, NP, PSPACE etc.

For this purpose obviously we must change the space definition - but how best?

EDIT: For example: if we just count the new written cells in a one-tape machine would this solve the problem?

  • $\begingroup$ Why are you looking for such a model? $\endgroup$ – Andrej Bauer Sep 21 '20 at 18:51
  • $\begingroup$ It would be more practical if one general uniform definition is used. $\endgroup$ – rl1 Sep 21 '20 at 19:38
  • 3
    $\begingroup$ The "work tape" definition can be used for all complexity classes you mention. It is the general uniform definition you're after $\endgroup$ – Yuval Filmus Sep 21 '20 at 20:38
  • 1
    $\begingroup$ Since you are shooting for "practical", it's more practical to have working tapes. $\endgroup$ – Andrej Bauer Sep 21 '20 at 20:46
  • $\begingroup$ @YuvalFilmus I know this definition works in all cases but I would prefer a simpler model with just one tape. I've added a special case in the "EDIT". $\endgroup$ – rl1 Sep 21 '20 at 21:32

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.