scientific article; zbMATH DE number 3995646
[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.
- On fixpoint arithmetic and infinite time Turing machines
- scientific article; zbMATH DE number 819737
- scientific article; zbMATH DE number 1344922
- scientific article; zbMATH DE number 4118351
- Bounded arithmetic and propositional proof complexity
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- The computational power of bounded arithmetic from the predicative viewpoint
- Bounded arithmetic and descriptive complexity
- Publication:4893147
- Presburger arithmetic with bounded quantifier alternation
- A remark on middle space bounded alternating Turing machines
- Time-space tradeoffs for satisfiability
- Transfinite induction within Peano arithmetic
- Bounding lemmata for non-deterministic halting times of transfinite Turing machines
- scientific article; zbMATH DE number 4033719 (Why is no real title available?)
- Fluted formulas and the limits of decidability
- Truth definition for _0 formulas and PSPACE computations
- Computation models and function algebras
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)