0
$\begingroup$

Suppose that we have an alphabet Σ = {a}. My question is, is it possible to create a language with this alphabet, which is recursively enumerable, but not recursive?

My assumption is a no, i think we can construct a deterministic finite machine, which accepts every language, constructed with a single element in its alphabet.

$\endgroup$
  • $\begingroup$ "i think we can construct a deterministic finite machine" -- How so? $\endgroup$ – Raphael Nov 8 '17 at 18:50
  • $\begingroup$ my initial thought was, since we have a single letter in the alphabet, the languages constructed with it will have the same pattern. $\endgroup$ – Fanta Nov 8 '17 at 22:21
  • $\begingroup$ It was a naive approach per se $\endgroup$ – Fanta Nov 8 '17 at 22:23
3
$\begingroup$

There are undecidable unary languages.

You can consider the set of words in $\{0,1\}^*$ as essentially encoding natural numbers in binary.* Similarly, the set of words in $\{1\}^*$ encodes natural numbers in unary. Intuitively, if a set of natural numbers is undecidable, that doesn't depend on the base in which the numbers are represented, since we can easily write algorithms to convert between bases.

Another way to see this is to observe that any decidable language (over any alphabet) is, by definition, decided by some Turing machine. There are only countably many Turing machines, but there are uncountably many unary languages. Therefore some (almost all!) unary languages must be undecidable.


* This isn't quite true because of the empty string and because, e.g., the strings $1$ and $01$ are clearly different but both encode the number one in binary. To get around this, say that the string $w$ encodes the number whose binary representation is $1w$.

$\endgroup$
1
$\begingroup$

Sure we can. The set of all words $\Sigma^*$ is isomorphic to $\mathbb N$, since only the length of each word matters. That is, given a word we can take its length, and given the length we can reconstruct the original word. Hence the bijection, which is trivially computable.

Hence, we can just take any r.e., non recursive subset of naturals $A$ (e.g. the Kleene's set $K$) and consider the language of all words of the form $a^n$ with $n\in A$.

$\endgroup$
1
$\begingroup$

It's easy to encode the Halting problem as unary language:

$\qquad\displaystyle L_H = \{ a^{\langle M \rangle} \mid M \text{ is a TM}, M(\langle M \rangle) \text{ halts}\}$

is decidable if and only if the (special) Halting problem is decidable (proof is a pair of trivial reductions).

What you may have had in mind is that all context-free unary languages are also regular. That is an interesting fact, but does not carry up the Chomsky hierarchy. There are many ways to see that, including

  • Myhill-Nerode's theorem and
  • Parikh's theorem.
$\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.