I am new to computability theory, but I understand the usual definition of a "computable set" S when S is a subset of the natural numbers. Is there a notion of "computable set" that doesn't involve just subsets of the real numbers? In particular, I am interested in the set $\Sigma^{\omega}$ for some finite alphabet $\Sigma$ (this is the set of right-infinite words over $\Sigma$). Is there a notion of a computable subset of $\Sigma^{\omega}$? Off the top of my head, it seems that a possible definition would be to say that a subset $X$ of $\Sigma^{\omega}$ is computable if each sequence in $X$ represents a computable function $\mathbb{N} \rightarrow \Sigma$, but that doesn't seem correct. Any help is appreciated.

  • $\begingroup$ Maybe the definition you proposed may yield some interesting results. One thing to note is that with your definition all computable subsets of $\Sigma^\omega$ correspond to subset of $\omega$. $X \subset \omega$. $X \subset \omega \Leftrightarrow \{\Phi_e : e \in X\} \subset \Sigma^\omega$, where $\Phi_e$ is the computable function with index $e$. $\endgroup$
    – William
    Dec 10, 2011 at 19:20
  • $\begingroup$ @dan I think you should change the title to "Definition of a computable (or recursive) subset of $\Sigma^{\omega}$" so readers know that you're not asking a question about the definition of a computable set of natural numbers. $\endgroup$ Dec 12, 2011 at 18:51

2 Answers 2


"Computable" subsets of $2^\omega$ are the clopen sets under the product topology (generated by basic (cl)open sets of the form $[\sigma] := \{X \in 2^{\omega} \colon \sigma \prec X \}$, where $\prec$ denotes "is a prefix of"), which is why clopen sets are called $\Delta_0$ in the Lightface Borel hierarchy. (Recall that $\Delta_0$ in the arithmetical hierarchy means computable.)

Prateek's answer is essentially proving that any clopen subset of Cantor space $2^\omega$ is a finite union of basic opens. I think a better word than "computable" for these sets is "decidable", since given any infinite sequence and clopen set you'll eventually know if that sequence is the clopen set or not (by Prateek's answer).

  • $\begingroup$ I've limited my answer to the case $\Sigma = 2 = \{0,1\}$, but everything I've said holds for general finite $\Sigma$. $\endgroup$ Dec 12, 2011 at 18:49

Your definition does not seem right, as it talks only about individual elements of $X$, but nothing uniform about $X$. One could try to generalize from the definition of computable subsets of $\Sigma^*$ (all finite words over $\Sigma$), but as shown below, this gives something rather surprising. Here is the definition for $\Sigma^*$:

$X \subseteq \Sigma^*$ is said to be computable if there exists a Turing machine $M$ which on every input $x \in \Sigma^*$, halts and says "yes" or "no" accordingly as $x \in X$ or $x \notin X$.

This is equivalent to the notion of computability of subsets of $\mathbb N$. One could try to generalize this by just replacing $\Sigma^*$ with $\Sigma^\omega$.

$X \subseteq \Sigma^\omega$ is said to be computable if there exists a Turing machine $M$ which on every input $x \in \Sigma^\omega$, halts and says "yes" or "no" accordingly as $x \in X$ or $x \notin X$.

One might ask, what does it mean for a Turing machine to take $x \in \Sigma^\omega$ as input? Well, let's just say that $x$ is written on a tape available to the TM, just like for a finite word $x$. Of course, in finitely many steps, the TM can access only some finite prefix of an input infinite word.

Suppose we have a Turing Machine $M$, for a computable subset $X \subseteq \Sigma^\omega$. For every $x \in \Sigma^\omega$, $M$ run on $x$ eventually halts (and says yes or no). $M$ has examined only a finite prefix of $x$ before deciding whether to say yes or no. So we get

For every $x \in \Sigma^\omega$, there exists $N$ such that for any $y$ which agrees with $x$ in the first $N$ places, $(x \in X \iff y \in X)$.

This $N$ depends on the input $x$. Here's something interesting : we can get a uniform $N$ which works for all inputs (our $M$ and $X$ are still fixed)! More precisely,

There exists $N$ such that for every $x,y \in \Sigma^\omega$, if $x$ and $y$ agree in the first $N$ places, then $(x \in X \iff y \in X)$.

Here's a proof: For any finite word $\sigma$, say $M$ halts on $\sigma$ if on any infinite input which begins with $\sigma$, $M$ halts without examining more than the first $|\sigma|$ symbols of the input. This definition clearly does not depend on which infinite extension of $\sigma$ we choose. Let

$$S = \{ \sigma : \sigma \in \Sigma^* , M \textrm{ does not halt on } \sigma \}$$

$S$ is prefix-closed, and so can be naturally thought of as a tree. This tree is finitely branching (every node has finitely many children) since $\Sigma$ is finite. Note that since $M$ halts on every infinite input, every $x \in \Sigma^\omega$ has a finite prefix $\sigma \in \Sigma^*$ such that $M$ halts on $\sigma$. This means that our tree $S$ cannot have any infinite path (that is to say, $S$ does not have words $\sigma_0, \sigma_1, \ldots$ such that $|\sigma_i| = i$ and each $\sigma_i$ is a prefix of $\sigma_{i+1}$). From König's lemma, we get that $S$ is finite! (this is not hard to prove directly)

As $S$ is finite, let $N$ be one plus the maximum length of any word in $S$. For any input $x$, $M$ halts after examining at most the first $N$ symbols of $x$. This means that $$X = T\Sigma^\omega$$ where $T$ is a subset of the finite set $\Sigma^N$. So as per this definition, computable subsets of $\Sigma^\omega$ aren't very powerful, they just behave like finite sets.

As a bonus, observe that from a description of $M$ (if we already know $M$ always halts), we can effectively compute the $N$, by building up the tree $S$. So if we are given two such TMs $M$ and $M'$, we can effectively compute if $M$ and $M'$ compute the same set : just get the corresponding $N$ and $N'$, and check for all finite words of length $\max(N,N')$. This is interesting because the corresponding result is not true for computable subsets of $\mathbb N$ or $\Sigma^*$.

(Aside: instead of generalizing computability, if one generalizes the notion of regularity from $\Sigma^*$ to $\Sigma^\omega$, one gets omega-regular languages.)


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.