Skip to main content
Wojowu's user avatar
Wojowu's user avatar
Wojowu's user avatar
Wojowu
  • Member for 11 years, 11 months
  • Last seen this week
comment
Relation between Turing degrees and functions computable with them
Interesting, so there are degrees such that some function of this degree isn't bounded by computable function, but there is no dominant function, and e.g. low c.e. sets have this property.
comment
Relation between Turing degrees and functions computable with them
So let me get this straight - if there is $A$-computable function which isn't bounded by any computable function, then degree of $A$ is hyperimmune, and "most" of degrees are hyperimmune, in particular all recursively enumerable degrees are hyperimmune. Is this right?
revised
Loading…
Loading…
revised
Loading…
comment
Peano arithmetic vs. fast-growing hierarchy with pathological fundamental sequences
@JoelDavidHamkins Do you think we could make a similar construction, so that we also have, for all ordinals $\alpha<\beta\leq\varepsilon_0$, that $F_\alpha$ is eventually outgrown by $F_\beta$? (that is, for sufficiently large $n$, $F_\alpha(n)<F_\beta(n)$? Your construction satisfies it for all ordinals other than $\varepsilon_0$ itself.
comment
Peano arithmetic vs. fast-growing hierarchy with pathological fundamental sequences
This is the best answer I could hope for! It's not only extremely simple, but modifies only very little number of fundamental sequences. Thanks!
comment
A question on the size of an admissible ordinal
Isn't this by definition $\Sigma_3$-admissible ordinal?
revised
Loading…
Loading…
comment
Dubins car shortest paths: Decidable?
How is the description of these polygons given for the algorithm?
comment
Are there sets which are computable in one model, but uncomputable in another?
Thanks, Joel, this is exactly what I was looking for! I have yet to read the paper, but I'm sure many interesting results are given there.
awarded
comment
Are there sets which are computable in one model, but uncomputable in another?
@LiangYu I don't see why this should be a contradiction. It can be the case that the subset of $\Bbb N^U$ becomes finite.
Loading…
revised
Loading…
revised
Loading…
1
149 150
151
152 153
155