Some remarks on real numbers induced by first-order spectra

DOI10.1215/00294527-3489987zbMath1402.03037OpenAlexW2324792240MaRDI QIDQ306827

Sune Kristian Jakobsen, Jakob Grue Simonsen

Publication date: 1 September 2016

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.ndjfl/1458829375

zbMATH Keywords

computational complexityfirst-order logiccomputability theoryspectral reals

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Model theory (number-theoretic aspects) (11U09) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forbidden words in symbolic dynamics
• The Arithmetical Hierarchy of Real Numbers
• Finite state languages
• On?-Languages whose syntactic monoid is trivial
• Diophantine properties of real numbers generated by finite automata
• Automatic Sequences
• The Construction of Decimals Normal in the Scale of Ten
• Turing machines and the spectra of first-order formulas
• An Introduction to Symbolic Dynamics and Coding
• Fifty years of the spectrum problem: survey and new results
• On the Computational Complexity of Algorithms
• On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction