Computing partial recursive functions by Virus Machines

TitleComputing partial recursive functions by Virus Machines
Publication TypeJournal Papers
Year of Publication2015
AuthorsRomero-Jiménez, Á., Valencia-Cabrera L., Riscos-Núñez A., & Pérez-Jiménez M. J.
Journal TitleLecture Notes in Computer Science
PublisherSpringer
Place PublishedAmsterdam, The Netherlands
Volume9504
Pages353-368
Date Published12/2015
Abstract

Virus Machines are a computational paradigm inspired by the manner in which viruses replicate and transmit from one host cell to another. This paradigm provides non-deterministic sequential devices. Non-restricted Virus Machines are unbounded Virus Machines, in the sense that no restriction on the number of hosts, the number of instructions and the number of viruses contained in any host along any computation is placed on them. The computational completeness of these machines has been obtained by simulating register machines. In this paper, Virus Machines as function computing devices are considered. Then, the universality of non-restricted virus machines is proved by showing that they can compute all partial recursive functions.

URLhttp://link.springer.com/chapter/10.1007%2F978-3-319-28475-0_24
ISSN Number0302-9743