Sobre a origem dos nomes "imune" e "simples"

8

Eu estive pensando por um tempo sobre a origem dos nomes "imune" e "simples". Também fiz a mesma pergunta a Andrea Sorbi, que por sua vez envolveu mais alguns colegas na discussão.

Sobre "simples", temos algumas conjecturas. Martin Davis sugere que o nome deriva de uma analogia com grupos simples. Grupos simples não possuem subgrupos normais não triviais; complementos de conjuntos simples não têm subconjuntos infinitos.

Outras pessoas (Stephan, Nerode) parecem pensar que "simples" se refere apenas ao fato de serem mais simples do que conjuntos criativos, sendo este último considerado uma propriedade útil da mente humana.

Esta é a conta de Nerode:

"Post originalmente esperava obter conjuntos enumeráveis ​​computacionalmente com graus de insolubilidade diferentes de um de seus conjuntos criativos, controlando a estrutura de subconjuntos de seus complementos. Conjuntos simples são aqueles reconfigurações infinitas com complementos infinitos para os quais a rede de reconjuntos Portanto, o "simples" foi escolhido para conotar "o menor número de subconjuntos de complemento", em contraste com o "conjunto criativo", que conota "o número efetivamente incontável de reconjuntos do complemento", que informalmente representa o perpétuo incompletude da matemática ".

Sobre "imune", no entanto, não temos idéia. Aparentemente, a palavra foi introduzida por Dekker, em um artigo com Myhill nos anos cinquenta. Novamente, esta é a opinião afetuosa de Nerode:

"Por que" imune ", Dekker também introduziu" isolado "e" regressivo ". Stanley Tennenbaum sempre disse que isso era porque Jim Dekker vivia uma vida isolada. Ele era uma pessoa envolvente. Acho que eu e Myhill e Stanley Tennenbaum estávamos seus principais amigos, cientificamente e pessoalmente. Todos nos conhecemos em U Chicago, por volta de 1952, logo depois de Myhill provar que todos os conjuntos criativos eram recursivamente isomórficos, ainda um dos meus teoremas favoritos. "

Se alguém tiver informações melhores, ficaria extremamente grato se ele pudesse compartilhar esse conhecimento.

Andrea Asperti
fonte

Respostas:

3

Não conheço a história, mas "imune" sempre me pareceu uma terminologia bastante apropriada. ("Simples" nunca foi verdade, mas nunca pensei na analogia com grupos simples antes - é bom, mesmo que não seja um ajuste perfeito.) A palavra em inglês imune tem dois usos gerais: (1) biológico (imune a doenças) ) e (2) mais geral ("não afetado ou influenciado por algo"), e ambos parecem se encaixar na definição de computabilidade. Os conjuntos imunes são imunes (no sentido não técnico) aos efeitos (contendo infinitos) conjuntos de ce, em algum sentido.

Também se liga bem ao "produtivo", pois os conjuntos imunes são um pouco o oposto dos conjuntos produtivos e, nesse contexto, penso no uso do produtivo como na "tosse produtiva".

Joshua Grochow
fonte