# Questions tagged [ordinal-computability]

The ordinal-computability tag has no usage guidance.

11
questions

**0**

votes

**0**answers

43 views

### Regarding equality of screens (beginning of successive regions)

This question is about a more specific notion than the previous question I asked. Let's briefly discuss this notion first. In the linked question, "eventually markable" values were discussed....

**5**

votes

**0**answers

154 views

### Weaker versions of Gandy ordinals

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

580 views

### Computable models of the ordinal numbers

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

57 views

### Length of Gaps in Clockable Values

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

293 views

### Connection between countable ordinals and Turing degrees

$\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

41 views

### Trace-Recursive Functions and Natural/Unnatural Operations

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

153 views

### On the proof of a normal form theorem for ordinal (primitive) recursion

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

338 views

### Order type of $\alpha$-computable well-orderings

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

124 views

### A question regarding an analogue of the Kleene $T$-predicate for Koepke's ordinal computability

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 ...

**17**

votes

**2**answers

2k views

### Analogues of Primitive Recursive Functions

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

327 views

### At what level of the analytic hierarchy do Cohen reals lie?

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 ...