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

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.

• (Before anyone beats me to it, I realize this maybe seems better suited for the (T)CS stack, but frankly I get stronger results here when it comes to this sort of area.) Oct 20, 2021 at 19:27

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$$.