Playing with Conway’s Problem

The centralizer of a language is the maximal language commuting with it. The ques-tion, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, a strong nega-tive answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game ap-proach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers. In 1999, Choffrut et al. [1] renewed an old problem raised by Conway [2] in 1971: given a rational language, does its centralizer — the maximal language commuting with it — have to be rational? The property is known to hold for some particular families of languages. In the case of codes, Ratoandra-manana [3] showed in 1989 that it holds for prefix codes, raising a restriction of Conway’s problem to codes which recently recieved a positive answer by Karhumäki et al. [4]. In the general case, until recently, the best known result, by Karhumäki and Petre [5], was that the centralizer of a recursive language has to be co-recursively enumerable. This property may also be considered as a particular case of results of Okhotin [6] concerning the computational power of systems of equations on languages. For a complete survey on Con-way’s problem, the reader may refer to [7–10]. In 2004, the community was thrilled by an announcement by Kunc [11] that a centralizer can actually be non-recursive. This announcement was followed by a conference communica-tion [12] in 2005 showing that finite languages exist whose centralizers are complete for co-recursively enumerable languages 1. It includes a sketch of the proof for the special case of rational languages. While simpler than the proof ∗ Corresponding author