0
$\begingroup$

Since there seems to be at least some interest in the question I asked, I will leave the previous version of question as it is (instead of deletion) and just briefly state the actual current question that I had in mind.

Current Main Question: Based on the question linked in the comments below, there are countable admissible values $\alpha$ such that $\alpha^+$ is greater than supremum of $\alpha$-computable well-orderings of $\alpha$. For a given $\alpha$ let's denote this, somewhat generically, by $X_\alpha$.

My question, if I be honest about it, results from being highly skeptical about how this could actually happen. What I can't see is how $\alpha$ being very big itself could affect how $X_\alpha$ behaves.

But I understand what I wrote in previous paragraph is too subjective from mathematical viewpoint. So here is a precise mathematical question: " For any given value countable admissible value $\alpha$ (entirely of our own choice) for which $X_\alpha<\alpha^+$, is there a known algorithm (which can be reasonably discerned/analyzed) that gives an upper-bound on $X_\alpha$."

Note that the use of word algorithm here is not far-off from standard usage. To be precise, what I mean is the description of an ordinary finite program (computing a function $\mathbb{N}^2$ to $\{0,1\}$) which, given any possible well-order relation for $\alpha$ given to us as oracle, would always give us some well-order relation that would correspond to a value greater than $X_\alpha$. Also, note that I didn't mention the value of $X_\alpha$ specifically at all. All that is required is any upper-bound on $X_\alpha$.

As for the phrase "algorithm which can be reasonably analyzed", perhaps this is somewhat blurry (mathematically), but what I am trying to say is that it should at least be at the same level of analysis as when proof-theorists give notation systems for recursive values. Perhaps this isn't precise enough, but that's the only analogy I could think of. I hope this question is making some sense.


Previous Question: Assume a sufficiently powerful infinite program (ordinal time, ordinal variable values etc.). For the purposes of this question, we want to have one input variable. Suppose the run time of the program on some input $x \in Ord$ is $T(x)$. $T(x)$ is well-defined whenever the program halts for a given input value $x$.

The question is easy to state. The idea is that we are concerned with inputs $x$ where $0 \leq x <\omega^{CK}_1$. The main thing we are concerned with here is the running time (for the input range in previous sentence). Further, we are not concerned at all with the case when the input is greater than or equal to $\omega^{CK}_1$ (whatever the computations do for this range is not our concern). We want to impose the condition that summing the values $T(i)$ (from $i=0$ to $i<\omega^{CK}_1$) should exactly yield $\omega^{CK}_1$. In other words, we don't want our computations running too long.

Now we want to consider the well-order relations for well-orders of $\omega^{CK}_1$ with some order-type $\alpha$. Here obviously $\alpha$ is meant to be greater than or equal to $\omega^{CK}_1$. Now consider a suitably encoded form of these relations (for example, using some type of slight generalisation of cantor pairing function) so they can be thought of as functions from $\omega^{CK}_1$ to $\{0,1\}$. If this function can be computed in total time exactly equal to $\omega^{CK}_1$ (as described in previous paragraph) then we say that the value $\alpha$ can be written in limited time (for purpose of this question).

(Q1) The question is that is the following true or false: "There are arbitrarily large values $\alpha$ below $\omega^{CK}_2$ which can be printed/written in the manner described above."

(Q2) What if we pose an analogous question for $\omega^{CK}_X$ (countable $X$)? That is, we consider the input range $0 \leq x <\omega^{CK}_X$. We similarly require the sum of running times (for the give input range) to be exactly $\omega^{CK}_X$. Furthermore we consider the well-orders of $\omega^{CK}_X$ (instead of well-orders of $\omega^{CK}_1$).

(Q3) In case the answer to both (Q1) and (Q2) happens to be positive, then would there be a specific reason why all the steps would go through for countable values $X$, but fail for $\omega_1$?

$\endgroup$
  • $\begingroup$ In case it wasn't quite clear, ORM/OTM computational models (and also possibly some small variations on them) should be fine for this question. $\endgroup$ – SSequence Mar 14 at 7:46
  • $\begingroup$ What's the paper that has the solution? $\endgroup$ – Dan Turetsky Mar 15 at 3:12
  • $\begingroup$ @DanTuretsky "Post’s Problem for ordinal register machines: an explicit approach" by Joel David Hamkins, Russell G. Miller .............. Towards the end the authors seem to remark about notions such as $\alpha$-RM's and $\alpha$-TM's where the run time is limited to less than $\alpha$ on inputs less than $\alpha$. I placed the same condition in question (and totality ..... that is relaxed there). Finally " for admissible $\alpha$, the $\alpha$-TM's and the $\alpha$-RM's both compute precisely the $\alpha$-partial recursive functions, as defined in $\alpha$-recursion theory. " $\endgroup$ – SSequence Mar 15 at 4:27
  • $\begingroup$ Combining it with the answer to mathoverflow.net/questions/277343, it seems answer to (Q2) is supposed to be negative. $\endgroup$ – SSequence Mar 15 at 4:28
  • $\begingroup$ Instead of deleting this question, I am posting the current question I have in mind. $\endgroup$ – SSequence Mar 15 at 8:18

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.