Must every Turing-complete language be able to enumerate precisely those algorithms which return a particular value?

Question

This kind of enumeration is particularly easy with some languages. For example, using SKI combinators, start with the expression $\mathbf{SKK}$ (Church encoding for $1$) and systematically apply the inverse operations of $\mathbf{S}$ and $\mathbf{K}$; e.g., to perform $\mathbf{K^{-1}}$, convert any existing term $x\to \mathbf{K}xy$, where $y$ can be any term you'd like.

It's easy to see how one could then step backwards through all possible computational trees by using ever more complex $y$ substitutions, converting additional terms, and repeated application of the operation; it would take countably infinitely long, but it seems you would be ensured to eventually reach any expression which will terminate with a value of $\mathbf{SKK}$. In other words, you could enumerate the exact set of programs or problems which have $1$ as their answer.

Turing completeness being what it is, my intuition is that this same property must hold for any Turing-complete model of computation. However, note the conditions that must be satisfied to match the example given above:

1. Given a fixed final computation state $W$ (read: a return value), and an arbitrary program length $N$, every algorithm of length $N$ or less that returns $W$ will be produced within some finite amount of time.
2. No programs that don't simplify to $W$ can be produced by your algorithm.
3. Edit: Every computational state generated by the algorithm is itself a member of the set that reduces to $W$. This rules out TomKern's otherwise very effective brute-force approach.

A general approach to the enumeration algorithm can be approximated, I think. Select the ending state you wish to simplify to, and then within the constraints of whichever computational model it is, identify every computational state which is penultimate to that. Rinse and repeat.

So does this apply to every TC language? I expect so, but I have been surprised by pathological edge cases and simple oversights too many times not to double check. It also seems plausible I have overlooked some Gödelian argument. I will consider a simple yes/no and a link or two to further reading, or alternatively some further exposition on this, to be a satisfactory answer.

Answer 1

If I'm understanding your question correctly, your enumeration procedure can be to just run every program in (diagonal) parallel and then if a program halts and returns the desired value, add it to the enumeration.

Answer 2

A really interesting distinction here is whether the set of all states that directly lead to a given state are recursive or recursively enumerable. Of course for any notion of computability this will be recursively enumerable, but you might want to distinguish between recursively enumerable in some meaningful way, versus recursively enumerable by just brute force checking all possible states for what states come next after them. I'm not sure how to formalize this.

But even in the case of recursive enumerability, you can still recursively enumerate the set of states that lead to a given finite state. Every time you discover a new state $S$ that eventually leads to the given finite state, print it out, then add a new machine to a parallel time-share setup that hunts for states that lead to $S$.