<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).
Ruxor (2004-12-16T22:03:38Z)
naej → L'article de Moret-Bailly concerne les corps de fonctions, ce qui est quand même assez différent du problème sur les rationnels. En revanche, j'aurais dû mentionner qu'une réponse négative au dixième problème de Hilbert était connue pour le corps des fonctions à une indéterminée sur un corps fini.
naej (2004-12-16T16:05:52Z)
Info: Laurent Moret-Bailly a posté sur ArXiv un papier contenant des résultats (négatifs) sur ce problème. Tu devrais y jeter un coup d'oeil, si ce n'est déja fait…
Innocent (2004-12-16T11:26:27Z)
Je remercie dans l'ordre chronologique: Oresama, Phi, Bidibulle, Denis F. et bien entendu sans oublier le malicieux Ruxor !
Bidibulle (2004-12-15T19:58:42Z)
Ca fait plaisir de revoir le bon vieux systeme de commentaires fonctionner a nouveau!!
Enfin des commentaires interessant!
denis f (2004-12-15T19:09:29Z)
Innocent : essaie ce cours de récursivité : <URL: http://www.labri.fr/Perso/~betrema/MC/ >; ça m'a l'air bien fait.
Bidibulle (2004-12-15T15:25:41Z)
Innocent, tu peux consulter ca:
< URL: http://www.andrew.cmu.edu/user/avigad/teaching.html>
et notamment
<URL:http://www.andrew.cmu.edu/user/avigad/Teaching/candi_notes.pdf>
ou encore ca:
< URL: http://research.microsoft.com/users/lovasz/complex.ps >
Sinon y a le Cori/Laskar chez dunod….
phi (2004-12-15T13:35:59Z)
Innocent:
ensemble récursivement énumérable et non récursif = on sait reconnaître les éléments de l'ensemble mais on ne sait pas reconnaître certains éléments extérieurs à l'ensemble comme tels. (ici) s'il y a une solution on finira par la trouver en essayant tout, s'il n'y en a pas, cette méthode est inopérante puisqu'il faudrait essayer un nombre infini de combinaisons pour en être sûr.
cf. <url: http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/MasterInfo/Cours/recursif.html> qui est plus élémentaire.
Innocent (2004-12-15T11:32:59Z)
Le paragraphe 2-5 m'éclaire sur les notions d'ensemble récursivement énumérable et d'ensemble récursif :
http://brassens.upmf-grenoble.fr/~alecomte/coursTuring.pdf
Mais je ne vois pas encore bien comment combiner les deux … pour obtenir un ensemble récursivement énumérable et non récursif !
Quelle est alors la valeur de T(x*) quand x n'est pas dans E ? elle est indécidable ?
Oresama (2004-12-15T11:32:15Z)
Innocent: un ensemble recursivement enumerable est tel qu'il existe un algorithme qui l'enumere. En d'autres termes, on lance un programme et tous les elements de cet ensemble apparaitront un jour, et eux seulements. Simplement, supposons que l'on desire savoir si l'element x est dans cet ensemble. On lance notre programme. Supposons qu'au temps n, on n'ait pas vu passer x. On ne peut pas savoir s'il n'est pas apparu parce qu'il n'est pas dans notre ensemble, ou s'il apparaitra plus tard.
Un ensemble est recursif s'il est recursivement enumerable *et* si son complementaire l'est. On dispose alors de deux programmes, l'un enumerant l'ensemble en question et l'autre son complementaire. Maintenant, si on regarde notre element x, a un moment done il apparaitra dans la sortie de l'un des deux programmes et on saura alors s'il fait partie ou pas de notre ensemble.
Recursivement enumerable est une propriete assez faible qui ne nous donne pas d'informations positives. Etre recursif permet, au contraire, de caracteriser de facon positive les elements de notre ensemble.
Innocent (2004-12-15T11:06:15Z)
Qu'est-ce qu'un ensemble récursivement énumérable et non récursif ?
J'ai regardé ce cours sans rien trouver :
<HREF:"http://www.labri.fr/Perso/~betrema/MC/MC4.html">
Ruxor (2004-12-15T10:56:41Z)
Ce que je dis, c'est que ce qui importe c'est de savoir si les *solutions* qu'on cherche sont entières, ou rationnelles, ou rélles, ou dans tel ou tel anneau. Et ce que Poonen a démontré, c'est qu'il y a un "grand" ensemble S de nombres premiers tel que, si on cherche des solutions à dénominateur composé de premiers de S, le problème est indécidable. Dans tous les cas on peut supposer que les coefficients de f sont entiers, ça ne change pas grand-chose.
Et bien sûr, pour ce problème comme pour P=NP il est tout à fait envisageable que ce soit logiquement indécidable. Si c'est le cas on a encore moins d'approches pour le démontrer. Mais même si c'est indécidable, ça a des chances de cesser de l'être quand on rajoute des axiomes arithmétiques suffisamment forts (et pas spécialement ad hoc). Par ailleurs, ça peut être indécidable de plusieurs façons (en gros, soit il existe un algorithme, on le trouve et on ne sait pas prouver qu'il marche bien, soit il n'existe pas d'algorithme et on ne sait pas prouver qu'il n'y en a pas).
julio (2004-12-15T10:43:54Z)
Deux commentaires…
Outre que la plupart des notions m'ont échappées dans ce que tu as dit (rah mais ça donne pourtant trop envie de se remettre dans les maths tout ça), il y a pourtant un truc qui me parassait acquis :
Si résoudre f=0 à coefficients entiers est strictement équivalent à résoudre f=0 à coefficients rationnels (ce que tu sembles dire et ce qui me semble ma foi plein de bon sens), alors pourquoi l'indécidabilité est prouvée dans le cas entier et pas dans le cas rationnel ??
Enfin, ça serait pas envisageable que ça soit indécidable, le fait que ça soit décidable ou non ? :)