1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I would call this “unclear what you’re asking”. If it were half the length, with less apologizing and psychologizing and more mathematical context, it would probably be fine. $\endgroup$
    – Matt F.
    Feb 26 '19 at 13:34
  • $\begingroup$ OK I will edit the question in that case. $\endgroup$
    – SSequence
    Feb 26 '19 at 14:07
8
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ The function $f$ defined in first paragraph of the second part of your question will take on only values $a \in \mathbb{N}$ which are algorithmically incompressible. Because they are incompressible, if $a$ is in the range of $f$, there is no program shorter than the length $a$ (less a fixed additive constant) which sets a variable equal to $a$. $\endgroup$
    – James
    Feb 26 '19 at 12:54
  • $\begingroup$ OK, thanks for clarifying your point. I will have to think about it in the context of question. $\endgroup$
    – SSequence
    Feb 26 '19 at 13:22
  • $\begingroup$ Your answer and comment seems quite relevant to my question. I do not know anything about kolmogorov complexity, so I have phrased my comment (after some brainstorming) in terms of how I am looking at it. Intuitively, as I understand, you are saying that program that sets some variable value equal to $f(a)$ will (always) have an index "very close" to $f(a)$. So even when we add the body of universal program after it, the total program-length will increase enough that the index of the resulting program will go "beyond" $f(a)$. Is this somewhat close to what you are describing? $\endgroup$
    – SSequence
    Feb 26 '19 at 14:50
  • $\begingroup$ But what is confusing me is that $f$ is a very slow-growing function. It can easily be recursively bounded (normally exponentially bounded). Wouldn't that be a problem? Because I can just give a very fast growing recursive function (thinking functions like tower,ackerman and beyond). Because the program-length for a program that sets a variable value to $f(a)$ has to be very close to $f(a)$ for all $a \in \mathbb{N}$ (once we consider the argument described in question in generality). Is this addressed too using the formalism you described in your answer? $\endgroup$
    – SSequence
    Feb 26 '19 at 14:55
  • 1
    $\begingroup$ Even functions whose growth is bounded linearly can have all of their values be algorithmically incompresible. The reason this is possible is that "almost all" strings are are algorithmically incompressible. $\endgroup$
    – James
    Feb 26 '19 at 20:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.