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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.