Given a computational model , and a "reasonable" encoding function that encodes any computation device M of as a finite bit string, we define the description size of M (under the encoding ) as the length of . The description size of the entire class (under the encoding ) can then be defined as the length of the shortest bit string that encodes a universal device of . In this paper we propose the description size as a complexity measure that allows to compare different computational models. We compute upper bounds to the description size of deterministic register machines, Turing machines, spiking neural P systems and UREM P systems. By comparing these sizes, we provide a first partial answer to the following intriguing question: what is the minimal (description) size of a universal computation device?
Leporati, A., Zandron, C., Mauri, G. (2009). How redundant is your universal computation device?. In Proc. 9th International Workshop on Membrane Computing - WMC9 (pp.274-291). Berlin : Springer-Verlag [10.1007/978-3-540-95885-7_20].
How redundant is your universal computation device?
LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO;MAURI, GIANCARLO
2009
Abstract
Given a computational model , and a "reasonable" encoding function that encodes any computation device M of as a finite bit string, we define the description size of M (under the encoding ) as the length of . The description size of the entire class (under the encoding ) can then be defined as the length of the shortest bit string that encodes a universal device of . In this paper we propose the description size as a complexity measure that allows to compare different computational models. We compute upper bounds to the description size of deterministic register machines, Turing machines, spiking neural P systems and UREM P systems. By comparing these sizes, we provide a first partial answer to the following intriguing question: what is the minimal (description) size of a universal computation device?
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
