Let a finite alphabet $\Sigma$.

Let $\mathcal{Reord_\Sigma}$ be the family of computable partial functions between the strings of this alphabet $r\,:\, \Sigma^*\, \rightarrow \Sigma^*$ with the restriction that the value must be a permutation of the argument.

I'm interested in a class of deterministic abstract machines with finite control that compute all and only the functions of this family. That is, given a string $s \in \Sigma^*$ as input, the machine either doesn't halt or halts returning a permutation of $s$, and every possible mapping of those is realized by some machine in the class.

All the transitions should be local (no random access on a tape), and possibly they should not explicitely name the symbols to be written (they should be 'copy' or 'swap' operations, not 'write symbol "A" ').

Does this class of transducers exist? Has it been researched?

  • 3
    $\begingroup$ The first thing that came to my mind is Sorting Networks ... but I don't know if that model can help you. $\endgroup$ Oct 23, 2012 at 17:00
  • $\begingroup$ I don't think it can be reformulated as a sorting problem. Sorting requires elements to be pairwise comparable. I don't make this assumption. $\endgroup$ Oct 23, 2012 at 21:52
  • 1
    $\begingroup$ I agree with you, but if you treat the "comparators" of a Sorting Network like simple "switches" (whose state is embedded and/or calculated by the abstract machine) then perhaps the model gets closer to your needs. Can you give more details about the context (theoretical and/or practical) in which those transducers should be used? $\endgroup$ Oct 23, 2012 at 23:03

1 Answer 1


If you allow an auxiliary work tape, then it is easy to customize the Turing machine model to suit your needs. The Turing machine has two tapes: input/output and work. The work tape operates as usual, while on the input/output tape, all you can do is switch two adjacent values. This is enough since the transpositions $(i \quad i+1)$ generate all of $S_n$.

If you don't allow a work tape, then the goal might be impossible. Let $f$ be a recursive function not computable in $O(n\log n)$ space. We can think of $f$ as a reordering function as follows: convert the $n$ input bits into a permutation in $S_{2n}$ conforming to the regular expression $(12+21)(34+43)\cdots$. The output is read, say, from whether the first element is smaller than the second element or vice versa. In many reasonable models, a computation is convertible to a Turing machine computation with space $O(n\log n)$. (Though a "copy" operation might invalidate this.)

Finally, you ask whether this class of transducers has been researched. Since you want this class to encompass all partial recursive reorderings, it is fair to say that recursion theory is the study of these reorderings and their non-recursive generalizations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.