All Questions
Tagged with foundations computability-theory
8 questions
1
vote
0
answers
100
views
What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?
The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive ...
- 4,587
2
votes
0
answers
133
views
Higher-order oracle computation of reals and axiom of constructibility
Certain real numbers can be approximated arbitrarily well by computable functions. If we introduce halting oracles, then more real numbers can be "computed", like Chaitin's constant or the ...
- 173
5
votes
0
answers
261
views
Higher order arithmetic, hierarchies and proof theoretic ordinals
I asked this question on MSE some days ago but I have not received any answer so I have decided to post it here.
I would like to consider a generalization of the notation $\Pi$ and $\Sigma$ used for ...
- 161
2
votes
1
answer
317
views
Why are types in type theory unordered collections?
Please excuse my naïveté, I have no higher math education, just a curious observer. In type theories, types are treated as set-like because they're unordered collections. Yet, the putative motive in ...
- 233
16
votes
2
answers
816
views
Can a stochastic Turing machine output a consistent extension of PA with positive probability?
Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...
- 163
2
votes
1
answer
609
views
Would a non-constructible set become constructible if we had oracles of arbitrarily high cardinality for the halting problems of ordinal computers?
I still have trouble to grasp the concept of a non-constructible set, my intuition is that we could "avoid" the non-constructibility of many of them if we assume we have "ordinal computers" extended ...
- 297
9
votes
3
answers
2k
views
What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?
Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...
- 297
6
votes
1
answer
812
views
What can be done with computability logic that previous logic systems can't?
I've been reading a lot about computability logic lately and I'm superficially aware that it unifies classical, intuitionistic and linear logics.
What I'm seeking to know is:
Can computability logic ...
- 69