Carl Mummert

Marshall University

science.marshall.edu/mummertc

Age: 35

I work in mathematical logic. My main areas of interest are arithmetic, reverse mathematics, computability, and proof theory.
2h
comment How many recursively definable groups are there on $\mathbb{N}$?
The answer seems perfectly clear to me - if you're in a position to ask the question, you can certainly fill in the routine details.
18h
comment People should not hurry to solve a problem when OP has not demonstrated efforts
I tend to downvote and/or vote to close "puzzles" - in my experience this site is intended for mathematical questions that users have encountered, not for mathematical questions that users have intentionally concocted to test others.
1d
reviewed Close prove the countable additive of measure theorem
1d
comment Uncomputability of subset relation
Those theorems sound almost right, but for the index version you need a computable $f$ and the ability to compute, given a finite initial segment of $f$, an index for an extension of that segment that is not in $D$. That extra restriction holds in all the examples I listed. In my mind, the proof of the index version is just an "effectivization" of the proof of the oracle version, vaguely analogous to another common type of "effectivization": taking a boldface result in descriptive set theory and making it into a lightface result. @Henning
1d
reviewed Close complex variable integral using residue theorem
1d
comment Uncomputability of subset relation
The systematic method is that there is a type of strategy to solve the oracle case: you pretend to construct an oracle for one object $\alpha$, which is computable, but as soon as the purported decision procedure says that you are constructing something with the appropriate property of $\alpha$, you switch to constructing an oracle for a different object $\beta$, also computable, whose oracle agrees with a sufficiently long initial segment of the oracle for $\alpha$. This method, which is very common, can almost always be adapted to work with indices exactly as above. @Henning
1d
comment Uncomputability of subset relation
Just one more, which involves fewer prerequisites but is more trivial. (1) it is not computable, given an oracle for a subset of $\mathbb{N}$, to tell whether the set is finite (2) it is not computable, given an index for a subset of $\mathbb{N}$, to tell whether the set is finite
1d
revised Uncomputability of subset relation
added 38 characters in body
1d
comment Uncomputability of subset relation
Similarly: (1) it is not computable, given an oracle for a group operation on $\mathbb{N}$, to tell whether the group determined by the operation is cyclic (2) it is not computable, given an index for a group operation on $\mathbb{N}$, to tell whether the group determined by the operation is cyclic. Again (2) follows immediately from the appropriate strategy to solve (1).
1d
comment Uncomputability of subset relation
I had built $i_1$ into the construction itself to avoid being too general, but now I have edited it to make $i_1$ explicit. To see that this is a general technique, consider these problems: (1) it is not computable, given an oracle for a Cauchy sequence of rationals, to tell whether the sequence converges to $0$. (2) it is not computable, given an index for a Cauchy sequence of rationals, to tell whether the sequence converges to $0$. There is a direct strategy to prove (1), and since that strategy is computable, it can be adapted in exactly the same way as my answer to solve (2). @Henning
1d
revised Uncomputability of subset relation
added 144 characters in body
1d
revised Uncomputability of subset relation
added 2667 characters in body
1d
comment Uncomputability of subset relation
@Henning: I added an explanation. I wanted to write this out because it is rally a fundamental collection of techniques for working with computability.
1d
revised Uncomputability of subset relation
added 2667 characters in body
1d
comment How to prove this limit in $\ell_1$
This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level.
1d
comment Is $U/U(w) = U \cap w U^- w^{-1}$?
What are your own thoughts on the problem? For some time now, questions that only state a problem, with no context, have been discouraged on MSE.
1d
comment canonical divisor and self-intersection number
What are your own thoughts about the problem?
1d
answered Uncomputability of subset relation
1d
comment Uncomputability of subset relation
The usual way for a Turing machine to take an infinite set as an input is to use the infinite set as an oracle. It's very common for machines to "literally" take infinite sets as inputs in this way. That is how I would interpret the original question, although it is not clear exactly what was intended. But, for questions like this, there will be parallel undecidability results if (a) we focus only on computable sets, represented by their indices, or if (b) we focus on arbitrary sets provided as oracles. (@Henning Makholm)
1d
comment Index Set & R.E Set & Primitive R.E
What are your own thoughts on the question? Why do you think it is false (indeed, it is not false...)
1 2 3 4 5