Impact
~23k
people reached
- 0 posts edited
- 1 helpful flag
- 391 votes cast
Mar
14 |
revised |
“Kolmogorov complexity” of models of computation
few missed items from previous edit |
Mar
12 |
comment |
“Kolmogorov complexity” of models of computation
(Continued from above.) Really I made my definitions too broad, since it's the case where $m$ is actually $\mu$-recursive that I'm interested in, but I am also still interested in the aside question in the second paragraph above. |
Mar
12 |
comment |
“Kolmogorov complexity” of models of computation
The picture in my head was that a model of computation is just a partial function $m$ whose inputs and outputs (where defined) are finite bit strings, $m_k$ is a "weak" interpreter for $m_j$ in $m_i$ if $m_i \circ m_k = m_j$, and an "interpreter" if additionally it is of the form $m_k(s) = int_{i,j} s$ where $int_{i,j}$ is a fixed string and $int_{i,j} s$ denotes concatenation. Then $m$ is Turing-equivalent if it has a (weak) interpreter for every $\mu$-recursive function $m'$, and some such $m'$ also has a weak interpreter for $m$. (Continued below.) |
Mar
12 |
comment |
“Kolmogorov complexity” of models of computation
As always, I'd appreciate comments from any downvoters so that I can try to reword or reformulate the question. |
Mar
12 |
revised |
“Kolmogorov complexity” of models of computation
intuition that binary lambda calculus, Jot should be "absolutely" simple in some sense |
Mar
12 |
asked | “Kolmogorov complexity” of models of computation |
Mar
9 |
comment |
Theories of arithmetic from recursively inseparable sets
I'm not sure if this is "interesting" enough to merit its own question, but what happens if we treat the recursively enumerable list of true statements "the [algorithm / lambda expression / Turing machine / ...] with index i terminates on empty input" as axioms of a theory? Is such a theory useful for anything? How strong is it? |
Mar
7 |
accepted | Theories of arithmetic from recursively inseparable sets |
Mar
7 |
comment |
Theories of arithmetic from recursively inseparable sets
Thanks again. I'm accepting this as pretty much a definitive answer. |
Mar
7 |
comment |
Theories of arithmetic from recursively inseparable sets
Thanks, it sounds like Arslanov's criterion is almost exactly what I was asking for. Regarding your last paragraph, I know that Albert Visser (among others) has done work on proving the incompleteness theorems directly in theories of "syntax" or string concatenation, which in turn I understand to be mutually interpretable with weak theories of arithmetic. So presumably a more general formulation of Arslanov's completeness criterion would apply to these theories as well? |
Mar
5 |
comment |
Theories of arithmetic from recursively inseparable sets
I was originally going to ask that, but then thought: maybe that could fail because one of $X, Y$ is "too small" compared with the other. So it could also be worth considering the situation where the "smaller" set comes from a weaker version of the theory. That's where $T_X$ and $T_Y$ come from. |
Mar
3 |
revised |
Theories of arithmetic from recursively inseparable sets
Sets and theories are supposed to be recursively enumerable |
Mar
3 |
asked | Theories of arithmetic from recursively inseparable sets |
Mar
2 |
comment |
Relationship between first and second incompleteness theorems
@abo I meant in the rather loose sense that your construction takes a theory and forgets one of the comprehension axioms, while Emil's takes a theory and forgets the deduction rules. Maybe there are other choices that would work, which is why I said "semi-canonical", but these do seem like reasonably natural choices. |
Mar
1 |
comment |
Relationship between first and second incompleteness theorems
Alright, thanks for clearing that up. What I particularly like about this answer is that it should be easy to generalize the construction to other axiom systems. And I think Emil's construction, in the comments above, is in some sense the flip side of this: it essentially gives a forgetful functor on theories, since the (Gödel numbers of) provable and unprovable statements of any strong enough theory are recursively inseparable. That would give a semi-canonical construction for both halves of the question, which is about as nice a result as one could hope for. Does that sound about right? |
Mar
1 |
accepted | Relationship between first and second incompleteness theorems |
Mar
1 |
revised |
Relationship between first and second incompleteness theorems
interested in theories which are consistent and recursively enumerable |
Mar
1 |
comment |
Relationship between first and second incompleteness theorems
@Burak Thanks, those were both interesting reads, but you're right that I would consider them "cheating": I'm interested in recursively enumerable theories. I'll add that into the question. |
Mar
1 |
comment |
Relationship between first and second incompleteness theorems
Thanks for this answer. I have a (maybe dumb) question: By my understanding, (PA3) says that every natural number has a successor, (PA2) says that the successor is also a natural number, and (PA4) says that it is unique. But you said the whole point of fpa was that you couldn't say this. Am I missing something here, or should (PA3) be omitted from the axioms? |
Feb
26 |
comment |
Relationship between first and second incompleteness theorems
Thanks. I was dimly aware of the existence of such theories, but unsure whether they could be (essentially) incomplete. I will look at some of Willard's papers. |