Show that for any function $\mathit{f}\mathbf{:}\mathit{N}\mathbf{\to }{\mathit{R}}^{\mathbf{+}}$where $\mathit{f}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\ge }\mathit{n}$, the space complexity class is$\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}\mathbf{\left(}\mathbf{f}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}$the same whether you define the class by using the single tape TM model or the two-tape read-only input TM model.

$SPACE\left(f\left(n\right)\right):Let f:N\to R^{+}$be a function. The Space completely class $SPACE\left(f\left(n\right)\right)$is defined as follows:

$SPACE\left(f\left(n\right)\right)=\left\{L|L is a language decided by an O\left(f\left(n\right)\right) space \det er\min istic Turning machine\right\}$

Now we have to prove that, class $SPACE\left(f\left(n\right)\right)$is the same whether we define z by using the single tape TM or two tapes read-only input TM model.

The turning machine model makes use of an infinite tape with unlimited memory and a tape head that can read and write symbols and move around the tape.

By omitting the segment of tape to the left of the input, the doubly infinite tape can replicate an ordinary turning machine.

A multi-tape turning machine isn't as powerful as a single-tape turning machine. By using the second tape as the negative half of the doubly infinite tape, a two-tape turning machine can replicate a doubly infinite one.

$SPACE\left(f\left(n\right)\right)$formalizes the class of problems that can be solved by computers with bounded memory. (Real world!)

$SPACE\left(f\left(n\right)\right)$problems could potentially take a long time to solve.

Intuitively space and time seem to be interchangeable.

Just because a problem needs only linear space does not mean it can be solved in linear time.

1. First, we have to scan the read only tape.
2. Contents of the read only tape are copied to the work tape.
3. Remainer of the contents is simulated by treating the read | write work- tape as the input tape of a single- tape TM.

• Clearly only log n space is used to copy the contents.
• Since $f\left(n\right)>n$, we can write all of the input on are work-tape
• In this way we simulated single-tape TM on two tape read only TM.

• There is no participation from single tape TM; we are working over the first input symbols, using the remainder of the tape as our work area.
• For n symbols, add n amount of space. By increasing space we add constant to n so from (i) and (ii) simulations we proved that class $SPACE\left(f\left(n\right)\right)$is the same whether we defined it by using the single tape TM or Two-tape read_only input TM.