Now why I have I never stumbled on this before...
https://en.wikipedia.org/wiki/Rice%27s_theorem
So these are a class of theorems of varying generality that prove that the only way to find out the "result" of a program is to run it.
And by "result" we mean any non-trivial property of the behaviour of the algorithm /logic /machine /process.
So I began with the question of whether there was a proof for there being no universal algorithm to find memory leaks in a program.
A memory leak is a kind of self-reference. An object references another object that through any manner of complex tree ends up referencing the first object. Automatic garbage collection tends to work by reference counting and when an object is no longer referenced it is assumed safe to remove. However if object A holds a reference to B and B holds a reference to A then we cannot garbage collect either. If we delete the object A a reference still remains in B, and if we delete B a reference remains in A so there is no way to get the references down to 0 for garbage collection to operate. We need remember to add Destructor logic to clear these internal references when the object is removed. Now when we delete A its destructor removes the reference to B. A remains alive in memory however due to B's dependence on it. But now when we remove B it is no longer referenced in A and can be destructed. And when it destructs then A is no longer referenced and memory can be clean up at last.
But this is just a simple case of an object A having another object B injected and a reference held for the lifetime of the object. What if it itself then spawns other objects like event handlers or delegates and passes B into those. If at any point anything in the tree keeps a reference to A then we have the self-referential loop that will stop garbage collection permanently and so a memory leak. The coder needs to be very cautious at each step to make sure that in every scope where an object reference is assigned there is code that will definitely be called at some stage to unassign it.
Now ChatGPT was of the opinion that this falls into the class of algorithms that are deciding a property of the code. And via Rice's Theorem the only universal way to see if there is a memory leak is to run the code and see.
But via later versions of this, we run into a practical problem that you cannot run a program an infinite number of times for every possible input. So even running it is has limited power. Such problems are basically not universally computable is the conclusion.
However I have no proof at this stage, and it seems to me the algorithm stated above of ensuring that a Destructor is present that matches every Constructor should ensure that all references get removed in a orderly fashion and garbage collection can operate in a fail safe way. I suppose we would need however to ensure that all possible computations fit that pattern. What if the only way to solve a problem was to inject and store more references after construction. Anyway something to do.
The relevance to SRH should be obvious. Essentially SRH is saying that you cannot put the foundation of a house on the house. A solid house must have foundations on something other than the house itself.
Arguments of the type:
Elephants are always truthful.
How do you know?
Well ask an elephant.
Fail by SRH. Because the argument that Elephants are truthful is founded upon the truthfulness of Elephants it is a Self-Referential Loop and so Self-reference Hypothesis says it is false.
This enters the same problems at the Memory Leak Problem above. To be safe from SRH you need to scan your entire argument and assumptions/dependencies to see whether you have anything referencing itself (via any path).
Rice's Theorem then says that there is no Universal Algorithm for SRH that could statically scan and argument and look for loops and so fallacy.
This is easier to prove than Rice's Theorem though because SRH is stating that anything with a Self-Referential Loop is false. And that means that SRH must not itself have a Self-Referential Loop. But as already shown earlier in blog: to be universal then SRH must decide somewhere whether SRH is free from loops. Well it is like the Elephants then deciding its own truth/false value.
But this is where it gets interesting. If SRH is True then loops matter which means it is false. If SRH is false then loops don't matter and so it could be True (may be other reasons why it is false).
SRH is a contradiction. But we can't reject it as it is self evident that a proof cannot be based upon itself.
We have essentially the same pattern as Godel's 2 Theorems.
Now we pushed this a step further. There is the pattern where we say "All rules have an exception"
If we apply this to our self we realise that there must be a rule which has no exception. This allows "All rules have an exception" to be a universal rule, while superficially stating that nothing is universal.
In a similar way can't we say that "All self-referential looping arguments are false"
If we apply it to itself then it is a "self-referential looping argument" and so is false. Which means there exists "a self-referential looping argument" that is true. And this allows SRH.
Summary/Conclusions
- Rice's Theorem is stronger than we need for SRH proof.
- SRH because it claims to provide a Truth decision generates a simple contradiction according to Tarski's Undefinability Theorem
- However SRH is self-evident on the small scale. Check this is really true with accepted Self-Referential Proofs like construction of Integers.
- The contradiction at the heart of the SRH provides the foundation for its proof. Is this valid logic?
- The consideration of Memory Leaks provides a real life analogy of how SRH is used.
==
Now not all proofs that involve self-reference are considered false. There is the Construction of the Integers. #TODO explore this again.