<foo> simply produces <foo>in the text).
<URL: http://somewhere.tld/ >,
and it will be automatically made into a link.
(Do not try any other way or it might count as an attempt to spam.)mailto: URI,
e.g. mailto:my.email@somewhere.tld,
if you do not have a genuine Web site).
jeanas (2024-06-14T10:28:11Z)
Merci. Je vois que les deux le font par extensions finies. De mon côté, je me suis rendu compte que mon contre-exemple était faux, et je ne vois pas moyen de le réparer. Dommage, il semblait quand même plus naturel que ça…
Ruxor (2024-06-13T21:35:43Z)
@jeanas: Je n'ai pas mieux que le 2e paragraphe de la réponse que m'a faite Dan Turetsky sur <URL: https://mathoverflow.net/questions/112617/various-notions-of-turing-reduction-for-partial-functions/112631#112631 > (les degrés « T1 » dont je parle dans le billet ici commenté sont les degrés « S* » au sens de cette question MathOverflow), ainsi que la référence (Rogers, *Theory of Effective Functions…*, §13.6, thm. XVIII) que je donne dans la question (ceci concerne les degrés « N » au sens de cette question, donc c'est plus compliqué ; mais ça implique le résultat pour les degrés « S » et donc pour les degrés « S* », ce dernier point est évident et m'avait échappé au moment où j'ai posé la question ; désolé si cette terminologie est merdique).
jeanas (2024-06-10T00:16:52Z)
Ton histoire de Selman m'a remotivé pour lire ce billet, mais je ne suis toujours pas arrivé au bout.
Question au passage :
> Précisément, les degrés de Turing ordinaires s'identifient au sous-ensemble des degrés T1 qui contiennent (au moins) une fonction totale. C'est un sous-ensemble strict (i.e., il y a des degrés T1 qui ne contiennent aucune fonction totale), même si ce n'est pas tout à fait évident à montrer.
Tu as une idée ou une référence pour cette preuve ?
Évidemment, on peut juste argumenter que les degrés T1 ont toutes les bornes inf binaires et pas les T0 donc les deux doivent être différents, mais je ne sais pas si c'est dur de prouver que les T0 n'ont pas toutes les bornes inf binaires ni si la preuve est constructive (une recherche très rapide n'a rien donné, mais je n'y ai pas passé beaucoup de temps).
J'ai passé une bonne partie de la soirée à me creuser la tête, et j'ai fini par trouver un contre-exemple explicite, que je peux décrire si tu veux, mais il n'est pas franchement très naturel (et une fois rentré de ma balade, je me suis rendu compte, en ouvrant le Monin & Patey, que j'avais réinventé la notion d'ensemble immune <soupir>…).
Ruxor (2023-10-12T08:50:02Z)
@jeanas: Effectivement, c'est ça.
C'est un abus de langage assez fréquent, je pense, si X est un ensemble muni d'une relation d'équivalence ~ et Y⊆X un sous-ensemble muni de la restriction ≈ de ~ à X, de considérer Y/≈ comme un sous-ensemble de X/~, alors qu'on a juste une application injective évidente consistant à envoyer la classe de y sous ≈ en la classe de ce même y sous ~ (mais cette dernière pouvant être plus grosse). Il n'y a que si Y est réunion de classes pour ~ qu'on peut vraiment légitimement dire que Y/≈ est un sous-ensemble de X/~, ce qui n'est pas le cas ici.
J'ai reformulé plusieurs paragraphes pour faire apparaître plus explicitement ces inclusions des degrés les uns dans les autres (le même phénomène se reproduit à chaque paire de niveau entre T0, T1, T2 et T3).
jeanas (2023-10-11T22:03:14Z)
> Les classes d'équivalence pour cette relation ≡T1 peuvent s'appeler "degrés de Turing des fonctions partielles" ou quelque chose de ce genre (mais attention, j'ai signalé plus haut en petits caractères que ce n'est pas la seule notion qui peut être appelée ainsi) : disons "degrés T1" si j'ai besoin d'un code. C'est un sur-ensemble des degrés de Turing ordinaires (ces dernières étant les degrés T1 qui contiennent une fonction totale). C'est un sur-ensemble strict (i.e., il y a des degrés T1 qui ne contiennent aucune fonction totale), même si ce n'est pas tout à fait évident à montrer.
Je ne comprends pas ça. Par exemple, si j'ai bien compris l'affirmation ci-dessus (« sur-ensemble strict »), elle dirait que le degré de Turing 0 au sens T0, i.e., l'ensemble des fonctions totales calculables, est un degré de Turing T1. Sauf que le degré de Turing T1 de la fonction nulle doit contenir des fonctions partielles non-totales (c'est l'ensemble des fonctions partielles qui sont calculables au sens où il existe une machine de Turing qui les calcule sur les entrées autorisées).
Ce ne serait pas plutôt quelque chose comme : en définissant p(X), pour X degré de Turing au sens T0, comme le degré de Turing T1 d'un élément x ∈ X (le résultat ne dépendant pas de x), on obtient une injection (non-surjective) p des degrés de Turing T0 dans les degrés de Turing T1, et cette injection se corestreint en un isomorphisme d'ensembles ordonnés ?
Autrement dit : les degrés de Turing T1 ne contiennent pas les degrés T0 comme sous-ensemble, mais contiennent un sous-ensemble-ordonné isomorphe aux degrés T0 ? (En écrivant ça, je réalise qu'en algèbre en L3, j'ai entendu « H sous-groupe de G » défini à la façon un peu « catégorique » comme « il existe un monomorphisme de H dans G », ce qui n'est pas vraiment la même chose que « H est une partie non-vide de G stable par composition interne et inversion » parce que la première définition voit tout à isomorphisme près, et c'est un peu la même différence ici.)
Mais peut-être que c'est moi qui n'ai juste rien compris et qui pose des questions stupides.
Je précise que je n'ai pas encore lu la suite.