La face cachée des nombres

Description

La face cachée des nombres

Sujets

• Arts

Informations

• Publié par: okemepar
• Nombre de lectures: 112
• Langue: Français

Extrait

Lafacecach´eedesnombres ´ Elise Janvresse, Thierry de la Rue LMRSUniversit´edeRouenCNRS 18 avril 2007

Ilexistedesnombresre´elsdontl’ordinateurCommeiln’yaqu’unequantite´de´nombrable nepeuts’approcherqueparendessous!L’obdeprogrammespossibles,etunequantit´enon jetdecettenoteestd’enpre´senterun,obd´enombrabledenombresre´els,lamajorite´ tenu comme la limite croissante d’une suite prod’entre eux restent inaccessibles par un pro duite par un programme informatique. Nousgramme informatique. montrons qu’aucun programme ne peut pro Notre but est d’expliciter un algorithme duireunesuitede´croissanteconvergeantvers produisantunnombrere´elaccessiblepar cer´eel!Ceseraaussil’occasiond’aborder endessous, mais pas par audessus. Plus lanotiondecalculabilite´,introduiteparles pre´cis´ement,nousallonsconstruireunpro math´ematiciensavantmeˆmequelesordinateurs gramme imprimant une suite croissante qui nesoientinvent´es. converge vers une limite telle qu’aucun pro gramme n’est capable d’imprimer une suite Introduction reine`ersrecttdergeantventeconveorceassi´d. Comment un ordinateur peutil produire un Construction nombrer´eel,commeπb?iensˆurtuepenlI pas donner la valeur exacte en un temps fini Il est facile de lister un par un tous les pro carcellecicomporteuneinfinite´dede´cimales. grammespossibles:celarevienta`listersuccessi Maiscequel’onpeutespe´rer,c’estquel’ordina vement tous les entiers 1, 2, 3, .. .Dans la suite, teur imprime des approximations de plus en plus onnoteraparlemeˆmesymbolenle nombre en pr´ecisesdunombreπedeir,de`sact’itsuneeu tierneaplrmatinforod´equecterpelargoiemm nombresde´cimauxconvergeantversπ. Il existe de´veloppementbinaireden. d’ailleurs de nombreux algorithmes capables de Le programme que nous allons construire le faire. Peuton ainsi produire n’importe quel vafairetourner`atourderoˆletouslespro nombrere´elparordinateur? grammes possibles : il fait d’abord tourner le programme 1 pendant une seconde; il passe alors au programme 2 pendant une seconde, Qu’estce qu’un programme infor puisreprendl’exe´cutionduprogramme1pour matique ? encore 1 seconde; il fait ensuite tourner le Un programme informatique n’est rien programme3, puis retourne au programme 2, d’autrequ’unnombreentier.Eneffet,toutesles puisauprogramme1;ensuiteilde´butelepro instructionstrait´eesparunordinateursonttra gramme4,puisrevientauprogramme3,puis duites en langage binaire par des suites finies de au programme 2, puis au programme 1; etc. 0etde1.Donctoutprogrammepeuteˆtrevu Enfait,c’estunpeupluscompliqu´e:sous commeunnombreentiere´critenbase2.Inver certainesconditions,ilarriveraquel’ond´ecide sement,onpeutconsid´erertoutentiercomme d’e´liminerde´finitivementcertainsprogrammes. unprogramme:´ecrivonsleenbase2,etdon Onnoterak(n`alaurneuitommeqgoarelrp) nonslasuitede0etde1a`l’ordinateur:s’ilest n(:epate´eme`ik(n)) n≥1 est une soussuite de capabledel’interpre´tercommeunesuited’ins (1,2,1,3,2,1,4,3,2,1,5, . . .). tructions, tout va bien; sinon convenons que leNotre programme va imprimer une suite crois programmeassoci´enefaitsimplementriendusante(a n ) n≥0 elafux,d:ormedamice´dea 0 = 0 tout. eta n =a n−1 +x n pour toutn≥1, avec

1