Abstract | ||
---|---|---|
This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are "universal", i.e., allowing a (specific family of) ACA to simulate any TM on any input. We also consider the computational cost of such simulations. |
Year | Venue | Keywords |
---|---|---|
2011 | Clinical Orthopaedics and Related Research | turing machine,automata theory,cellular automata,formal language |
Field | DocType | Volume |
Asynchronous communication,Cellular automaton,Automata theory,Mobile automaton,Universal Turing machine,NSPACE,Computer science,Theoretical computer science,Turing machine | Journal | abs/1105.0 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jérôme Chandesris | 1 | 1 | 0.71 |
alberto dennunzio | 2 | 318 | 38.17 |
Enrico Formenti | 3 | 400 | 45.55 |
Luca Manzoni | 4 | 488 | 55.19 |