0
$\begingroup$

https://en.wikipedia.org/wiki/Recursively_enumerable_set says

A subset S of the set of natural numbers is called recursive enumerable, if there is a partial recursive function whose domain is exactly S.

A recursive enumerable language is a recursive enumerable subset of a formal language.

  1. Does "A recursive enumerable language is a recursive enumerable subset of a formal language" mean "A recursive enumerable language is a recursive enumerable subset of $\Sigma^*$" instead?

  2. Does the second sentence for a recursive enumerable language assume some encoding from the set of all words over an alphabet to the set of all natural numbers? What is some classic encoding?

Similar questions about that https://en.wikipedia.org/wiki/Recursive_set says:

A subset S of the set of natural numbers is called recursive if there exists a total recursive function whose domain is exactly S.

A recursive language is a recursive subset of a formal language.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ If you can handle one encoding, you can handle any reasonable encoding, because translations between them are generally primitive recursive functions. We therefore do not usually worry about which encoding is used. $\endgroup$ – Ross Millikan Jun 29 at 22:34
  • $\begingroup$ could you give a classic encoding? $\endgroup$ – Tim Jun 29 at 22:54
  • $\begingroup$ It depends on the language. The one I am familiar with is used in the PA incompleteness proofs. There are about a dozen characters needed in the language and you give them each a number. Then the string $abc$ is encoded as $3^a5^b7^c$ and you just use enough primes for the number of characters. A sequence of strings $abc,def$ is encoded as $2^{3^a5^b7^c}3^{3^d5^e7^f}$. If the number is even you know you need the second layer of unpacking. $\endgroup$ – Ross Millikan Jun 29 at 23:11
  • $\begingroup$ I was wondering about encoding of binary strings over $\{0,1\}$ into natural numbers $\endgroup$ – Tim Jun 29 at 23:20
  • $\begingroup$ You can just use base $2$ to do that. Each string goes to the number it represents. You need to put a $1$ in front of each string to handle strings that start with $0$. $\endgroup$ – Ross Millikan Jun 30 at 0:37
2
$\begingroup$

We have many equivalent options here, analogously to how there are many equivalent formulations of computability in the first place; and just as in that situation, the equivalences between all reasonable notions let us be pretty blithe about the details.

The two main points to have in mind are the following:

  • We can define "recursively enumerable subset of $\Sigma^*$" for any finite language $\Sigma$ directly: as the set of strings in $\Sigma$ accepted by some Turing machine with alphabet some superset of $\Sigma^*$. This doesn't involve any coding and is totally unambiguous; however, it really only works for finite $\Sigma$s.

  • Alternatively, given a finite language $\Sigma$ we can consider for each $f:\Sigma^*\rightarrow\mathbb{N}$ the notion of computability gotten by saying that $X\subseteq\Sigma^*$ is recursively enumerable via $f$ if $f[X]:=\{f(x): x\in X\}$ is an r.e. subset of $\mathbb{N}$. Note that of course this will depend on the choice of $f$. On the plus side, this generalizes quite a lot and is a useful abstraction down the road.

It turns out that any "natural" choice of $f$ will result in the first version of r.e.-ness, and moreover such an $f$ is easy to whip up. For a generally applicable example, fix some numbering $\{\sigma_1,...,\sigma_k\}$ of $\Sigma$ and consider the map $\sigma_{i_1}\sigma_{i_2}...\sigma_{i_n}\mapsto p_1^{i_1}p_2^{i_2}...p_n^{i_n}$ where $p_j$ denotes the $j$th prime; for a particularly nice example in the case where $\Sigma=\{0,1\}$, just send $x\in\{0,1\}^*$ to the natural number with binary expansion $1x$ (so e.g. "$010$" goes to $1010_2=10$). So we tend to ignore the details here.

| cite | improve this answer | |
$\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.