Considere el siguiente problema del universo .
El problema del universo. Dado un conjunto finito para una clase de idiomas y un autómata que acepta el idioma , decidir si .
En [1], se afirma y prueba que el problema del universo es indecidible para una clase particular de autómatas de un contador. Este resultado sigue para la clase de todos los autómatas de un contador no deterministas. Me pregunto si se sabe si este problema aún es indecidible cuando restringimos el tamaño del alfabeto de entrada del autómata.
Creo que con el tamaño del alfabeto 1 el problema se vuelve decidible, pero ¿qué pasa con el tamaño 2? Y si eso resulta ser decidible, ¿cuál es el valor más pequeño de tal que el problema es indecidible.
Creo que es probable que se conozca la respuesta a esta pregunta, pero tengo problemas para encontrar una respuesta. Si ya se conoce, agradecería una referencia.