Reputation
Next tag badge:
553/400 score
79/80 answers
Badges
19 356 608
Newest
 Nice Answer
Impact
~2.0m people reached

43m
answered Can epsilon-induction be derived from the transitive closure operator?
23h
comment “Clubiness” of projective sets of ordinals
What do we know about the strength of having a single club $C\subseteq\omega_1$ that decides (on a tail) every projectively definable set of countable ordinals?
1d
revised “Clubiness” of projective sets of ordinals
added 44 characters in body
1d
answered “Clubiness” of projective sets of ordinals
1d
comment A question on subsets of $\omega_1$
Under CH we can do this, even if $2^{\omega_1}$ is very large, by labeling the nodes of the tree $2^{<\omega_1}$ with ordinals below $\omega_1$, and then taking all paths through the tree.
1d
comment Complexity of Turing Machine behavior
@JosephO'Rourke That is correct; that is a convention. But meanwhile, nothing prevents us from running a TM on an arbitrary tape. We may regard the entire tape contents as the "input" in this way.
1d
comment Complexity of Turing Machine behavior
@FanZheng, as I said, I think you are correct, for the reasons you say. The blank-tape-detection problem is not decidable, for exactly that reason. Meanwhile, the larger point is that a TM can have simple behavior on some tapes and complicated on others.
1d
comment Complexity of Turing Machine behavior
What Fan says is correct, but nevertheless it is true that one can easily design programs that are trivial on some large class of inputs and complicated on others. I had interpreted your question broadly, as, What kind of hierarchies of complexity are associated with Turing machine programs, and the c.e. degrees are certainly an example of this. But computability theory and complexity theory are filled with numerous hierarchies of complexity, as mentioned also by Bjorn, and any of these would also be such a broad answer.
1d
answered Complexity of Turing Machine behavior
May
1
comment Completing class-sized Fields
It seems to me that much of what is going on here has little to do with the field structure, as opposed to the order structure. The surreal line as an order is not "complete" in the sense that it admits unfilled proper class cuts. There is no class order that completes it, in the sense that No is dense in it and that order has no unfilled proper class cuts. Indeed, I think there is no proper class dense linear order at all that is complete in that sense.
Apr
30
comment Completing class-sized Fields
Have you defined the real closure properly? You say only that $F'$ is an algebraic extension of $F$, and nothing seems to prevent $F=F'$, even when $R(F)$ is larger.
Apr
29
comment Does Con(ZF + Reinhardt) really imply Con(ZFC + I0)?
Your remark is correct, but we don't usually consider $I_0$ without AC.
Apr
29
comment Does Con(ZF + Reinhardt) really imply Con(ZFC + I0)?
Asaf, I believe that the question is whether from ZF+$\kappa$ is Reinhardt, you can get a model of ZFC+$I_0$. So you need to get that embedding inside a ZFC model.
Apr
29
comment Does Con(ZF + Reinhardt) really imply Con(ZFC + I0)?
The ordering of cardinals on Cantor's attic was based on the ZFC version of Reinhardt cardinals, which are inconsistent. Reinhardt had originally proposed his cardinals in ZFC. The vestige of his idea lives on ZF.
Apr
28
comment Non-regular languages fulfilling the Pumping Lemma
Hauke, for your $L_1$ example, if you intend it to have the pumping property, you should use $a^{n+1}b^mc^m$, since if there are no $a$'s, then you can't pump.
Apr
28
comment Non-regular languages fulfilling the Pumping Lemma
@BjørnKjos-Hanssen This question is about languages in an alphabet of size one, and that question isn't. So I don't think it is a duplicate.
Apr
28
revised Non-regular languages fulfilling the Pumping Lemma
correct error: most --> least
Apr
28
comment Non-regular languages fulfilling the Pumping Lemma
I edited the tags.
Apr
28
revised Non-regular languages fulfilling the Pumping Lemma
added 10 characters in body
Apr
28
revised Non-regular languages fulfilling the Pumping Lemma
added 285 characters in body