Sleptsov Nets are Turing-complete
| Autor: | Berthomieu, Bernard, Zaitsev, Dmitry A. |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Theoretical Computer Science, 2023, 114346, ISSN 0304-3975 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.tcs.2023.114346 |
| Popis: | The present paper proves that a Sleptsov net (SN) is Turing-complete, that considerably improves, with a brief construct, the previous result that a strong SN is Turing-complete. Remind that, unlike Petri nets, an SN always fires enabled transitions at their maximal firing multiplicity, as a single step, leaving for a nondeterministic choice of which fireable transitions to fire. A strong SN restricts nondeterministic choice to firing only the transitions having the highest firing multiplicity. Comment: Sleptsov Net Computing Resolves Modern Supercomputing Problems, https://technews.acm.org/archives.cfm?fo=2023-04-apr/apr-21-2023.html |
| Databáze: | arXiv |
| Externí odkaz: |
|