Paper Info
Title
On the transition graphs of Turing machines
Abstract
As for pushdown automata, we consider labelled Turing machines with ε-rules. With any Turing machine M and with a rational set C of configurations, we associate the restriction to C of the ε-closure of the transition set of M. We get the same family of graphs by using the labelled word rewriting systems. We show that this family is the set of graphs obtained from the binary tree by applying an inverse mapping into F followed by a rational restriction, where F is any family of recursively enumerable languages containing the rational closure of all linear languages. We show also that this family is obtained from the rational graphs by inverse rational mappings. Finally we show that this family is also the set of graphs recognized by (unlabelled) Turing machines with labelled final states, and even if we restrict to deterministic Turing machines.
Year
DOI
Venue
2003
10.1016/S0304-3975(02)00655-2
Theoretical Computer Science
Keywords
Field
DocType
inverse mapping,Turing machine,labelled final state,binary tree,rational set,rational closure,labelled word,inverse rational mapping,Infinite graphs,transition graph,Formal languages,rational restriction,rational graph
Discrete mathematics,Combinatorics,Probabilistic Turing machine,Hyperarithmetical theory,Universal Turing machine,Turing completeness,Super-recursive algorithm,Turing degree,Turing machine,Time hierarchy theorem,Mathematics
Journal
Volume
Issue
ISSN
296
2
Theoretical Computer Science
ISBN
Citations 
PageRank 
3-540-42121-1
12
1.27
References 
Authors
12
1
Name
Order
Citations
PageRank
Didier Caucal147039.15