How close would this rank a program p with a universal Turing machine simulating p? My sense is not very close because the “same” computation steps on each program don’t align.
My “most naïve formula for logical correlation” would be something like put a probability distribution on binary string inputs, treat p1 and p2 as random variables {0,1}∗→{0,1}∗∪{⊥}, and compute their mutual information.
The strongest logical correlation is −0.5, the lower the better.
For p and sim(p), the logical correlation would be −ε, assuming that p and sim(p) have the same output. This is a pretty strong logical correlation.
This is because equal output guarantees a logical correlation of at most 0, and one can then improve the logical correlation by also having similar traces. If the outputs have string distance 1, then the smallest logical correlation can be only 0.5.
How close would this rank a program p with a universal Turing machine simulating p? My sense is not very close because the “same” computation steps on each program don’t align.
My “most naïve formula for logical correlation” would be something like put a probability distribution on binary string inputs, treat p1 and p2 as random variables {0,1}∗→{0,1}∗∪{⊥}, and compute their mutual information.
The strongest logical correlation is −0.5, the lower the better.
For p and sim(p), the logical correlation would be −ε, assuming that p and sim(p) have the same output. This is a pretty strong logical correlation.
This is because equal output guarantees a logical correlation of at most 0, and one can then improve the logical correlation by also having similar traces. If the outputs have string distance 1, then the smallest logical correlation can be only 0.5.