Turing machines and the spectra of first-order formulas with equality
Neil Deaton Jones, Alan L. Selman · 1972
In this paper we show that these similarities are not accidental - that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference (if any) between deterministic and non-deterministic time-or space-bounded Turing machines.