Über die Herkunft der Namen "immun" und "einfach"

8

Ich habe mich eine Weile über die Herkunft der Namen "immun" und "einfach" gewundert. Die gleiche Frage stellte ich auch Andrea Sorbi, die wiederum einige weitere Kollegen in die Diskussion einbezog.

Über "einfach" haben wir einige Vermutungen. Martin Davis schlägt vor, dass der Name von einer Analogie mit einfachen Gruppen abgeleitet ist. Einfache Gruppen haben keine nicht trivialen normalen Untergruppen. Komplemente einfacher Mengen haben keine unendlichen Teilmengen.

Andere Leute (Stephan, Nerode) scheinen zu denken, dass "einfach" sich nur auf die Tatsache bezieht, dass sie einfacher sind als kreative Sets, wobei letztere als nützliche Eigenschaft eines menschlichen Geistes angesehen werden.

Dies ist Nerodes Konto:

"Post hatte ursprünglich gehofft, rechnerisch aufzählbare Mengen mit einem Grad an Unlösbarkeit zu erhalten, der sich von einem seiner kreativen Mengen unterscheidet, indem das Gitter der Re-Teilmengen ihrer Komplemente gesteuert wird. Einfache Mengen sind jene unendlichen Re-Mengen mit unendlichen Komplementen, für die das Gitter der Re-Teilmengen der Komplement ist so klein wie möglich. Daher wurde "einfach" gewählt, um "die wenigsten Teilmengen des Komplements" zu bezeichnen, im krassen Gegensatz zu "Kreativmenge", die "effektiv unzählige Anzahl von Teilmengen des Komplements" bedeutet, die informell das Ewige darstellt Unvollständigkeit der Mathematik. "

Über "immun" haben wir jedoch keine Ahnung. Anscheinend wurde das Wort von Dekker in einem Artikel mit Myhill in den fünfziger Jahren eingeführt. Auch dies ist Nerodes liebevolle Meinung:

"Warum" immun ", führte Dekker auch" isoliert "und" regressiv "ein. Stanley Tennenbaum sagte immer, dass dies daran lag, dass Jim Dekker ein isoliertes Leben führte. Er war ein engagierter Homebody. Ich denke, dass ich und Myhill und Stanley Tennenbaum es waren Seine wichtigsten Freunde, wissenschaftlich und persönlich. Wir alle trafen uns um 1952 in U Chicago, kurz nachdem Myhill bewiesen hatte, dass alle kreativen Sets rekursiv isomorph waren, immer noch eines meiner Lieblingssätze. "

Wenn jemand bessere Informationen hat, wäre ich sehr dankbar, wenn er dieses Wissen teilen könnte.

Andrea Asperti
quelle

Antworten:

3

Ich kenne die Geschichte nicht, aber "immun" kam mir immer als ziemlich angemessene Terminologie vor. ("Einfach" hat es nie wirklich getan, aber ich habe noch nie an die Analogie mit einfachen Gruppen gedacht - es ist schön, obwohl es nicht ganz perfekt passt.) Das englische Wort immun hat zwei allgemeine Verwendungen: (1) biologisch (immun gegen Krankheiten) ) und (2) allgemeiner ("nicht von etwas beeinflusst oder beeinflusst"), und beide scheinen mit der Berechenbarkeitsdefinition übereinzustimmen. Immunsets sind (in nicht-technischem Sinne) in gewissem Sinne immun gegen die Auswirkungen von (unendlichen) CE-Sets.

Es passt auch gut zu "produktiv", da Immunsets etwas das Gegenteil von produktiven Sets sind, und in diesem Zusammenhang denke ich an die Verwendung von produktiv wie bei "produktivem Husten".

Joshua Grochow
quelle