>My hope is that one day someone will show LDU (or a similarly intuitive algorithm) can compare any two computable sequences, but I don’t think that this is that proof.
I’m pretty sure you can’t use a computable algorithm to do this for general computable sequences while maintaining weak Pareto efficiency due to a diagonalization argument. LetA(⋅,⋅) be the algorithm you use to choose between two computable sequences, which returns 0 if the first sequence is better and 1 otherwise. Let 0.5=(0.5,0.5,...) be the infinite sequence whose value is always 0.5. Consider the sequence a=(a,a,a,...) where a has value A(a,0.5). That is, if A chooses a, then a is an infinite sequence of 0s, and if A chooses 0.5, then a is an infinite sequence of 1s. Either way, A violates weak Pareto efficiency, since it tells you to choose a sequence whose value at every timestep is less than the other sequence.
Thanks! But is that correct? I notice that your argument seems to work for finite sequences as well (or even single rational numbers), but clearly we can order the rational numbers.
I think the issue here is whether you’re comparing functions (which allow self-reference in a way that can break ordering) or numbers (which don’t); for ordering arbitrary computable sequences, you need to have a way to avoid the sort of diagonalization that makes your choices affect the sequences you have to sort.
FYI, I was still confused about this so I posted on math .se. Someone responded that the above proof is incorrect, but they gave their own proof that there is no computable ordering over Z∞ which respects Pareto.
>My hope is that one day someone will show LDU (or a similarly intuitive algorithm) can compare any two computable sequences, but I don’t think that this is that proof.
I’m pretty sure you can’t use a computable algorithm to do this for general computable sequences while maintaining weak Pareto efficiency due to a diagonalization argument. Let A(⋅,⋅) be the algorithm you use to choose between two computable sequences, which returns 0 if the first sequence is better and 1 otherwise. Let 0.5=(0.5,0.5,...) be the infinite sequence whose value is always 0.5. Consider the sequence a=(a,a,a,...) where a has value A(a,0.5). That is, if A chooses a, then a is an infinite sequence of 0s, and if A chooses 0.5, then a is an infinite sequence of 1s. Either way, A violates weak Pareto efficiency, since it tells you to choose a sequence whose value at every timestep is less than the other sequence.
Thanks! But is that correct? I notice that your argument seems to work for finite sequences as well (or even single rational numbers), but clearly we can order the rational numbers.
I think the issue here is whether you’re comparing functions (which allow self-reference in a way that can break ordering) or numbers (which don’t); for ordering arbitrary computable sequences, you need to have a way to avoid the sort of diagonalization that makes your choices affect the sequences you have to sort.
FYI, I was still confused about this so I posted on math .se. Someone responded that the above proof is incorrect, but they gave their own proof that there is no computable ordering over Z∞ which respects Pareto.