2
$\begingroup$

In our lecture we have the following relationships: enter image description here I have problems to understand these abstract classes. First of all, our Turingmachines are defined as $1$ input tape and $k$ working tapes. DSPACE(f)(resp. NSPACE(f)) means all languages that are excepted by Turingmachines which are deterministic (resp. non-deterministic) and f-spacebounded. DTIME(f)(resp. NTIME(f)) means all languages that are excepted by Turingmachines which are deterministic (resp. non-deterministic) and f-timebounded.

If I look at $1$ for DSPACE, I get $$ DSPACE(\mathcal{O}(f)) = DSPACE_{1-tape}(f).$$ So I know that the left side is the union of all DSPACE($c\cdot f), c\in\mathbb N$, but no amount of tapes is given. So, does that mean, if I have a problem and I know it can be solved in time $15^{7}\cdot f$ and needs a large number of tapes, then I know there is a TM that solves the problem in time $f$ and needs only $1$ tape?

Point $2$ is even more confusing. I understand it in the way that it says, if I have a problem that needs time $15^7\cdot f$, then there is a TM for the same problem that only needs time $f$. I am am consufed because the folliwng theorem (Hennie-Stearns) in the lecture says enter image description here but here I have a number $k$ of tapes?

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.