0
$\begingroup$

Due to its nature, this is a very long question (so please bear with me). To convey the question, while keeping it in manageable length, I have tried to convey the main idea in the question (rather than discuss every detail).

The question is primarily related to a certain definition of admissibility that I read last month. Now what I don't quite understand is how this definition doesn't conflict with a certain construction (to be discussed in rest of the question). Now if the construction is correct, it would seem to imply severe issues. If it is false then I can see three possibilities for how I could have made a mistake: (a) I have misunderstood something very basic, which I am assuming to be correct. (c) I have simply misunderstood/misinterpreted the given definition (relating admissibility and cofinality). (c) There is some (logical) mistake that I keep making over and over when I review the construction.

Due to last paragraph, I will first describe the main assumption and the premise behind the construction (so that if there is a mistake there, the whole question doesn't need to be read). Then I will discuss the main idea.

ASSUMPTIONS:

The main definition on which the question is based is Theorem-9 in this paper1. Quoting that theorem here: "An ordinal $\alpha$ closed under ordinal exponentiation is admissible iff there is no $\alpha$ computable function $g$ that maps some $\beta<\alpha$ cofinally into $\alpha$." For the notion of $\alpha$-computation I am taking the intuitive definitions towards end of section-3 of this paper2.

Meaning that I am assuming once we have settled on a given computational model (which seems to be OTM in-case of paper1), we can define the following notions: (a) $\alpha$-computable --- Collection of all (total) functions (from $\alpha$ to $\alpha$) such that for all inputs $<\alpha$ there is a program that halts in a run-time $<\alpha$. (b) $\alpha$-partial computable --- Collection of all functions (from $\alpha$ to $\alpha$) such that for all inputs $<\alpha$ there is a program that either halts in a run-time $<\alpha$ or it never halts.

Now I do not know precisely what the use "$\alpha$-computable" in theorem-9 quoted in paper1 above means (sorry that's because I understand very little in the paper)? There are only three possibilities: (1) "$\alpha$-computable" means $\alpha$-computable as in paragraph above. (2) "$\alpha$-computable" means $\alpha$-partial computable as in paragraph above. (3) "$\alpha$-computable" means something else entirely.

Possibility-(2) above seems to be false to me, since a simple construction shows that for $\alpha=\omega^{CK}_1$, there is a $\alpha$-partial computable function (in the sense I defined the phrase in second-last pargraph) $f:\omega \rightarrow \alpha$ such that the function has cofinality $\alpha$. Now if possibility-(3) is true that means I have just misunderstood the meaning of the theorem entirely (and then perhaps I should delete the question). I assume possibility-(1) for the rest of the post.

There is one other quite basic thing that I do not know about (this doesn't affect the proceeding construction though). If we say (total) $\alpha$-computable function $g:\beta \rightarrow \alpha$ (with $\beta<\alpha$) then there should be a program whose run-time is $<\alpha$ for all inputs $x$ with $x<\beta$. However, is it also required that for all inputs $x$ in range $\beta \leq x < \alpha$ the run-time is less than $\alpha$? I thought that this was worth asking. (though the answer to this particular point wouldn't affect the construction that follows because the program we describe can be written in a way to satisfy the second condition too ...... for the appropriate ordinal, which will be $q^+$ ...... $q$ here is supposed to be the smallest good admissible value $\geq C$)

MAIN CONSTRUCTION:

Here is the linked document (sorry it isn't in TeX format for now ..... since I will need to learn it to be able to convert) to a fairly detailed description of the argument that I thought of (though one would also want to include/add a run-time analysis, but I didn't do it for now). Basically much of what I have written can also be found in the given link, including much more details. Here I will just try to summarize the main point.

Through-out $C$ will be used to denote supremum of clockable values, meaning the supremum of all halting positions (on empty zero input). Now what I don't get is that why the existence good admissible ordinals $\geq C$ doesn't conflict with theorem-9 (in paper1). In particular, if there are an uncountable number of good admissibles $<\omega_1$ will automatically imply the existence of a good admissible $\geq C$ (since $C$ is countable). By good admissible $\alpha$ I mean that: (a) $\alpha$ is admissible (b) $\alpha^+=|\alpha \mbox{-} recursive|$. The symbol $\alpha^+$ denotes the next admissible value after $\alpha$.

Furthermore, let's denote the $x$-th admissible as $\omega^{CK}_x$ and let's use the notation $x \mapsto \beta_x$ for the mapping in this link --- suitably extended to go beyond $\omega_1$ if needed. Only difference is that in the link we had $\beta_0=\omega^{CK}_1$. Here we define $\beta_i=\omega^{CK}_i$ (for all $i<\omega$).

Now the whole construction is based upon observation of how a program (of one variable) with index $i$ can be categorized when we consider some ordinal value $\alpha$ ....... and how such categories can possibly change as $\alpha$ increases. Note that all values of $\alpha$ need not be tried. For example, in the construction in the linked document all admissible values are tried in increasing order (starting from $\omega^{CK}_0=\omega$).

For any given pair $i$,$\alpha$ we have the following possibilities:(A) For all inputs $<\alpha$, the program (corresponding to index $i$) halts in a time $<\alpha$. (B) There exists some input $<\alpha$ such that the program (corresponding to index $i$) doesn't halt in a time $<\alpha$.

The main thing here is that we want to subdivide the possibility-(A) into three further possibilities. (A1) The given (total) function (from $\alpha$ to $\alpha$) encodes a well-order (on some subset of $\alpha$). (A2) The given (total) function (from $\alpha$ to $\alpha$) encodes a linear-order (on some subset of $\alpha$) but not a well-order. (A3) The given (total) function (from $\alpha$ to $\alpha$) doesn't encode a linear-order (on some subset of $\alpha$).

For both possibilities (A1),(A2) we require the function to return the values in the set $\{0,1,2\}$ for inputs $<\alpha$. This figure-1 shows how the categorisation of a given program changes as we increase the value of $\alpha$. Self-transitions have been omitted (to make the diagram easier to follow).

The encircled states represent the "start state" (so to speak). Observe the omission of transtion: (a) From A2 to A1 (b) From A3 to A1 (c) From A3 to A2. For some specific program with index $i \in \mathbb{N}$, consider two ordinal values $\alpha_1,\alpha_2$ with $\alpha_2>\alpha_1$. If we had possibility (A2) as true for the pair $i,\alpha_1$ then it can never be the case that the possibility (A1) is true for the pair $i,\alpha_2$ [that's because an infinite descent that has been detected once will never be removed]. Similar observations hold for the other transitions that have been excluded.

If we consider this figure-2, we can see that we can divide the our diagram into four "regions". This figure-3 shows the possible movements within the regions. Now here are few crucial points. For any fixed index $i \in \mathbb{N}$, there always exists the notion of an eventual region. For any given $i$, a careful inspection of the previous two linked figures will show that for all $\alpha \geq C$, the program corresponding to index $i$ will never change its region.

Now we can categorise every index $i \in \mathbb{N}$ based upon the eventual region. Write the set of indexes whose eventual regions are 1,2,3,4 respectively as $X_1,X_2,X_3,X_4$. Note that we have $X_1 \cup X_2 \cup X_3 \cup X_4 =\mathbb{N}$.

Now consider the construction which proceeds in stages. Denote $s$ as the (ordinal-valued) variable which starts from value $0$ and only ever increases (it denotes the stage-number). At each stage-$s$, the value $\beta_s$ is checked as to whether its admissible or not (if it isn't, then nothing is done and the next admissible is searched). Obviously such a check can be skipped if $s$ isn't a limit.

Now, in the construction (in the linked document below the "MAIN QUESTION:" heading), we define a set $A_s \subseteq \mathbb{N}$ which satisfies the following the three conditions: (i) As the stage-number increases values can only ever be removed from $A_s$ but never added. That is whenever we have $\alpha_2>\alpha_1$, we get $A_{\alpha_2} \subseteq A_{\alpha_1}$. (ii) $A_s \supseteq X_1$ (for all $s \in Ord$) (iii) $A_s \cap X_2=\phi$ (for all $s \geq C$)

From the first condition in the last paragraph, one can infer (obviously after some reasoning) that $A_s=A_C$ (for all $s \geq C$). And finally, now consider stumbling upon some stage $p \in Ord$ such that $\beta_p$ is both admissible and good. The set $A_p$ doesn't contain any index where the corresponding program encodes a linear-order (on some subset of $p$) but not a well-order (third condition in previous paragraph). Furthermore $A_p$ contains all indexes where the corresponding program encodes a well-order on some some subset of $p$ (second condition in previous paragraph).

Now consider figure-2 which I already linked above. It is not difficult to see that if the possibilities (B) or (A3) occur for some value $\alpha$, then checking them to be true is quite inexpensive in run-time (the run-time should be bounded by a rather simple function over $\alpha$).

So due to the observations in previous two paragraphs, I really don't see why we can't define a $q^+$-computable function $F_{q+}:q^+ \rightarrow q^+$ such that when we restrict the domain of this function to $q^+$ the confinality of the resulting function is $q^+$.


So here is a summarised description of how our program (with one input variable) acts on each stage-$s$ (and as a result calculates the function $F:Ord \rightarrow Ord$, whose restriction to $q^+$ is what we are interested in). The variable $s$ is initially zero and only ever increases (in increments of $1$). At each stage-$s$ the following things are done: (1) Check whether $s$ is a limit or not. (2) Calculate the set $A_s$ (the calculation differs depending on answer to first question). (3) If the answer to first question is "yes" (meaning $s$ is a limit), check whether $\beta_s$ is admissible or not. (4) If the answer to previous question is yes, then check all indexes in $A_s$ in increasing order as to whether they represent a well-order on a subset of $\beta_s$ (or one of the other possibilities). (5) When the previous set is complete, all values $F(x)$ (with $\beta_s \leq x<\beta_s+\omega$) have been settled. For $\beta_s+\omega \leq x<\beta_{s+1}$, the value $F(x)$ is set to zero. This is alongside with simultaneous search for $\beta_{s+1}$.

If on step-(3) it turns out that $\beta_s$ isn't admissible, then the program sets $F(x)$ (with $\beta_s \leq x<\beta_{s+1}$) to $0$ while simultaneously searching for $\beta_{s+1}$.

Finally note that my description has been in "sequential mode" so to speak (something like producing all input/output pairs with a (non-halting) program starting from blank/zero state). But actually the program is just given a single input and it gives an output for any given input). I hope that the reader will see that the conversion from one to another isn't difficult (essentially we will have to add an initial segment at the beginning of our program, along with few minor modifications, to account for this).

FEW REMARKS:

Here is the link to the main document that was also linked before (but posting it here in-case it got lost in the text). It includes a number of details that were not included in this question (because the length of the question is going overboard). One example is that while I discussed the motivation behind the definition of $A_s$, I didn't write a precise definition of it (that can be found in the document ....... in-particular in the "Sketch of the Constuction" section).I might be updating the linked document later-on for improvement. One thing that it might have included but didn't (for now) is more clear statements regarding run-time of the program (for a given input). Another thing might be adding detailed implementation (thought this wouldn't have any effect on the correctness (or lack of it) of the construction).

I have also been thinking about an analogous (but different) construction from point of view of clocking positions instead of cofinality. A (very) tentative version of that is here. This linked document is likely to be substantially revised in next few weeks though (for improvement). But anyway, this isn't directly relevant to the question.

Concluding, here is the question in brief. Assuming what I described in "ASSUMPTIONS:" section holds, then why doesn't the definition of admissibility (based on cofinality of infinite-time functions) doesn't conflict with existence of a good admissible $\geq C$ (countable will be very convenient but the question would still remain for uncountable one)?

$\endgroup$
  • $\begingroup$ Incidentally, while I think the question is interesting, it's also so long as to be virtually unreadable. At the very least you should remove all unnecessary exposition (e.g. the paragraph including the paranthetical remark "this doesn't affect the proceeding construction though"). $\endgroup$ – Noah Schweber Aug 14 at 9:59
  • $\begingroup$ Is " I really don't see why we can't define a $q^+$-computable function $F_{q+}:q^+ \rightarrow q^+$ such that when we restrict the domain of this function to $q^+$ the confinality of the resulting function is $q^+$." a typo? I think you want to restrict the domain to $q$, not $q^+$ (there are trivially cofinal computable maps from $q^+$ to $q^+$). $\endgroup$ – Noah Schweber Aug 14 at 10:09
  • $\begingroup$ @NoahSchweber Thanks. Yes, it's a typo. What I meant to write was: "I really don't see why we can't define a $q^+$-computable function $F_{q^+}:{q^+} \rightarrow {q^+}$ such that when we restrict the domain of this function to $q+\omega$ the confinality of the resulting function is $q^+$". I will correct this upon edit (just editing for one word or phrase seems a bit much to me due to bumping on frontpage). Also, regarding that particular paragraph, I was hoping someone would clarify that point. But anyway, I will try to cut-down the remarks (that don't relate directly to question) upon edit. $\endgroup$ – SSequence Aug 14 at 10:26
  • $\begingroup$ Can you say in words what your machine is trying to do? E.g. are you trying to sum up all the admissibles below $q$? Are you trying to sum up all the $q$-recursive well-orderings (where more-or-less at stage $a$ you add $\Phi_a^q$ if that's a well-ordering, and don't do anything otherwise)? $\endgroup$ – Noah Schweber Aug 14 at 10:28
  • $\begingroup$ Firstly, one thing to note is that $q$ doesn't have any special status (just happens to "occur"). Now, for any given input $x \in Ord$, first we find the value $r$ such that $\beta_r \leq x < \beta_{r+1}$. Then it is tested whether $\beta_r$ is an admissible or not. If we had $\beta_r=q$, then the test will return true. After this, the program proceeds in stages with the stage-number $s$ taking all values from $s:=0$ to $s:=r$ (this is in section-8 of linked document). At each stage-$s$, (1) It is checked whether $s$ is a limit or not. (2) The set $A_s$ is calculated. (continued) $\endgroup$ – SSequence Aug 14 at 10:37

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.