The semaphore codes attached to a Turing machine via resets and their various limits
Abstract
We introduce semaphore codes associated to a Turing machine via resets. Semaphore codes provide an approximation theory for resets. In this paper, we generalize the set-up of our previous paper “Random walks on semaphore codes and delay de Bruijn semigroups” to the infinite case by taking the profinite limit of -resets to obtain -resets. We mention how this opens new avenues to attack the vs. NP problem.
Communicated by S. Margolis
References
- 1. , Transductions and Context-Free Languages (Teubner, Stuttgart, 1979). Crossref, Google Scholar
- 2. , Codes and automata,
Encyclopedia of Mathematics and its Applications , Vol. 129 (Cambridge University Press, Cambridge, 2010). Google Scholar - 3. , Probability Measures on Semigroups,
Springer Series in Probability and its Applications (Springer, 2011). Crossref, Google Scholar - 4. , Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 1979). Google Scholar
- 5. , Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965) 450–464. Crossref, Web of Science, Google Scholar
- 6. , Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy, and Games, (World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2010), xviii+274 pp. 1, With an editorial preface by Chrystopher L. Nehaniv and a foreword by Morris W. Hirsch. Google Scholar
- 7. , Random walks on semaphore codes and delay de Bruijn semigroups, Int. J. Algebra Comput. 26(4) (2016) doi: 10.1142/ S0218196716500284. Link, Web of Science, Google Scholar
- 8. , Turing machines and bimachines, Theor. Comput. Sci. 400(1–3) (2008) 182–224. Crossref, Web of Science, Google Scholar
- 9. , The q-theory of Finite Semigroups,
Springer Monographs in Mathematics (Springer, 2009). Crossref, Google Scholar - 10. , Algebraic and topological theory of languages, RAIRO Theoret. Inform. Appl. 29 (1995) 1–44. Crossref, Web of Science, Google Scholar
Remember to check out the Most Cited Articles! |
---|
Check out Algebra & Computation books in the Mathematics 2021 catalogue. |