niplav comments on shortplav

[niplav]

Consider proposing the most naïve formula for logical correlation^[1].

Let a program $p$ be a tuple of code for a Turing machine, intermediate tape states after each command execution, and output. All in binary.

That is $p=(c,t,o)$, with $c\in \{0,1{\}}^{+},t\in (\{0,1{\}}^{+}{)}^{+}$ and $o\in \{0,1{\}}^{+}$.

Let $l=|t|$ be the number of steps that $p$ takes to halt.

Then a formula for the logical correlation $合$^[2] of two halting programs $p_1=(c_1,t_1,o_1),p_2=(c_2,t_2,o_2)$, a tape-state discount factor $\gamma$^[3], and a string-distance metric $d:\{0,1{\}}^{+}\times \{0,1{\}}^{+}\to N$ could be

$$合(p_1,p_2,\gamma )=d(o_1,o_2)-\frac{1}{2+{\sum }_{k=0}^{min(l_1,l_2)}{\gamma }^k\cdot d\left(t_1\right(l_1-k),t_2(l_2-k\left)\right)}$$

The lower $合$, the higher the logical correlation between $p_1$ and $p_2$. The minimal value is $-0.5$.

If $d(o_1,o_2)<d(o_1,o_3)$, then it’s also the case that $合(p_1,p_2,\gamma )<合(p_1,p_3,\gamma )$.

One might also want to be able to deal with the fact that programs have different trace lengths, and penalize that, e.g. amending the formula:

$$合{}^{\prime }(p_1,p_2,\gamma )=合(p_1,p_2,\gamma )+2^{|l_1-l_2|}$$

I’m a bit unhappy that the code doesn’t factor in the logical correlation, and ideally one would want to be able to compute the logical correlation without having to run the program.

How does this relate to data=code?

---

1. ↩︎

   Actually not explained in detail anywhere, as far as I can tell. I’m going to leave out all motivation here.

2. ↩︎

   Suggested by GPT-4. Stands for joining, combining, uniting. Also “to suit; to fit”, “to have sexual intercourse”, “to fight, to have a confrontation with”, or “to be equivalent to, to add up”.

3. ↩︎

   Which is needed because tape states close to the output are more important than tape states early on.

[tailcalled]

What do you want to use the logical correlation measure for?

[niplav]

I don’t have a concrete usage for it yet.

[faul_sname]

Ideally one would want to be able to compute the logical correlation without having to run the program.

I think this isn’t possible in the general case. Consider two programs, one of which is “compute the sha256 digest of all 30 byte sequences and halt if the result is 9a56f6b41455314ff1973c72046b0821a56ca879e9d95628d390f8b560a4d803” and the other of which is “compute the md5 digest of all 30 byte sequences and halt if the result is 055a787f2fb4d00c9faf4dd34a233320”.

Any method that was able to compute the logical correlation between those would also be a program which at a minimum reverses all cryptograhic hash functions.

[robo]

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 $p_1$ and $p_2$ as random variables $\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }\cup \left\{\perp \right\}$, and compute their mutual information.

[niplav]

The strongest logical correlation is −0.5, the lower the better.

For $p$ and $\text{sim}\left(p\right)$, the logical correlation would be $-\epsilon$, assuming that $p$ and $\text{sim}\left(p\right)$ 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.

[Alexander Gietelink Oldenziel]

Could you say more about the motivation here ?

[niplav]

Whenever people have written/​talked about ECL, a common thing I’ve read/​heard was that “of course, this depends on us finding some way of saying that one decision algorithm is similar/​dissimilar to another one, since we’re not going to encounter the case of perfect copies very often”. This was at least the case when I last asked Oesterheld about this, but I haven’t read Treutlein 2023 closely enough yet to figure out whether he has a satisfying solution.

The fact we didn’t have a characterization of logical correlation bugged me and was in the back of my mind, since it felt like a problem that one could make progress on. Today in the shower I was thinking about this, and the post above is what came of it.

(I also have the suspicion that having a notion of “these two programs produce the same/​similar outputs in a similar way” might be handy in general.)

[Mateusz Bagiński]

If you want to use it for ECL, then it’s not clear to me why internal computational states would matter.

[niplav]

My reason for caring about internal computational states is: In the twin prisoners dilemma^[1], I cooperate because we’re the same algorithm. If we modify the twin to have a slightly longer right index-finger-nail, I would still cooperate, even though they’re a different algorithm, but little enough has been changed about the algorithm that the internal states that they’re still similar enough.

But it could be that I’m in a prisoner’s dilemma with some program $p^{\star }$ that, given some inputs, returns the same outputs as I do, but for completely different “reasons”—that is, the internal states are very different, and a slight change in input would cause the output to be radically different. My logical correlation with $p^{\star }$ is pretty small, because, even though it gives the same output, it gives that output for very different reasons, so I don’t have much control over its outputs by controlling my own computations.

At least, that’s how I understand it.

---

1. ↩︎

   Is this actually ECL, or just acausal trade?