# Questions tagged [ordinal-computability]

The ordinal-computability tag has no usage guidance.

The ordinal-computability tag has no usage guidance.

16
questions

3
votes

0
answers

219
views

An ordinal $\alpha$ is said to be computable if there is a computable relation on a subset of integers that is well-ordered and its order type equals $\alpha$.
But let's consider well-founded trees on ...

4
votes

1
answer

209
views

Does there exist a function $f$ that satisfies all of the following three properties?
The function converts an arbitrarily large (empty, finite, countably/uncountably infinite) set of ordinals to a ...

0
votes

1
answer

129
views

By the Tennenbaum's theorem,
there are no non-standard countable models of
Peano Arithmetic that are computable using Turing machines. What about models of infinitary computation like infinite time ...

2
votes

1
answer

134
views

Is there a theory about using α-recursion to compute ordinals?
For example, consider α-recursive well orders on α, what is the supreme of their order type? Is it the next admissible ordinal after α? ...

1
vote

2
answers

796
views

In their arXiv preprint, "Infinite Time Turing Machines" (arXiv:math/9808093v1 [math.LO] 21 Aug 1998) Hamkins and Lewis state the Lost Melody Theorem for ITTM's as follows:
Lost Melody ...

5
votes

1
answer

196
views

This is a somewhat open-ended question, so let me motivate it a little.
One of the first results in the study of Ordinal Turing Machines includes the following computational characterization of $L$ by ...

5
votes

0
answers

211
views

Gostanian's paper "The next admissible ordinal" (see https://www.sciencedirect.com/science/article/pii/0003484379900251 ), is concerned with the supremum of the $\alpha$-recursive ordinals for various ...

9
votes

1
answer

640
views

It's known, for example in the answer to this question: Is there a computable model of ZFC? that ZFC has no computable model. My questions is: is there a model of ZFC for which the order relation on ...

2
votes

0
answers

58
views

As I understand, there can't be any (total) OTM computable function (in traditional input/output sense) $f:Ord \rightarrow Ord$ such that $f(x)$ gives an upper-bound on the length of the $x$-th gap.
...

2
votes

2
answers

440
views

$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.
For a ...

3
votes

0
answers

52
views

I have been quite hesitant to post this question. Due to the highly general nature of the question there is a possibility of a trivial answer. At a first glance at least, one gets the feeling that ...

4
votes

0
answers

182
views

Consider the following statement (which follows easily from various results found in the literature):
(†) There exists a primitive recursive (“p.r.”) relation $T$ on the ordinals such that, if $(...

8
votes

2
answers

494
views

One of the nice features of the first admissible ordinal after $\omega$, i.e. $\omega_1^{CK}$, is that it is the collection of ordinals whose order type is that of a computable well-ordering on $\...

2
votes

0
answers

130
views

Does Koepke's notion of ordinal computability admit an analogue of the Kleene $T$-predicate? If so, is the existence of such a $T$-predicate independent of $ZFC$? Also, if one assumes the existence ...

18
votes

2
answers

2k
views

Let $\mathbf{A}$ be an admissible set (possibly with urelements). I am wondering if there is some good notion of "primitive recursive arithmetic" relative to $\mathbf{A}$. More precisely, I would like ...

3
votes

1
answer

382
views

In his doctoral thesis titled "Three models of ordinal computability", Benjamin Seyfferth proved the following theorems:
i) A set $\mathtt A$ of reals is Ordinal Turing Machine-enumerable if and only ...