How many recursive language families are there?

114 Views Asked by At

Let’s define a transducer as a $5$-tuple $(Q, A, B, \phi, \psi)$, where $Q$ is a finite collection of states, $A$ is a finite input alphabet, $\phi: Q\times A \to Q$ is the transition function and $\psi: Q \times A \to B^*$ is the output function.

Any transducer defines a transducer function $\overline{\psi}: Q\times A^* \to B^*$ described by the following recurrence:

$\overline{\psi}(q, \Lambda) = \Lambda$, where $\Lambda$ is the empty word.

$\overline{\psi}(q, a \alpha) = \psi(q, a) \overline{\psi}(\phi(q, a), \alpha)$, where $a \in A$, $\alpha \in A^*$.

Let’s call a function $f: A^* \to B^*$ a regular transduction iff $\exists$ a finite transducer $(Q, A, B, \phi, \psi)$ and an initial state $q \in Q$, such that $\forall \alpha \in A^*$ we have $f(\alpha) = \overline{\psi}(q, \alpha)$.

Now, let’s call a set of languages $\mathfrak{F}$ over a finite alphabet $A$ ($|A| > 2$) a family iff it satisfies two properties.

1)$\forall L_1, L_2 \in \mathfrak{F} L_1 \cup L_2 \in \mathfrak{F}$

2)$\forall L \in \mathfrak{F}$ and $\forall$ regular transductions $f$ $f(L) \in \mathfrak{F}$.

It is not hard to see, that the class of all recursive languages (languages that can be recognised by a Turing machine) forms a language family.

Let’s call a language family recursive, iff it is contained in the family of all recursive languages (or iff all its languages are recursive).

My question is:

How many recursive language families are there?

It is known, that there are ${\aleph_0}$ recursive languages total, and thus the number of recursive language families is $\leq 2^{\aleph_0}$.

On the other hand, it is $\geq \aleph_0$ due to the following theorem, proved by David Weir in 1992:

$\forall n \in \mathbb{N} \exists$ a recursive language family that contains $\{w^{2^k}| w \in A^*\}$ $\forall k < n$, but does not contain $\{w^{2^n}| w \in A^*\}$

This question is a follow up of that one, however, the method used in the answer to it can not be applied this time, as there are only countably many infinite strings $\phi \in A^\mathbb{N}$ such that $L(\phi)$ is recursive.