An Apparent Incongruity

Question

I thought of a certain point that seems to point to an apparent incongruity. Hopefully someone would promptly point out the logical mistake and/or some implicit assumption that may not hold under a closer look. Even though the question is a quite long in length, the actual point is very short. I have thought about it for a good number of hours, but I am likely suffering from a blindspot (and possibly an easy one, though I would hope it isn't trivial).

So here is the rather short construct, so to speak. Let's first consider the case of $\omega_{CK}$. Now we want to define two functions $F:\omega \rightarrow \omega_{CK}$ and $f:\omega \rightarrow \omega$ (the way I consider $F$ and $f$ in the actual question is almost exactly the same). For $F$, we simple define $F(x)$ to be the ordinal value whose well-order relation (for a well-order of $\mathbb{N}$) is generated by program with index $x$. If the program with index $x$ doesn't generate a well-order relation we can set $F(x)=\omega_{CK}$ (just as a matter of convention really).

Now we want to define the function $f$. We define $f(0)$ to be the smallest value $a \in \mathbb{N}$ that satisfies the property $F(a)<\omega_{CK}$. Now we recursively define $f(x+1)$ to be the smallest value $a \in \mathbb{N}$ such that: (1) $F(a)>F(f(x))$ AND (2) $F(a)<\omega_{CK}$. It isn't difficult to see that: (a) $f$ is a strictly increasing function (b) The function $G:\omega \rightarrow \omega_{CK}$ defined by the equation $G(x)=F(f(x))$ forms a (fundamental) sequence for $\omega_{CK}$.

Now before proceeding, an elementary point that is relevant to the question. Consider an ordinary program where all variables start from value $0$. We also assume that the only way to increase the value of a variable is by the command of form $v:=v+1$. Now suppose we wanted to set a variable value to say $1000,000$. We don't have to write the same number of lines for increment. We can just write a function ($\mathbb{N}$ to $\mathbb{N}$) such as $x \rightarrow 10^x$. Suppose hypothetically that this function takes $100$ lines. Now all we have to do is increment a variable (call it $v$) six times in the beginning and then place the body of function calculating $10^x$ afterwards (replacing the input variable by $v$ in the body of course). This will set the output variable to $1000,000$ in $106$ lines.

---

And now here is my confusion. Let $c$ be the supremum of clockable values for an ordinal-register program (or a program model that is quite similar to it). Now define a function $F:\omega \rightarrow c$ so that $F(x)$ returns the value clocked by the program with index $x$. If the program with index $x$ doesn't halt set $F(x)=c$ (as convention). Now define functions $f:\omega \rightarrow \omega$ and $G:\omega \rightarrow c$ in a manner completely identical to how they were defined in first part of question.

Consider the family of programs that, for some given value $a \in \mathbb{N}$, simulate the program with index $f(a)$. These programs halt in their simulation when the program with index $f(a)$ halts. These programs all have the same structure. For convenience choose $f$ to be a very simple function, say $x \rightarrow 10^x$ (obviously $f$ can't be recursive, but the main thing is just that $f$ is strictly increasing). The main point that is confusing me is, that for a very large value $a \in \mathbb{N}$ (and hence also very large $f(a)$), why can't we just set a variable equal to value $f(a)$ rapidly in a few lines and then simulate the program with index $f(a)$ using essentially a universal program. And unless the specific construction for infinite case (since I have never written it in full detail) has some drastic different from finite case here, wouldn't this be a constant overhead in terms of number of lines.

It sounds too abstract but a simple example would help. Suppose writing the universal program takes about $200$ lines. Now as I mentioned above, suppose that $f(x)=10^x$. In particular, we have $f(6)=1000,000$. But couldn't we just set a variable whose value equals $1000,000$ in $106$ lines (as I mentioned in first part of answer) and then place the body of universal program afterwards (to simulate the program with index $1000,000$). Wouldn't this would take a total of just $200+106=306$ lines? Sure its index will be a bit higher, but I am not clear that this makes any real difference. The program with index $1000,000$ clocked the value $G(5)=F(f(5))$. And now somehow the program with smaller index is clocking a value greater than or equal to $G(5)$ [assuming that simulating a program will always be at least as expensive as directly running the program]?

Now given that our indexing is well-behaved in the sense that it assign the program of bigger length the greater index, then what I wrote in above paragraph simply shouldn't hold (otherwise there seems to be an incongruity). Hopefully someone will promptly point out the error.

Answer 1

This is an OK question, you just have not explained it very clearly. I think people are downvoting because they think you are confused about whether $f$ is computable or not (which you aren't).

What you're running into is something that ultrafinitists study in detail. It boils down to the fact that "having a short description" is not closed downwards. For example, we can describe a very, very large number with only a handful of characters by $4 \uparrow^{100} 5$ in Knuth's "up arrow" notation. But most of the numbers less than $4 \uparrow^{100} 5$ don't have descriptions that could ever be written down, or even descriptions of length less than $4 \uparrow^{99} 5$. This is just the pigeonhole principle.

One way to think about this is to use algorithmic incompressibility using prefix free Kolmogorov complexity. Fix a compression factor $r < 1$, and look at the proportion of strings $\sigma$ of length $<n$ which can compressed by at least factor $r$ (i.e., have $K(\sigma) < r|\sigma|$, where $K(\sigma)$ is the length of the shortest description of $\sigma$ according to a fixed universal encoding scheme). This proportion has to converge to zero as $n \rightarrow \infty$.

This tells you that you shouldn't expect a priori that the values of your function $f$ are going to be compressible. And in fact if you think carefully about what you've written, you've actually proven that they can't be compressible by more than than a fixed additive constant determined by the size of a universal machine.