Return to Question

Edit: I see that there are three votes to close the question. I hope someone can point where the problem lies in the description below. Perhaps someone can briefly describe in comments where I have made a mistake? I haven't been able to find it. Of course I would delete the question if the actual issue is uninteresting or trivial.

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).

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).

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).

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+105=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]?

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]?

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).

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 $105$ 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+105=305$ 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]?

Edit: I see that there are three votes to close the question. I hope someone can point where the problem lies in the description below. Perhaps someone can briefly describe in comments where I have made a mistake? I haven't been able to find it. Of course I would delete the question if the actual issue is uninteresting or trivial.

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).

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+105=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]?