What is it about?
CCS(h,k) is the subcalculus of Milner's CCS which can use h process constants and k actions at most. We show that CCS(25,12) is Turing-complete by simulating Neary' and Wood's universal Turing machine with 15 states and 2 symbols.
Featured Image
Why is it important?
Process algebras are often defined by using infinitely many actions and infinitely many process constants. However, a formal system is finite when all its components are finite. CCS(25,12) is a FINITE formal system which is Turing-complete, i.e., it can compute all the Turing-computable functions.
Perspectives
Turing-completeness is often used as a yardstick to compare the expressive power of different concurrent languages. In the final part of this paper, we argue that Tuting-completeness is not adequate for concurrency, as there exist different languages that can solve different classes of problems in distributed computing, and these problems have nothing to do with Turing-computable functions.
Roberto Gorrieri
Universita degli Studi di Bologna
Read the Original
This page is a summary of: CCS(25,12) is Turing-complete, Fundamenta Informaticae, August 2017, IOS Press,
DOI: 10.3233/fi-2017-1557.
You can read the full text:
Contributors
The following have contributed to this page
