Let us assume , d. H. there is a nondeterministic Turing machine that takes up space and accepts exactly language . Due to the limited space, it can only assume different configurations , the number of their states and the number of different ribbon symbols denoting. So if this machine accepts an input of length , (if and only then) there is also an accepting run with fewer than computing steps. Let's consider a predicate
Based on the configuration, the NTM can achieve the configuration within computing steps .
Identify the initial configuration of the NTM when entering the word and the accepting hold configuration. Then we can formulate " accepted " (with a suitable constant depending on and ) as:
.
We know that a deterministic Turing machine with space requirements can calculate whether it is true. Also has the property
there is an intermediate configuration with and .
A deterministic Turing machine can calculate by enumerating all possible configurations and calculating and for each (one after the other) . For this purpose (for suitable ) band cells for and band cells for the calculation of or are sufficient . In particular, such a DTM can determine with space requirements whether and thus whether .
The choice of suitable constants is possible in particular because of .