In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a sequence (NOT a set) $S=(s_1,s_2,\ldots)$ is 1-computable if (I state it differently from the paper but equivalently) there is a Turing machine that writes this sequence to the tape in the correct order. A set $S$ is 1-enumerable if there is a Turing machine which prints exactly the elements of $S$ but in any order.

However, what we usually understand is that "computable" means a Turing machine which guarantees to halt and can find out whether an element belongs to a set $S.$

Is there any relation between those two different definitions of computability?


1 Answer 1


If you have one of:

  1. A machine that takes an index $i$ and definitely terminates with $s_i$ as a result
  2. A machine that takes an index $i$ and a value $s$ and definitely terminates, indicating whether $s$ is the $i$th value of the sequence

then you can write out the sequence in order by simulating one of the above machines for each index in turn. #2 requires searching for the right $s$, but that can be done.

You can also go in the opposite direction. Simulate the machine that writes the sequence in order until it produces the $i$th element, then either yield it for #1, or check it against the input for #2 (assuming representations of $S$ can be compared computably).

If you have:

  • A machine that takes a value $s$ and definitely terminates if $s \in S$, and otherwise might not halt.

Then you can make a machine that enumerates all of $S$ in an arbitrary order by dovetailing. You simultaneously simulate the machine on ever more candidates, and finalize a result whenever one of the simulations halts. The order that you'll enumerate the values depends on how long it takes for the input machine to halt, though, and you have to interleave simulations to avoid getting stuck on a simulation that will never halt. So no order can be guaranteed.

You can also go backwards in this scenario. Given a machine that enumerates $S$ in an arbitrary order, you can produce a machine that given $s$, definitely terminates if $s \in S$, and loops otherwise. You just simulate the enumerator, and check $s$ against what it produces. If $s \in S$ then you will eventually get a match. Otherwise you will keep looking forever, because there is no guarantee about the order of the enumeration.

The first scenario is "recursive" or "computable." The second scenario is "recursively enumerable" or "computably enumerable."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.