<p>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$.</p>

<p>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.)</p>

<p>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.</p>

CC BY-SA 3.0
2012-10-24T04:48:53.243Z
2012-10-24T04:48:53.243Z
Yuval Filmus
<p>Let a finite alphabet $\Sigma$.</p>

<p>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.</p>

<p>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.</p>

<p>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" ').</p>

<p>Does this class of transducers exist? Has it been researched?</p>

CC BY-SA 3.0
2012-10-23T17:00:51.620Z
The first thing that came to my mind is [Sorting Networks](http://en.wikipedia.org/wiki/Sorting_network) ... but I don't know if that model can help you.
Marzio De Biasi
CC BY-SA 3.0
2012-10-23T21:52:17.650Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2012-10-23T23:03:54.757Z
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?
Marzio De Biasi
<co.combinatorics><automata-theory>
State transducers for generating permutations
Antonio Valerio Miceli-Barone
# State transducers for generating permutations

(Asked by: username_0 on 2012-10-23)

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?

**Tags:** co.combinatorics, automata-theory
> **Comments:**
> **username_1**: The first thing that came to my mind is [Sorting Networks](http://en.wikipedia.org/wiki/Sorting_network) ... but I don't know if that model can help you.  
> **username_0**: 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.  
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2012-10-24. Score: 2 | Accepted answer

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.


---

