This is just an elaboration of the proof noted above. Consider the following algorithm:
A(x) {
Step 1: If x is not of the form $(M,1^{t})$ for some nondeterministic Turing machine $M$ and integer $t$, reject.
Step 2: Compute $q = 2^{g(n)}$ where $n$ is the length of $x$.
/ * Needs $O(g(n))$ deterministic space, assuming $g$ is constructible */
Step 3: Using a universal Turing machine, simulate $M$ on $x$ for $q$ steps. If $M$ accepts $x$, accept $x$. Otherwise, reject $x$.
/ * This simulation requires only $O(g(n))$ space */
}
Claim: $L(A)$ is not equal to $L(M)$ for any $O(f(n))$ space non deterministic Turing machine if $f(n) = o(g(n))$ and $f(n)$ is constructible.
Proof: For the sake of contradiction, assume that a non deterministic Turing machine $M$ accepts $L(A)$ in $O(f(n))$ space. Then, by <PERSON>-Szelepscsenyi theorem, there exists a machine $N$ that accepts the complement of $L$ in $O(f(n))$ space.
Consider a string $x$ of the form $x = (N, 1^{t})$ of length $n$ such that $t$ is large enough to ensure that the simulation of $N$ on input $x$ in step 3 of the algorithm runs to completion on all computational paths of $N$.
Now suppose $(N, 1^{t})\in L(A)$. 743
By Step 3 of the algorithm, this means that $N$ accepts $(N, 1^{t})$ on at least one computational path - that is, $(N, 1^{t})\in L(N)$. However, both $A$ and $N$ cannot accept the input $(N, 1^{t})$ because of our assumption that $L(N)$ is the complement of $L(A)$.
Hence, we conclude that $A$ does not accept $(N, 1^{t})$. But this too is contradictory. By Step 3 of the algorithm, $N$ must reject $(N, 1^{t})$ on all computational paths. In other words, $N$ must reject $(N, 1^{t})$. But both $A$ and $N$ cannot reject $(N, 1^{t})$ as $L(N)$ was assumed to the the complement of $L(A)$.
We conclude that our assumption that $M$ accepts $L(A)$ is contradictory and that $L(A)$ is different from the language accepted by any non deterministic Turing machine that uses $O(f(n))$ space for any $f(n)=o(g(n))$. 743