Recursive enumerability of N-Cuil Problem

Summary:

Let the N-Cuil Problem be as follows: Given two situations x and x', and some constant N >=0, determine whether x' is a member of k‽(x), for any k such that 0 <= k <= N.

Recursive enumerability of N-Cuil Problem

Rich Frankel (guest) 1244190438|%e %b %Y, %H:%M %Z|agohover

Let the N-Cuil Problem be as follows: Given two situations x and x', and some constant N >=0, determine whether x' is a member of k‽(x), for any k such that 0 <= k <= N.

It seems to me that k‽(x) is an infinite set (when k > 0), in which case the N-Cuil Problem is not decidable, but is recursively enumerable. This is trivially true for N = 0, and is easy to see for N = 1. I suspect this also to be true for all N >= 0, but I am not positive. Thoughts?

Re: Recursive enumerability of N-Cuil Problem

oxygen83 1250046546|%e %b %Y, %H:%M %Z|agohover

Depends if the number of permutations if finite or infinite, which itself depends on whether the set of universes is countable or uncountable. If it is countable, one permutation and its inverse are sufficient to go through all of them. If it's uncountable, the number of permutations has to be at least countably infinite. Thus the set of all universes N cuils from 0, where N is finite, must also be countably infinite. Since it's countable, it's possible to use diagonalization to go through all of them and check if they're equivalent to x'. In any case, the problem is recursively enumerable.