Robin Saunders
Reputation
1,163
Next privilege 2,000 Rep.
 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.