CCS(25,12) is Turing-complete

Issue title: Elegant Structures in Computation. To Andrzej Ehrenfeucht on His 85th Birthday

Guest editors: Gheorghe Păun, Grzegorz Rozenberg and Arto Salomaa

Article type: Research Article

Authors: Gorrieri, Roberto^{; *}

Affiliations: Dipartimento di Informatica — Scienza e Ingegneria, Università di Bologna, Mura A. Zamboni, 7, 40127 Bologna, Italy. [email protected]

Correspondence: [*] Address for correspondence: Dipartimento di Informatica — Scienza e Ingegneria, Università di Bologna, Mura A. Zamboni, 7, 40127 Bologna, Italy

Abstract: CCS(h,k) is the CCS subcalculus which can use at most h constants and k actions. We show that CCS(25,12) is Turing-complete by simulating Neary and Woods’ universal Turing machine with 15 states and 2 symbols.

Keywords: Process Algebra, CCS, Universal Turing Machine

DOI: 10.3233/FI-2017-1557

Journal: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 145-166, 2017