Metric structures and probabilistic computation (Q541224): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
The author uses probabilistic computation to study the effective content of continuous first-order logic in the sense of, for example, \textit{I. Ben Yaacov} and \textit{A. P. Pedersen} [J. Symb. Log. 75, No. 1, 168--190 (2010; Zbl 1194.03028)]. The main result is that if \(T\) is a complete decidable continuous first-order theory, then there is a probabilistically decidable continuously weak structure \({\mathcal M}\) with \({\mathcal M}\) a model of \(T\). This is proven by a Henkin construction of sorts. Some relationships with BPP and with reverse mathematics are discussed. | |||
Property / review text: The author uses probabilistic computation to study the effective content of continuous first-order logic in the sense of, for example, \textit{I. Ben Yaacov} and \textit{A. P. Pedersen} [J. Symb. Log. 75, No. 1, 168--190 (2010; Zbl 1194.03028)]. The main result is that if \(T\) is a complete decidable continuous first-order theory, then there is a probabilistically decidable continuously weak structure \({\mathcal M}\) with \({\mathcal M}\) a model of \(T\). This is proven by a Henkin construction of sorts. Some relationships with BPP and with reverse mathematics are discussed. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Rodney G. Downey / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03C57 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D32 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q30 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5904445 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
computable model theory | |||
Property / zbMATH Keywords: computable model theory / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
continuous first-order logic | |||
Property / zbMATH Keywords: continuous first-order logic / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
probabilistic computation | |||
Property / zbMATH Keywords: probabilistic computation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Henkin construction | |||
Property / zbMATH Keywords: Henkin construction / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q59199685 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2070221296 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0806.0398 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computable structures and the hyperarithmetical hierarchy / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3602612 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A proof of completeness for continuous first-order logic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Continuous first order logic and local stability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Isoperimetric functions of groups and computational complexity of the word problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective categoricity of abelian \(p\)-groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective categoricity of equivalence structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4249365 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Countable algebra and set existence axioms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4249356 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Order-computable sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4526985 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4249727 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Theory of computation. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2715528 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Foundations of recursive model theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3221403 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Isoperimetric and isodiametric functions of groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3395521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3699664 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3392275 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 03:53, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Metric structures and probabilistic computation |
scientific article |
Statements
Metric structures and probabilistic computation (English)
0 references
6 June 2011
0 references
The author uses probabilistic computation to study the effective content of continuous first-order logic in the sense of, for example, \textit{I. Ben Yaacov} and \textit{A. P. Pedersen} [J. Symb. Log. 75, No. 1, 168--190 (2010; Zbl 1194.03028)]. The main result is that if \(T\) is a complete decidable continuous first-order theory, then there is a probabilistically decidable continuously weak structure \({\mathcal M}\) with \({\mathcal M}\) a model of \(T\). This is proven by a Henkin construction of sorts. Some relationships with BPP and with reverse mathematics are discussed.
0 references
computable model theory
0 references
continuous first-order logic
0 references
probabilistic computation
0 references
Henkin construction
0 references