scientific article; zbMATH DE number 3995646

From MaRDI portal
Publication:4723712





[For the entire collection see Zbl 0587.00004.] The main result of this paper is that for every positive integer k there is a \(\Delta_ 0\)-formula (i.e., a formula in first-order arithmetic with bounded quantifiers) which is not equivalent to any \(\Delta_ 0\)- formula containing only k quantifiers. This strengthens earlier work of \textit{A. J. Wilkie} [Lect. Notes Math. 834, 363-369 (1980; Zbl 0483.03024)], and is related to the \(\Delta_ 0\)-hierarchy problem asking whether there is a proper \(\Delta_ 0\)-hierarchy according to the number of alternations of bounded quantifiers needed to define a predicate. As proved by \textit{K. Harrow} [Inf. Control 36, 102-117 (1978; Zbl 0374.02019)], if the \(\Delta_ 0\)-hierarchy does not collapse, then DSPACE(n) contains a set of natural numbers which cannot be defined by any \(\Delta_ 0\)-formula; this would solve a problem of Parikh. For the proof, the author uses Turing machines of constant alternation, inadvertently renamed Turing machines of constant attention in the running head of the odd numbered pages of this article.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723712)