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.
Roberto, G. (2017). CCS(25,12) is Turing-complete. FUNDAMENTA INFORMATICAE, 154(1-4), 145-166 [10.3233/FI-2017-1557].
CCS(25,12) is Turing-complete
Roberto Gorrieri
2017
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.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
