All Questions
Tagged with computability-theory ordinal-numbers
38 questions
4
votes
2
answers
489
views
Mapping between Notations
$\DeclareMathOperator{\address}{address}$
As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\address:p \rightarrow \Bbb{N}$ and assumed to be ...
- 6,367
17
votes
7
answers
2k
views
Finding the largest integer describable with a string of symbols of predefined length
(This question is motivated by the reading of the article Large numbers and unprovable theorems by Joel Spencer, which can be found at http://mathdl.maa.org/images/upload_library/22/Ford/Spencer669-...
- 328
4
votes
3
answers
491
views
Ordinal numbers reachable by primitive recursive ordinal functions in omega
$ \def \PRo {{\mathcal { PR } _ \omega}} $
The class of primitive recursive ordinal functions in the constant omega function (henceforth denoted by $ \PRo $) are defined by Jensen and Karp (1971) as ...
16
votes
1
answer
750
views
Is ordinal arithmetic more complicated than classical arithmetic?
Consider the first-order language $\mathcal{L}_{\text{OA}}:=(+,\cdot,0,1)$; in this language, we can formulate statements of ordinal arithmetic. Clearly, the theory $T_{\text{OA}}$ of $(\text{On},+,\...
- 47.1k
1
vote
0
answers
123
views
Is possibile to define transfinite sum and product recursively? [closed]
On mathstackexchange a few days ago I published the following question where I asked about "transfinite" sum and products but actually nobody answered or gave an opinion with a comment: thus ...
6
votes
1
answer
571
views
Parameter-free effective cardinals
In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined.
I'm curious about its little variation, parameter-free ...
- 2,031
0
votes
1
answer
137
views
Is there a canonical mapping between countable transfinite ordinals and $\omega$? What about recursive ordinals?
Consider $\omega^2$. We can build a simple bijection between the ordinal and $\omega$ similarly to how the bijection between $\mathbb{Q}$ and $\mathbb{N}$ can be built.
I was wondering if there is a ...
- 21.2k
5
votes
1
answer
487
views
How to solve this exercise about large countable ordinals?
In this note (Notes on Higher Type ITTM-recursion, 2021) written by Philip Welch, I'm trying to solve exercise 3.5(i), but I don't know how to solve it.
The problem is: assume that $L_{\gamma_0}<_{...
- 2,031
7
votes
1
answer
443
views
Gaps in the ordinals writable by Ordinal Turing Machines with a single countable parameter
Let $W(\alpha)$ denote the set of all (countable) ordinals writable by Ordinal Turing Machines with a single (countable) parameter $\alpha$, i.e. each computation starts with a single ($\alpha$-th) ...
- 236k
1
vote
1
answer
287
views
How large is the smallest ordinal larger than any “minimal ordinal parameter” for any pair of an Ordinal Turing Machine and a real?
In this question, the notation $P^x(\alpha)$ denotes a situation where a particular OTM-program $P$ performs a computation on input $x$ with an ordinal parameter $\alpha$, assuming that $x$ is written ...
- 3,042
2
votes
1
answer
204
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 α? ...
- 2,031
3
votes
0
answers
368
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 ...
- 2,031
4
votes
0
answers
253
views
Is this recursion theoretic analogue of a criterion of weakly compact cardinal accurate?
Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
- 2,031
2
votes
0
answers
235
views
The supremum of ordinals eventually writable by Ordinal Turing Machines with an oracle for the class of stabilization ordinals
This question is based on the assumption that all computations start with no ordinal parameters (i.e. the input is empty).
The term “stabilization time of a machine” for this question implies the ...
- 959
4
votes
1
answer
268
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 ...
- 17.7k
4
votes
3
answers
495
views
How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?
Given a fixed enumeration of Infinite Time Turing Machines (ITTMs), let $M_i(x)$ denote a computation of an $i$-th ITTM, assuming that the input $x$ is a real (an infinite binary sequence).
Then the ...
- 1
4
votes
1
answer
469
views
How large are the stabilization times of Ordinal Turing Machines with an oracle for the transfinite initial ordinals?
This question is based on the assumption that $V \ne L$ and we have $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing ...
- 959
4
votes
3
answers
403
views
Countably infinite sets of ordinals as parameters for Ordinal Turing Machines
Let $A$ and $B$ denote two countably infinite sets of ordinals.
Let $W_A$ denote the supremum of ordinals writable by Ordinal Turing Machines with the set $A$ given as the source of parameters. That ...
- 4,839
4
votes
1
answer
227
views
Is there a real $x$ which is eventually writable from an ordinal parameter $\alpha < \omega_1$, but not from $\omega_1$?
According to Lemma 3.14 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”, there is a real $x$ in $L$ which is recognizable from some ordinal $\alpha$...
- 881
4
votes
1
answer
337
views
How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?
This question implies that we have fixed: (i) a particular enumeration of Ordinal Turing machines; (ii) a particular way to encode an ordinal by an infinite binary sequence.
The class of $[1]$-...
- 881
5
votes
0
answers
262
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 ...
- 3,065
10
votes
2
answers
595
views
Transfinite algorithms
The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
- 211
9
votes
1
answer
442
views
First order axioms for primitive recursion in Takeuti's theory of ordinal numbers
In this article, Takeuti has introduced a theory of ordinal numbers, which in his own words, is intended to be a first order theory:
The theory of ordinal numbers we are to develop is based on the ...
- 346
9
votes
1
answer
610
views
Does every cofinal branch through Kleene's O compute true arithmetic?
My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides
ordinal denotations for any ...
- 3,073
5
votes
1
answer
193
views
How far does this restricted definition on $\mathcal{O}$ goes?
$\mathcal{O}$ notation describes an onto function $f:\mathcal{O} \rightarrow \omega_{CK}$. In calculating all values $n \in \mathbb{N}$ such that $f(n)=\alpha$, when $\alpha$ is a limit, all indexes $...
- 3,073
5
votes
1
answer
749
views
Which ordinal is larger, the supremum of ordinals writable by iterated Infinite Time Turing Machines or the smallest $\Sigma_2^1$-reflecting ordinal?
The ordinal $\tau_1$ corresponds to $\lambda^{\textit{it}}$ (the supremum of all ordinals writable by iterated ITTMs) — see Definition 3.1 in the paper “ITTMs with Feedback” [Robert S. Lubarsky]. ...
- 4,839
8
votes
0
answers
287
views
Natural examples of recursive pseudowellorderings
Question: What are some natural examples of recursive pseudowellorderings?
By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an ...
- 881
6
votes
0
answers
303
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 ...
- 365
9
votes
1
answer
711
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 ...
- 21.2k
4
votes
0
answers
210
views
Upper bound on ranks of well-founded trees in $SKI\Omega$ calculus
All ideas explained below are due to A.P.Goucher, and defined here.
First of all, $SKI\Omega$ calculus is an extension of standard SKI calculus, with additional type of combinator, called oracle ...
4
votes
2
answers
591
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 ...
- 4,201
4
votes
0
answers
199
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 $(...
- 32.5k
13
votes
1
answer
650
views
About primitively recursively recognizable ordinals
Preliminary: I believe the notion of primitive recursive functions on ordinals is standard and unproblematic (the main difference with the finite case is that one needs to introduce a $\sup$ or $\...
- 4,839
4
votes
1
answer
218
views
Are two recursive well-orderings with the same order type recursively isomorphic?
Let $\leq_1$ and $\leq_2$ be recursive well-orderings of $\omega$ that have the same order type. Is there necessarily a recursive bijection $f$ such that $f(x)\leq_1f(y)\iff x\leq_2y$? If this does ...
- 236k
5
votes
1
answer
627
views
On a characterization of the recursively inaccessible ordinals
For a given set of numbers $A$, let $O^A$ be the hyperjump of $A$. It is possible to iterate inductively the hyperjump of a set, through the computable ordinals, in a way that the $\alpha$-th ...
CommunityBot
- 1
12
votes
1
answer
834
views
Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?
Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
- 21.2k
27
votes
1
answer
2k
views
Why isn't this a computable description of the ordinal of ZF?
In a previous MO question, I was told by several commenters that
(a) it's known that there exists a computable ordinal $\alpha_{ZF}$ that "encodes the strength of ZF set theory" (i.e., a least ...
CommunityBot
- 1
17
votes
1
answer
1k
views
Looking for a copy of Leo Harrington's unpublished notes on the first nonprojectible ordinal
Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how widely they were ...
CommunityBot
- 1