No Algorithm to calculate Complexity

Can we find the shortest algorithm code to perform a task? This question seems to be behind most of what I’m trying to think out.

Is it possible to compute the shortest algorithm? Suppose we had an algorithm say a function: bool Optcpx(char* code) that returns TRUE if it is the shortest code and FALSE if there is a shorter code.

So we have some code that implements Optcpx() and we feed that into the Optcpx() algorithm to see if there is a shorter piece of code that performs the same function.

What Optcpx() has to do determine if there is any code that will do the same thing as itself and which takes up less memory. Here is Ouroboros and SRH problem seems to emerge!

Suppose Optcpx() returns FALSE. It means that there is a shorter piece of code that will also return FALSE when given this code as input. In other words the Optcpx() function needs to know that it will return FALSE before it has completed so that it knows that the other piece of code will also return FALSE. Put another way (this is not clear in my head yet) the code can’t determined whether another piece of code is functionally identical until it knows its own output, and if its own output depends upon the nature of another piece of code then it is stuck.

This assumes that you can only determine a codes “identity” from its output.

So Optcpx() can’t determine whether another piece of code is functionally equivalent to itself. Thus it can’t determine whether it is a larger or smaller piece of code to itself.

There is no way of computing the smallest algorithm for Optcpx().