про первую часть, я думаю, что поскольку мн-во разрешимо, значит его хар-кая ф-ция вычислима, и след-но есть программа (алгоритм), которая может перечислить все эл-ты
а вот в обратную сторону догадок никаких нет..