- 291

- 36

**Preface:**

I also posted this question on mathoverflow(link: https://mathoverflow.net/questions/324110). A bit surprising for me that it has gotten votes to close. Mostly because all the dozen or so questions (after my very first one) that I have asked there have been received positively.

But maybe this question has some basic issue that I wasn't able to see (before posting)?

I would guess that it is one of my better questions there lest the mistake I made is a trivial one. But I haven't been able to see anything clearly wrong with the question till yet (and hence my reason for re-posting it here ..... and I suppose an extended discussion might help my understanding anyway). Since if there is trivial error/mistake I would like to delete the question there. I suppose perhaps maybe someone will point it out there in comments anyway.

**Here is the copy-paste of the 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.

Now here is my confusion, which I assume has a simple answer that I am failing to see. I will use some specific numbers just so that the main point is immediately clear (I really doubt the specific numbers really play any important role here .... so I have chosen some easy numbers for convenience).

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. I suppose I should write the details (unless the error is something simpler).

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.

Last edited: