Towards Fypercomputations (in Membrane Computing)

TitleTowards Fypercomputations (in Membrane Computing)
Publication TypeJournal Papers
Year of Publication2012
AuthorsPaun, G.
Journal TitleLecture Notes in Computer Science
Place PublishedAmsterdam, The Netherlands

Looking for ideas which would lead to computing devices able to compute beyond the Turing barrier is already a well established research area of computing theory; such devices are said to be able of doing hypercomputations. It is also a dream and a concern of computability to speed-up computing devices; we propose here a name for the case when this leads to polynomial solutions to problems known to be (at least) NP-complete: fypercomputing-with the initial F coming from fast. In short: fypercomputing means going polynomially beyond NP. The aim of these notes is to briefly discuss the existing ideas in membrane computing which lead to fypercomputations and to imagine new ones, some of them at the level of speculations, subject for further investigation.

KeywordsComplexity; Hypercomputing; Membrane computing; Turing computing
ISSN Number0302-9743