Questions tagged [ordinal-computability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
0 answers
123 views

Logical properties of realizability (topoi or McCarty models) defined by alpha-recursion on admissible ordinals

Setup: Let $\alpha$ be an admissible ordinal (viꝫ., one such that $L_\alpha$ is a model of Kripke-Platek set theory), identified as usual with the set of ordinals $<\alpha$. Then there is a ...
Gro-Tsen's user avatar
  • 29.6k
3 votes
1 answer
489 views

Are all constructible from below sets parameter free definable?

Lets take the intersection of the theory of $L_{\omega_1^{CK}}$ and $\sf ZF + [V=L]$, this is equivalent to the theory of constructability from below + limit stages. Can this theory prove the ...
Zuhair Al-Johar's user avatar
1 vote
0 answers
36 views

Single parameter programs and halting supremums

Let's first define a function $H:\mathrm{Ord} \rightarrow \mathrm{Ord}$. Suppose we are given some ordinal $\alpha$ and we want to find $H(\alpha)$. We define $H(\alpha)$ as the supremum of halting ...
SSequence's user avatar
  • 851
3 votes
0 answers
308 views

An alternative definition of computable ordinals

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 ...
Dan's user avatar
  • 1,288
4 votes
1 answer
252 views

Existence of a particular function that maps an arbitrary set of ordinals to a single ordinal

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 ...
lyrically wicked's user avatar
0 votes
1 answer
201 views

Is there a non-standard model of PA computable with infinitary computation?

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 ...
Jozef Mikušinec's user avatar
2 votes
1 answer
191 views

Ordinal notations in α-recursion theory

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 α? ...
Reflecting_Ordinal's user avatar
1 vote
2 answers
822 views

Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not?

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 ...
Thomas Benjamin's user avatar
5 votes
1 answer
224 views

Can there be a computational characterization of HOD?

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 ...
Jason Zesheng Chen's user avatar
6 votes
0 answers
279 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 ...
M Carl's user avatar
  • 335
9 votes
1 answer
680 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 ...
Raul Gomez's user avatar
2 votes
0 answers
61 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. ...
SSequence's user avatar
  • 851
2 votes
2 answers
512 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 ...
Christopher King's user avatar
3 votes
0 answers
58 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 ...
SSequence's user avatar
  • 851
4 votes
0 answers
189 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 $(...
Gro-Tsen's user avatar
  • 29.6k
9 votes
2 answers
604 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 $\...
Nate Ackerman's user avatar
2 votes
0 answers
132 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 ...
Thomas Benjamin's user avatar
19 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 ...
Jacob Lurie's user avatar
  • 17.5k
4 votes
1 answer
422 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 ...
Thomas Benjamin's user avatar