0
$\begingroup$

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. One thing with markable values was that the "position" of marker (or alternatively, some chosen ordinal variable) could be set to a lower ordinal. We can define the notion of "eventually pointable values" where the position of marker can never be decreased (during the whole course of computation). Further the position can only be increased in increments of $1$, and in continuous manner on limit number of increments. Alternatively, if we had chosen some ordinal variable (say $y$) then that variable will only have the access to command $y\mathrel{:=}y+1$. Through-out in the question, $y_e(t)$ denotes the (ordinal) value of the variable at time $t$. The value $Y_e$ is the ordinal value to which the program with index $e$ eventually points (this value is undefined if the variable $y$ never stabilizes to becomes fixed).

$\newcommand\screen{\mathit{screen}}\newcommand\lessequals{\mathit{lessequals}}$Now we can define a function $\screen:\mathrm{Ord} \rightarrow \mathbb{R}$. For any ordinal $t$, the value $\screen(t)$ is supposed to be a real number encoding the function $\lessequals:\mathbb{N}^2 \rightarrow \{0,1\}$ which is defined as follow (here $i,j \in \mathbb{N}$): (i) $\lessequals(i,j)=1$ iff $y_i(t) \leq y_j(t)$ (ii) $\lessequals(i,j)=0$ iff $y_i(t) > y_j(t)$. There is one further notation $p_i$ (with $i \in \mathrm{Ord}$) that needs to be defined before moving to the question. Define $p_0=0$. Given a value $p_i$, we define $p_{i+1}$ to be the supremum of times when all those programs $e$ (that don't stabilize or for which $Y_e > p_i$) finally get the value of their (pointing) variable to $p_i+1$. To put it in symbolic form: $p_{i+1}=\operatorname{sup}\{t \in \mathrm{Ord} \,\,|\,\, \exists e \in \mathbb{N} \,\, (y_e(t)=p_i \, \wedge \,y_e(t+1)=p_i+1) \}$. For a limit value $j$, we define $p_j$ to be the supremum of all the $p_i$'s with $i<j$.

Finally let $R_i$ denote the interval $[p_i,p_{i+1})$. Now define a "region" $R_i$ to be "unpointable/empty" if there is no program $e$ such that $p_i \leq Y_e < p_{i+1}$. Otherwise call $R_i$ a "pointable" region. Here is the question:

For every countable ordinal $i<\omega^L_1$, if $R_i$ is an empty region then it can be shown that $\screen(p_i)=\screen(p_{i+1})$. What is the case for $i \geq \omega^L_1$?

Some Context for the Question

$\newcommand\char{\mathit{char}}$The question, as stated, might look a bit unmotivated. Below constructibiliy is assumed. Define $S=\{\screen(t)\mathrel|t \in \mathrm{Ord}\}$ . Further, it is clear that every screen $s \in S$ has a unqiue ordinal $\alpha < \omega_1$ associated with it. Let's write it as $\char(s)$. Here are several facts about pointable values: (1) The supremum of stabilization times for markable and pointable values is the same. (2) There are gaps in eventually pointable value. They exist even below $\eta_0$ (the supremum of ordinals eventually markable in countable time). (3) Denoting $\mathcal{S}$ to be the supremum of stabilization times we have $\char(\screen(\mathcal{S}))=\eta+1$. (4) Suppose $R_i$ is a pointable region. Then $p_i$ is eventually pointable.

Now we want to define a function $g:\mathrm{Ord} \rightarrow \omega_1$ ("firing count"). The value $g(i)$ is defined as the "number of times" (ordinal count) when some program moves/changes its pointing variable from $p_i$ to $p_i+1$. (1) For all ordinals $i$, $p_i$ is a limit. (2) For all ordinals $i$, $g(i)$ is a limit. (3) For all ordinals $i$, we have $p_{\omega_{\alpha}}=\omega_{\alpha}$. (4) ("Arrival") Let $i$ be any arbitary ordinal and let $A$ be the set of all program indexes $e$ that either don't stabilize or $Y_e \geq p_i$. Then for all $a \in A$ we have $y_a(p_i)=p_i$. (5) For all countable ordinals $i$ we have $g(i)=p_{i+1}$ (this is false for all uncountable ordinals $i$). (6) The ordinal denoted as "$p$" in Relation of $\omega_{\omega_1+1}^{CK}$ to some other ordinals is equal to $p_{\omega_1+1}$ (in the notation of this question).

Along with few basic facts, the statement (4) in the above paragraph is essential to showing $\screen(p_i)=\screen(p_{i+1})$ whenever $i$ is countable and $R_i$ is an unpointable region. Some others basic facts I have skipped (which are relatively easy but longer to state and probably not that relevant to the question). At any rate, these show that the pointable values generally tend to be fairly well-behaved. Though some of the more complicated questions seem to be significantly more difficult (some seem relatively approachable, but others I don't have any idea).

However, the question I asked is one of the more intrinsic questions one can ask (in one sentence), but also seems more difficult (in comparison to the statements I wrote). This question is raised because, in contrast to countable $i$, if we are at some value $p_i$ (with uncountable $i$), then it is not necessary that all programs $e$ with $Y_e<p_{i+1}$ have stabilized to their eventual pointable value before $p_{i+1}$.

$\endgroup$

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.