{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:00:58Z","timestamp":1759147258581},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":14621,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1974,3]]},"abstract":"H. Scholz [11] defined the spectrum<\/jats:italic> of a formula \u03c6 of first-order logic with equality to be the set of all natural numbers n<\/jats:italic> for which \u03c6 has a model of cardinality n<\/jats:italic>. He then asked for a characterization of spectra. Only partial progress has been made. Computational aspects of this problem have been worked on by Gunter Asser [1], A. Mostowski [9], and J. H. Bennett [2]. It is known that spectra include the Grzegorczyk class and are properly included in . However, no progress has been made toward establishing whether spectra properly include , or whether spectra are closed under complementation.<\/jats:p>A possible connection with automata theory arises from the fact that contains just those sets which are accepted by deterministic linear-bounded Turing machines (Ritchie [10]). Another resemblance lies in the fact that the same two problems (closure under complement, and proper inclusion of ) have remained open for the class of context sensitive languages for several years.<\/jats:p>In this paper we show that these similarities are not accidental\u2014that 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 nondeterministic time or space bounded Turing machines.<\/jats:p>In particular we show that spectra are just those sets which are acceptable by nondeterministic Turing machines in time 2cx<\/jats:italic><\/jats:sup>, where c<\/jats:italic> is constant and x<\/jats:italic> is the length of the input. Combining this result with results of Bennett [2], Ritchie [10], Kuroda [7], and Cook [3], we obtain the \u201chierarchy\u201d of classes of sets shown in Figure 1. It is of interest to note that in all of these cases the amount of unrestricted read\/write memory appears to be too small to allow diagonalization within the larger classes.<\/jats:p>","DOI":"10.2307\/2272354","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:27:55Z","timestamp":1146936475000},"page":"139-150","source":"Crossref","is-referenced-by-count":71,"title":["Turing machines and the spectra of first-order formulas"],"prefix":"10.1017","volume":"39","author":[{"given":"Neil D.","family":"Jones","sequence":"first","affiliation":[]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200065531_ref010","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0158822-2"},{"key":"S0022481200065531_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80017-6"},{"key":"S0022481200065531_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90120-2"},{"key":"S0022481200065531_ref006","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"S0022481200065531_ref003","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321625"},{"key":"S0022481200065531_ref002","unstructured":"Bennett J. , On spectra, Doctoral Dissertation, Princeton University, Princeton, N.J., 1962."},{"key":"S0022481200065531_ref001","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19550010403"},{"key":"S0022481200065531_ref009","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19560021007"},{"key":"S0022481200065531_ref011","first-page":"160","volume":"17","author":"Scholz","year":"1952","journal-title":"Problems"},{"key":"S0022481200065531_ref004","first-page":"151","volume-title":"Third ACM Symposium on Theory of Computing","author":"Cook","year":"1971"},{"key":"S0022481200065531_ref012","first-page":"569","article-title":"Impossibility of an algorithm for the decision problem in finite classes","volume":"70","author":"Tractenbrot","year":"1950","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200065531_ref005","first-page":"1","article-title":"Some classes of recursive functions","volume":"44","author":"Grzegorczyk","year":"1953","journal-title":"Rozprawy Mathematyczne"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200065531","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:37:51Z","timestamp":1559151471000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200065531\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,3]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1974,3]]}},"alternative-id":["S0022481200065531"],"URL":"https:\/\/doi.org\/10.2307\/2272354","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1974,3]]}}}