2
$\begingroup$

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.

  • 0
    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$.2011-12-10
  • 0
    @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.2011-12-12

2 Answers 2