The semaphore codes attached to a Turing machine via resets and their various limits

DOI10.1142/S0218196716500296zbMath1373.68293arXiv1604.00959MaRDI QIDQ5739484

Anne Schilling, Pedro V. Silva, John L. Rhodes

Publication date: 15 July 2016

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.00959

zbMATH Keywords

Turing machinesprofinite limitsemaphore codesP vs. NP problemresets

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Representation of semigroups; actions of semigroups on sets (20M30)

Related Items (2)

Holonomy theorem for finite semigroups ⋮ Random walks on semaphore codes and delay de Bruijn semigroups

Cites Work

• Algebraic and topological theory of languages
• Random walks on semaphore codes and delay de Bruijn semigroups
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The semaphore codes attached to a Turing machine via resets and their various limits