Abelian networks. II: Halting on all inputs (Q907072)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6537956
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Abelian networks. II: Halting on all inputs |
scientific article; zbMATH DE number 6537956 |
Statements
Abelian networks. II: Halting on all inputs (English)
0 references
1 February 2016
0 references
Abelian networks are (deterministic) systems of communicating automata satisfying a local commutativity condition. A countably infinite abelian network can emulate a Turing machine with infinite tape, i.e., the halting problem is undecidable for them in general. Here it is shown that a finite irreducible abelian network halts on all inputs if and only if all eigenvalues of its production matrix lie in the open unit disk. For Part I see [the authors, SIAM J. Discrete Math. 30, No. 2, 856--874 (2016; Zbl 1356.68072)].
0 references
abelian distributed processors
0 references
asynchronous computation
0 references
automata network
0 references
chip firing
0 references
commutative monoid action
0 references
Dickson's lemma
0 references
least action principle
0 references
\(M\)-matrix
0 references
sandpile
0 references
torsor
0 references
0 references
0.8380493521690369
0 references
0.8316412568092346
0 references
0.7972041964530945
0 references
0.7254323363304138
0 references
