# decidability of regularity of a language depending on representation

It is well known that many decision problems for regular languages are decidable. However, the proofs seem to rely on a witness of the regularity of said language, be it an automaton, a grammar, a regular expression or whatever.

But what happens if you are presented with a set $$L\subset \Sigma^*$$ that just happens to be regular. Is its regularity algorithmically decidable? I assume it is, if I have a defining formula $$\varphi$$ of some simple enough sort. But is there a crisp boundary as to what kind of representation is necessary?

Thanks for reading!

• If you give a language by a Turing machine you cannot decide if it is regular, so these things of course depend on the representation. I would guess you would need to be more specific about what sorts of representations you allow in order to get a precise answer. – Benjamin Steinberg May 16 at 12:58
• What do you mean by "presented with a set"? Are you just given a black box for deciding membership in the set? Or an algorithm fo deciding membership? Or an algorithm that lists the members of the set? Or what? – Andreas Blass May 16 at 13:01
• @ Andreas. I didn't want to specify this, as I wanted to know the answer for several different representations, if possible. So let's assume the set is given by a black-box deciding membership (I guess that would mean you have $L$ as an oracle, if you want to check membership with a Turing machine). Also, what if the set was defined by some formula $\varphi$ in some logic (with or without parameters). For example, if $\varphi$ was some expression in first-order logic over $\mathbb{N}$. I know it is a very general question... I'm also happy if I am pointed towards some literature or papers. – Sebastian Mueller May 16 at 13:14
• @Benjamin. Thanks, is that obvious or can you point to some literature? – Sebastian Mueller May 16 at 13:19
• Rice’s theorem covers the Turing machine. – Benjamin Steinberg May 16 at 14:04