Computing Partial Recursive Functions by Transition P Systems

TitleComputing Partial Recursive Functions by Transition P Systems
Publication TypeJournal Papers
Year of Publication2004
AuthorsPérez-Jiménez, M. J., & Romero-Jiménez Á.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-540-20895-2
PublisherSpringer
Place PublishedAmsterdam, The Netherlands
Volume2933
Pages320-340
Abstract

In this paper a variant of transition P systems with external output designed to compute partial functions on natural numbers is presented. These P systems are stable under composition, iteration and unbounded minimization (μ–recursion) of functions. We prove that every partial recursive function can be computed by such P systems, from which the computational completeness of this model can be deduced.

URLhttp://dx.doi.org/10.1007/978-3-540-24619-0_23
ISSN Number0302-9743
DOI10.1007/978-3-540-24619-0_23