State transducers for generating permutations

Question

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?

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.