No label defined (Q4723712)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3995646
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3995646

      Statements

      0 references
      1986
      0 references
      bounded arithmetic
      0 references
      alternating Turing machine
      0 references
      \(\Delta _ 0\)-hierarchy
      0 references
      first-order arithmetic with bounded quantifiers
      0 references
      alternations of bounded quantifiers
      0 references
      constant alternation
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references