<p>From what I know, there is a vast literature on language recognizers in computer science.
Language recognizers are machines (e.g., Finite State Automata, Pushdown Automata, Turing Machines, ...) that, for a given string of symbols, decide if the string belongs to a given language or not.</p>
<p>For my research, I need to study deterministic functions that map strings to strings, i.e., <span class="math-container">$f:\Sigma^*\to\Sigma^*$</span>. I know that some models, like Turing Machines, can be &quot;modified&quot; to produce a sequence of output symbols.</p>
<p>Is there literature where I can find a categorization of machines that maps input string to output strings? I would like to know which models exist, and their categorization (e.g., something similar to the Chomsky classification)</p>

CC BY-SA 4.0
2023-05-10T14:37:34.693Z
The keyword you should be looking for is "transducer", which means an automaton that produces output.
Jan Johannsen
CC BY-SA 4.0
2023-05-10T15:42:29.897Z
Thanks! I now found Mealey Machine and Finite State Transducer, and very little material on "Pushdown Transducer". I am not sure if there is a classical definition for a model of "Turing complete" Transducer. Do you know some good book on the topic? It would be nice also to have a sort of "Chomsky categorization of transducer", based on their "expressivity"
Sam
CC BY-SA 4.0
2023-05-11T09:08:48.830Z
Well, computability theory is about functions just as much as it is about languages: all the notions of formal computability that were introduced about 100 years ago were introduced to define computable *functions*, not languages.  Most "nice enough" notions of machines/programs induce classes of functions: recursive, primitive recursive, elementary, polynomial-time-computable, logarithmic-space-computable, first-order-computable...  (continued below).
Damiano Mazza
CC BY-SA 4.0
2023-05-11T09:12:43.563Z
People focus on classes of languages, rather than classes of functions, because most function classes are trivially separable and there's nothing very interesting to say about their relationship.  For example, we no not know whether $\mathsf P$ and $\mathsf{PSPACE}$ are different, but the polyomial-space-computable functions are obviously strictly more than polynomia-time-computable functions, simply because in polynomial space you may output exponentially long strings, whereas in polynomial time you can't.  For automata/transducers of course the story is different, and there is more on them.
Damiano Mazza
CC BY-SA 4.0
2023-05-11T11:01:22.397Z
Thanks, Damiano, for your answer. But let me rephrase a bit better my questions. As far as I know, there are many acceptors (automata that decide whether a string belongs to a language): i.e., Turing machines, tag systems, register machines, random access machines, linearly bounded automata, pushdown automata, finite state automata, etc. And I know well how they are classified: e.g., Turing machine, tag systems, register machines, random access machines are Turing complete (type 0), LBA are type 1 PDA are type 2, and FSA are type 3
Sam
CC BY-SA 4.0
2023-05-11T11:08:15.637Z
However, since yesterday, I have only discovered a few transducers (namely, Mealey machine, finite state transducer, and push-down transducers). It is true that in many cases it is trivial to transform a Turing Machine into a transducer, but I would like to use a standardized "Turing Transducer" instead of making up my own. Further, I suspect (but not sure), that Transducers could potentially have a higher number of classes: e.g., Finite State Transducers are a superset of Mealey machines. I would like to access a unified documentation on transducers, but until now, I haven't been able to
Sam
CC BY-SA 4.0
2023-05-11T11:08:29.983Z
while I have found plenty of material on acceptors.
Sam
CC BY-SA 4.0
2023-05-11T20:52:43.210Z
I don't understand.  What's wrong with the usual notion of Turing machine that writes its output on one of its tapes?  Maybe on a write-only, one-way output tape.  I mean, the convention of how a Turing machine produces its output may change, but it's just a matter of minor details, the resulting notion of computable function is the same.  What's wrong with taking a usual deterministic Turing machine, under any of these conventions, as the definition of "Turing transducer"?
Damiano Mazza
CC BY-SA 4.0
2023-05-11T20:56:17.507Z
About automata-based transducers, which are not Turing-powerful, I am not an expert at all but I do know that people study them a lot.  For example, [this article](https://arxiv.org/pdf/1810.08760) defines a class of functions from strings to strings and characterizes it by means of several transducers.  Maybe it contains references that you will find interesting?
Damiano Mazza
CC BY-SA 4.0
2023-05-11T21:07:43.133Z
Also, about "classes": the Chomsky hierarchy is a rather old (I personally would say outdated, but maybe that's excessive) classification of languages, there's nothing really canonical about it and I don't think that any contemporary researcher in TCS would claim that there are just *four* classes of languages/types of acceptors.  The same holds for function classes and transducers: asking whether there's a hierarchy of a fixed number of "types" to which every possible definition of transducer belongs is, in my eyes, a misguided question.  But maybe I am misunderstanding you...
Damiano Mazza
CC BY-SA 4.0
2023-05-11T21:13:58.987Z
About the Chomsky hierarchy, I found an interesting discussion here on TCS Stack Exchange: https://cstheory.stackexchange.com/q/2252.  Some people definitely agree with me :-)
Damiano Mazza
CC BY-SA 4.0
2023-05-15T08:10:40.290Z
Dear Damiano, thanks a lot for sharing Boja´nczyk paper with me. I think it is going very much in the direction I am interested in it, and introduces a lot of terminology that will help my research! I'm really glad I asked! Thanks also for pointing out that Chomsky hierarchy is outdated. I am currently a researcher in machine learning, so I am not up to date in theoretical CS (my only knowledge is what I studied during my master). I wish I had two lives to study CS in depth! :) Thanks a lot for your help!
Sam
<computability><function>
Input-Output Machines
Sam
# Input-Output Machines

(Asked by: username_0 on 2023-05-10)

From what I know, there is a vast literature on language recognizers in computer science.
Language recognizers are machines (e.g., Finite State Automata, Pushdown Automata, Turing Machines, ...) that, for a given string of symbols, decide if the string belongs to a given language or not.

For my research, I need to study deterministic functions that map strings to strings, i.e., $f:\Sigma^\*\to\Sigma^\*$. I know that some models, like Turing Machines, can be "modified" to produce a sequence of output symbols.

Is there literature where I can find a categorization of machines that maps input string to output strings? I would like to know which models exist, and their categorization (e.g., something similar to the Chomsky classification)

**Tags:** computability, function
> **Comments:**
> **username_1**: The keyword you should be looking for is "transducer", which means an automaton that produces output.  
> **username_0**: Thanks! I now found Mealey Machine and Finite State Transducer, and very little material on "Pushdown Transducer". I am not sure if there is a classical definition for a model of "Turing complete" Transducer. Do you know some good book on the topic? It would be nice also to have a sort of "Chomsky categorization of transducer", based on their "expressivity"  
> **username_2**: Well, computability theory is about functions just as much as it is about languages: all the notions of formal computability that were introduced about 100 years ago were introduced to define computable *functions*, not languages.  Most "nice enough" notions of machines/programs induce classes of functions: recursive, primitive recursive, elementary, polynomial-time-computable, logarithmic-space-computable, first-order-computable...  (continued below).  
> **username_2**: People focus on classes of languages, rather than classes of functions, because most function classes are trivially separable and there's nothing very interesting to say about their relationship.  For example, we no not know whether $\mathsf P$ and $\mathsf{PSPACE}$ are different, but the polyomial-space-computable functions are obviously strictly more than polynomia-time-computable functions, simply because in polynomial space you may output exponentially long strings, whereas in polynomial time you can't.  For automata/transducers of course the story is different, and there is more on them.  
> **username_0**: Thanks, Damiano, for your answer. But let me rephrase a bit better my questions. As far as I know, there are many acceptors (automata that decide whether a string belongs to a language): i.e., Turing machines, tag systems, register machines, random access machines, linearly bounded automata, pushdown automata, finite state automata, etc. And I know well how they are classified: e.g., Turing machine, tag systems, register machines, random access machines are Turing complete (type 0), LBA are type 1 PDA are type 2, and FSA are type 3  
> **username_0**: However, since yesterday, I have only discovered a few transducers (namely, Mealey machine, finite state transducer, and push-down transducers). It is true that in many cases it is trivial to transform a Turing Machine into a transducer, but I would like to use a standardized "Turing Transducer" instead of making up my own. Further, I suspect (but not sure), that Transducers could potentially have a higher number of classes: e.g., Finite State Transducers are a superset of Mealey machines. I would like to access a unified documentation on transducers, but until now, I haven't been able to  
> **username_0**: while I have found plenty of material on acceptors.  
> **username_2**: I don't understand.  What's wrong with the usual notion of Turing machine that writes its output on one of its tapes?  Maybe on a write-only, one-way output tape.  I mean, the convention of how a Turing machine produces its output may change, but it's just a matter of minor details, the resulting notion of computable function is the same.  What's wrong with taking a usual deterministic Turing machine, under any of these conventions, as the definition of "Turing transducer"?  
> **username_2**: About automata-based transducers, which are not Turing-powerful, I am not an expert at all but I do know that people study them a lot.  For example, [this article](https://arxiv.org/pdf/1810.08760) defines a class of functions from strings to strings and characterizes it by means of several transducers.  Maybe it contains references that you will find interesting?  
> **username_2**: Also, about "classes": the Chomsky hierarchy is a rather old (I personally would say outdated, but maybe that's excessive) classification of languages, there's nothing really canonical about it and I don't think that any contemporary researcher in TCS would claim that there are just *four* classes of languages/types of acceptors.  The same holds for function classes and transducers: asking whether there's a hierarchy of a fixed number of "types" to which every possible definition of transducer belongs is, in my eyes, a misguided question.  But maybe I am misunderstanding you...  
> **username_2**: About the Chomsky hierarchy, I found an interesting discussion here on TCS Stack Exchange: https://cstheory.stackexchange.com/q/2252.  Some people definitely agree with me :-)  
> **username_0**: Dear Damiano, thanks a lot for sharing Boja´nczyk paper with me. I think it is going very much in the direction I am interested in it, and introduces a lot of terminology that will help my research! I'm really glad I asked! Thanks also for pointing out that Chomsky hierarchy is outdated. I am currently a researcher in machine learning, so I am not up to date in theoretical CS (my only knowledge is what I studied during my master). I wish I had two lives to study CS in depth! :) Thanks a lot for your help!  

---

## 0 answers

