1
$\begingroup$

I have a basic question about the behavior of a potential Turing machine.

Suppose that $S$ is a countable set of binary strings, so that we can enumerate $S$ as $(s_i)_{n\in \mathbb{N}}$.

Suppose that we want to construct a Turing machine $M$ that, on any input, simply writes each element of $S$ on a tape in order $s_1, s_2, \ldots$. (I realize that $M$ will never halt.)

But we can construct such an $M$ if and only if our particular bijection $\mathbb{N} \to S$ is computable, correct? Or is knowing that $S$ is countable somehow enough?

$\endgroup$
0
$\begingroup$

By definition, a set $S$ is recursively enumerable if there is a Turing machine that enumerates it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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