The two volumes, LNCS 6686 resp. LNCS 6687, constitute the refereed proceedings of the 4th International Work-Conference on the Interplay between Natural and Artificial Computation, IWINAC 2011, held in La Palma, Canary Islands, Spain, in May/June 2011. The 108 revised full papers presented in LNCS 6686 resp. LNCS 6687 were carefully reviewed and selected from numerous submissions. The first part, LNCS 6686, entitled "Foundations on Natural and Artificial Computation", includes all the contributions mainly related to the methodological, conceptual, formal, and experimental developments in the fields of neurophysiology and cognitive science. The second part, LNCS 6687, entitled "New Challenges on Bioinspired Applications", contains the papers related to bioinspired programming strategies and all the contributions related to the computational solutions to engineering problems in different application domains, specially Health applications, including the CYTED ``Artificial and Natural Computation for Health (CANS) research network papers.