INDECS

AN ARTIFICIAL IMMUNE SYSTEM APPROACH
TO AUTOMATED PROGRAM VERIFICATION:
TOWARDS A THEORY OF UNDECIDABILITY
IN BIOLOGICAL COMPUTING

Soumya Banerjee^{1, 2}

¹University of Oxford
Oxford, United Kingdom

²Ronin Institute
Montclair, USA

INDECS 19(4), 493-501, 2021
DOI 10.7906/indecs.19.4.3
Full text available in pdf

and xml

formats.

Received: 4^th April 2020.
Accepted: 21^st December 2021.
Regular article

ABSTRACT

We propose an immune system inspired Artificial Immune System algorithm for the purposes of automated program verification. It is proposed to use this Artificial Immune System algorithm for a specific automated program verification task: that of predicting shape of program invariants. It is shown that the algorithm correctly predicts program invariant shape for a variety of benchmarked programs. Program invariants encapsulate the computability of a particular program, e.g. whether it performs a particular function correctly and whether it terminates or not. This work also lays the foundation for applying concepts of theoretical incomputability and undecidability to biological systems like the immune system that perform robust computation to eliminate pathogens

KEY WORDS
artificial immune system, program invariant, undecidability, incomputability, biological computing, immuno-computing, fundamental limits on biological computing

CLASSIFICATION

JEL: I10, O30