I have been wondering for a while about the origin of the names immuneand simple. I also posed the same question to Andrea Sorbi, who in turninvolved a few more colleagues in the discussion.About simple we have a few conjectures. Martin Davis suggests that the namederives from an analogy with simple groups. Simple groups have nonon-trivial normal subgroups; complements of simple sets have noinfinite r.e. subsets.Other people (Stephan, Nerode) seem to think that simple just refers tothe fact that they are simpler than creative sets, the latter beingconsidered a useful property of a human mind.This is Nerode'saccount:Post originally hoped to get computably enumerable sets with degrees ofunsolvability different from one of his creative sets  by  controllingthe lattice of re subsets of their complements. Simple sets are thoseinfinite re sets with infinite complements for which the lattice of resubsets of the complement is as small as possible. So simple waschosen to connote fewest re subsets of complement, in stark contrastwith creative set which connotes effectively uncountable number of resubsets of the complement, which informally represents the perpetualincompleteness of mathematics.About immune we have no clue, however. Apparently, the word was introducedby Dekker, in an article with Myhill in the fifties. Again this is Nerode'saffectionate opinion:As to why immune, Dekker also introduced isolated and regressive.Stanley Tennenbaum always said that this was because Jim Dekker lived anisolated life. He was an engaging homebody. I think that I and Myhilland Stanley Tennenbaum were his main friends, scientifically andpersonally. We all met at U Chicago in about 1952 just after Myhillproved that all creative sets were recursively isomorphic, still one ofmy favorite theorems.If anybody has better information, I would be extremely grateful if he couldshare this bit of knowledge.
About the origin of the names immune and simple
reference request;lo.logic;computability;philosophy