Carl Mummert

Marshall University

science.marshall.edu/mummertc

Age: 36

I work in mathematical logic. My main areas of interest are arithmetic, reverse mathematics, computability, and proof theory.
2d
revised Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity
deleted 491 characters in body
2d
comment Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity
You're right - I'm going to delete that part of the answer. We agree that it should say that $C(n) \leq C(n|l(n)) + C(l(n)) + f(n)$ for an appropriate and unbounded $f(n)$. Apparently I was trying too hard to salvage the argument in the text, and began to work as if their inequality was actually right. But your version of the argument also gives the right conclusion.
2d
comment Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity
I don't see it either, immediately. There should be an additional term, unless I am missing some special assumption. But the overall conclusion of the argument seems to be sound, which is what I decided I could verify in the answer.
2d
answered Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity
2d
comment Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity
As a separate point, questions like this are certainly unrelated to descriptive set theory; they are not really related to computational complexity unless we consider some sort of resource-bounded Kolmogorov complexity; and Kolmogorov complexity is not only a "computer science" topic (no more than computability theory in general), so I have edited the tags of the question.
2d
revised Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity
edited tags
2d
comment Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity
Are you certain this is plain complexity, rather than prefix-free complexity?
Jul
23
comment Proof that $\sqrt6 - \sqrt2 - \sqrt3$ is irrational.
There is another path from $\sqrt{3} - r\sqrt{2} = r+1 \in \mathbb{Q}$, using the fact that $\sqrt{3} \not \in \mathbb{Q}[\sqrt{2}]$.
Jul
23
comment Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often
You are right; the authors must only mean that the difference is bounded.
Jul
23
comment expressing inclusive OR using exclusive OR.
It is not clear what you are asking. The question states you have conjunction and negation. Just use those and ignore the XOR entirely.
Jul
23
comment expressing inclusive OR using exclusive OR.
If you have negation and conjunction, you don't need XOR at all! Negation and conjunction are a complete set of connectives - they can be used to express every connective.
Jul
23
answered Examples of logical possibility
Jul
23
revised Why can't you prove the law of the excluded middle in intuitionistic logic (for layman)?
added 12 characters in body
Jul
23
answered Why can't you prove the law of the excluded middle in intuitionistic logic (for layman)?
Jul
21
answered Is there much of difference between set models and class models?
Jul
20
comment Multiple accounts, a wide open door for breaking rules?
It seems that the suspension on the user in question has been extended to November 23, 2015.
Jun
23
awarded Autobiographer
Jun
23
awarded Yearling
Jun
21
awarded Enlightened
Jun
21
awarded Nice Answer
1 2 3 4 5