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
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
0.89357215
0 references
0.88094974
0 references
0.8789011
0 references
0.8779206
0 references
0.87690794
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