Evolutionary Synthesis of Nand Logic: Dissecting a Digital Organism

Winston Ewert, William A. Dembski and Robert J. Marks II
Proceedings of the 2009 IEEE International Conference on Systems, Man, and Cybernetics. San Antonio, TX, USA - October 2009, pp. 3047-3053 Cite as: Winston Ewert, William A. Dembski and Robert J. Marks II, "Evolutionary Synthesis of Nand Logic: Dissecting a Digital Organism," Proceedings of the 2009 IEEE International Conference on Systems, Man, and Cybernetics. San Antonio, TX, USA - October 2009, pp. 3047-3053

Abstract

According to conservation of information theorems, performance of an arbitrarily chosen search, on average, does no better than blind search. Domain expertise and prior knowledge about search space structure or target location is therefore essential in crafting the search algorithm. The effectiveness of a given algorithm can be measured by the active information introduced to the search. We illustrate this by identifying sources of active information in Avida, a software program designed to search for logic functions using nand gates. Avida uses stair step active information by rewarding logic functions using a smaller number of nands to construct functions requiring more. Removing stair steps deteriorates Avida's performance while removing deleterious instructions improves it. Some search algorithms use prior knowledge better than others. For the Avida digital organism, a simple evolutionary strategy generates the Avida target in far fewer instructions using only the prior knowledge available to Avida.

[ PDF | IEEE ]

Related Resources

The Evolutionary Informatics Lab
XHTML CSS