0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ (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.) $\endgroup$
    – Trevor
    Oct 20, 2021 at 19:27

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I felt like an idiot for a second, but actually, I don't think this is quite what I had in mind. Sure, this will work, but will also carry out lots of unrelated computation -- I'm curious whether it is always possible to build out a chain such that every step is itself a valid state simplifying to the goal value. I realize I didn't specify that at all... I think that was the third criterion I forgot. $\endgroup$
    – Trevor
    Oct 20, 2021 at 21:22
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .