{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T05:17:36Z","timestamp":1771651056746,"version":"3.50.1"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T00:00:00Z","timestamp":1591142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,9,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We consider notions of space by Winter [21, 22]. We answer several open questions about these notions, among them whether low space complexity implies low time complexity (it does not) and whether one of the equalities P=PSPACE, P$_{+}=$PSPACE$_{+}$ and P$_{++}=$PSPACE$_{++}$ holds for ITTMs (all three are false). We also show various separation results between space complexity classes for ITTMs. This considerably expands our earlier observations on the topic in Section 7.2.2 of Carl (2019, Ordinal Computability: An Introduction to Infinitary Machines), which appear here as Lemma $6$ up to Corollary $9$.<\/jats:p>","DOI":"10.1093\/logcom\/exaa025","type":"journal-article","created":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T19:10:58Z","timestamp":1590606658000},"page":"1239-1255","source":"Crossref","is-referenced-by-count":6,"title":["Space and time complexity for infinite time Turing machines"],"prefix":"10.1093","volume":"30","author":[{"given":"Merlin","family":"Carl","sequence":"first","affiliation":[{"name":"Europa-Universit\u00e4tFlensburg, Institut f\u00fcr mathematische, naturwissenschaftliche und technische Bildung, Abteilung f\u00fcr Mathematik und ihre Didaktik"}]}],"member":"286","published-online":{"date-parts":[[2020,6,3]]},"reference":[{"key":"2020081904464704000_ref1","volume-title":"BIWOC Report","author":"Dimitriou","year":"2007"},{"key":"2020081904464704000_ref2","doi-asserted-by":"crossref","first-page":"1403","DOI":"10.1016\/j.apal.2014.04.010","article-title":"The distribution of ITRM-recognizable reals","volume":"165","author":"Carl","year":"2012","journal-title":"Annals of Pure and Applied Logic"},{"key":"2020081904464704000_ref3","doi-asserted-by":"crossref","DOI":"10.1515\/9783110496154","volume-title":"Ordinal Computability: An Introduction to Infinitary Machines","author":"Carl","year":"2019"},{"key":"2020081904464704000_ref4","article-title":"Resetting $\\alpha $-register machines and ZF","author":"Carl","year":"2019"},{"key":"2020081904464704000_ref5","volume-title":"Ranks of Countable Length","author":"Carl","year":"2019"},{"key":"2020081904464704000_ref6","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1093\/logcom\/exi022","article-title":"P$\\ne $NP$\\cap $co-NP for infinite time Turing machines","volume":"15","author":"Deolalikar","year":"2005","journal-title":"Journal of Logic and Computation"},{"key":"2020081904464704000_ref7","article-title":"Two observations regarding infinite time Turing machines","volume-title":"BIWOC Report","author":"Friedman","year":"2007"},{"key":"2020081904464704000_ref8","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0003-4843(79)90025-1","article-title":"The next admissible ordinal","volume":"17","author":"Gostanian","year":"1979","journal-title":"Annals of Mathematical Logic"},{"key":"2020081904464704000_ref9","doi-asserted-by":"crossref","first-page":"567","DOI":"10.2307\/2586556","article-title":"Infinite time Turing machines","volume":"65","author":"Hamkins","year":"2000","journal-title":"Journal of Symbolic Logic"},{"key":"2020081904464704000_ref10","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00153-009-0167-x","article-title":"The basic theory of infinite time register machines","volume":"49","author":"Carl","year":"2010","journal-title":"Archive for Mathematical Logic"},{"key":"2020081904464704000_ref11","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1007\/978-3-540-69407-6_34","article-title":"An enhanced theory of infinite time register machines","volume-title":"Logic and Theory of Algorithms","author":"Koepke","year":"2008"},{"key":"2020081904464704000_ref12","volume-title":"Ordinalzahltheoretische Berechnungsm\u00f6glichkeiten","author":"Matzner","year":"2016"},{"key":"2020081904464704000_ref13","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/978-3-642-03073-4_29","article-title":"Ordinal computability","volume-title":"Mathematical Theory and Computational Practice","author":"Koepke","year":"2009"},{"key":"2020081904464704000_ref14","doi-asserted-by":"crossref","first-page":"377","DOI":"10.2178\/bsl\/1122038993","article-title":"Turing computations on ordinals","volume":"11","author":"Koepke","year":"2005","journal-title":"The Bulletin of Symbolic Logic"},{"key":"2020081904464704000_ref15","first-page":"143","article-title":"Primitive recursive set functions","volume-title":"Axiomatic Set Theory","author":"Jensen","year":"1967"},{"key":"2020081904464704000_ref16","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/11780342_34","article-title":"Space bounds for infinitary computations","volume-title":"Logical Approaches to Computational Barriers","author":"L\u00f6we","year":"2006"},{"key":"2020081904464704000_ref17","volume-title":"Recursive Aspects of Descriptive Set Theory","author":"Mansfield","year":"1985"},{"key":"2020081904464704000_ref18","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s00605-002-0545-5","article-title":"P$\\ne $NP for infinite time Turing machines","volume":"139","author":"Schindler","year":"2003","journal-title":"Monatshefte f\u00fcr Mathematik"},{"key":"2020081904464704000_ref19","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1016\/j.tcs.2008.09.050","article-title":"Characteristics of discrete transfinite time Turing machine models: halting times, stabilization times, and normal form theorems","volume":"410","author":"Welch","year":"2009","journal-title":"Theoretical Computer Science"},{"key":"2020081904464704000_ref20","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1112\/S0024609399006657","article-title":"The length of infinite time Turing machine computations","volume":"32","author":"Welch","year":"2000","journal-title":"Bulletin of the London Mathematical Society"},{"key":"2020081904464704000_ref21","volume-title":"Space Complexity in Infinite Time Turing Machines","author":"Winter","year":"2007"},{"key":"2020081904464704000_ref22","first-page":"126","article-title":"Is P=PSPACE for infinite time Turing machines?","volume-title":"ILC 2007","author":"Winter","year":"2009"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/6\/1239\/33663202\/exaa025.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/6\/1239\/33663202\/exaa025.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,19]],"date-time":"2020-08-19T08:47:32Z","timestamp":1597826852000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/30\/6\/1239\/5850578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,3]]},"references-count":22,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2020,6,3]]},"published-print":{"date-parts":[[2020,9,4]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaa025","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,9]]},"published":{"date-parts":[[2020,6,3]]}}}