There are several classical ways of extending synthesis results, for
instance considering larger classes of specifications, larger classes
of implementations or both. In particular, an interesting direction is
to consider non-functional specifications. As mentioned in
Introduction however, and as a motivation for studying the functional
case,
enlarging both (non-functional) specifications and implementations to an asynchronous setting leads to
undecidability. Indeed, already in the finite alphabet setting, the
synthesis problem of deterministic transducers over \(\omega \) -words
from specifications given by non-deterministic
transducers is undecidable [1]}. A simple adaptation of
the proof of [1]} allows to show that in this finite
alphabet setting, enlarging the class of implementations to any
computable function also yields an undecidable synthesis problem. An
interesting case however is yet unexplored already in the finite
alphabet setting: given a synchronous specifications, as an
\(\omega \) -automaton, is to possible to synthesise a computable function
realizing it? In
[3]}, [4]},
this question has been shown to be decidable for specifications with
total input domain (any input word has at least one correct
output by the specification). More precisely, it is shown that
realizability by a continuous function is decidable, but it turns out
that the synthesised function is definable by a
deterministic transducer (hence computable). When the domain of the
specification is partial, the situation changes drastically:
deterministic transducers may not suffice to realize a
specification realizable by a computable function. This can be seen by considering the (partial) function \(g\)  of
Introduction, seen as a specification and casted to a finite alphabet
\(\lbrace a,b,c\rbrace \) : it is not computable by a deterministic transducer, since
it requires an unbounded amount of memory to compute this function.
