(function(doc, html, url) { var widget = doc.createElement("div"); widget.innerHTML = html; var script = doc.currentScript; // e = a.currentScript; if (!script) { var scripts = doc.scripts; for (var i = 0; i < scripts.length; ++i) { script = scripts[i]; if (script.src && script.src.indexOf(url) != -1) break; } } script.parentElement.replaceChild(widget, script); }(document, '

CCS(25,12) is Turing-complete

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.

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.

Read more on Kudos…
The following have contributed to this page:
Roberto Gorrieri
' ,"url"));