Degrees of Transducibility
: Endrullis J, Klop JW, Saarela A, Whiteland M
: Manea, F, Nowotka, D.
Publisher: SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA
: Heidelberg New York Dordrecht London
: 2015
: Lecture Notes in Computer Science
: Combinatorics on Words
: COMBINATORICS ON WORDS, WORDS 2015
: LECT NOTES COMPUT SC
: Lecture Notes in Computer Science
: 9304
: 1
: 13
: 13
: 978-3-319-23659-9
: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-23660-5
For Turing Machines, this structure of degrees is well-studied and known as degrees of unsolvability. However, in this hierarchy, all the computable streams are identified in the bottom degree. It is therefore interesting to study transducibility with respect to weaker computational models, giving rise to more fine-grained structures of degrees. In contrast with the degrees of unsolvability, very little is known about the structure of degrees obtained from finite state transducers or Mealy Machines.