Timeline for Decidable theories with arbitrary complexity
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2022 at 18:18 | vote | accept | Dmytro Taranovsky | ||
| Aug 18, 2022 at 11:11 | answer | added | Fedor Pakhomov | timeline score: 8 | |
| Aug 18, 2022 at 10:30 | comment | added | Fedor Pakhomov | I just communicated with Albert Visser about Hanf's paper (it was relevant to our recent paper arxiv.org/pdf/2207.08174.pdf , where we needed a construction of essentially undecidable r.e. theory in arbitrary r.e. degree). From Albert I learned about a book "Finitely axiomatizable theories" by M. Peretyatkin, whom was expanding on the works of Hanf and in fact his main theorem solves your question. I'll write a proper answer now. | |
| Aug 17, 2022 at 23:56 | history | edited | Dmytro Taranovsky | CC BY-SA 4.0 |
added 1 character in body
|
| Aug 17, 2022 at 23:53 | comment | added | Dmytro Taranovsky | @JoelDavidHamkins Computational complexity defaults to polynomial time reducibility. I edited the question; let me know if it can be improved further. | |
| Aug 17, 2022 at 23:51 | history | edited | Dmytro Taranovsky | CC BY-SA 4.0 |
clarified computational complexity
|
| Aug 17, 2022 at 23:33 | comment | added | Joel David Hamkins | Can the OP explain precisely what is meant by the phrase "arbitrarily high computational complexity" of a complete finitely axiomatizable theory? I am a little confused, since as Hanson notes, these are decidable theories. And no countable set can be unbounded in the Turing degrees. So I'm just not sure what is meant. | |
| Aug 17, 2022 at 23:32 | comment | added | Dmytro Taranovsky | @JamesHanson It is (but not every decidable theory is complete). | |
| Aug 17, 2022 at 23:00 | comment | added | Fedor Pakhomov | @DmytroTaranovsky I didn't knew about Hanf work. Indeed, seems to be quite similar to the ideas I was expressing. | |
| Aug 17, 2022 at 22:57 | comment | added | James E Hanson | I'm under the impression that a complete finitely axiomatizable first-order theory is always decidable. Is this not the case? | |
| Aug 17, 2022 at 20:37 | comment | added | Dmytro Taranovsky | @FedorPakhomov I updated the question — you comments led me to learn about Hanf normal form and related constructs. | |
| Aug 17, 2022 at 20:35 | history | edited | Dmytro Taranovsky | CC BY-SA 4.0 |
added related results
|
| Aug 17, 2022 at 15:17 | comment | added | Fedor Pakhomov | Over $T_{n,2}$ we could finitely axiomatize something like computation protocols for a fixed Turing machine (by computation protocol I mean a grid, whose rows are states of the machine; we use four unary functions to walk within the grid). Then from one hand we would be able to express that the machine terminates with accepting state starting from a given input and perhaps under some assumptions about the machine we would be able to decide the resulting theory (the language of the theory should allow essentially to talk only about possible local parts of computations). | |
| Aug 17, 2022 at 15:04 | comment | added | Fedor Pakhomov | I think one could produce the theories of arbitrary high complexities using the computation graph idea. Consider the theory $T_{n,m}$ of $n$ unary predicates and $2m$ unary functions $f_{i,j}$, $i<m$, $j<2$ s.t. $f_{i,j}(x)\ne x\to f_{i,1-j}(f_{i,j}(x))=x$. Observe that over it any $\Pi_2$-formula is equivalent to a $\Sigma_2$-formula and hence any formula is equivalent to a $\Sigma_2$-formula. | |
| Aug 16, 2022 at 19:39 | history | asked | Dmytro Taranovsky | CC BY-SA 4.0 |