TRI* sur l'indécidabilité

Tarik Kaced

Description

T.R.I. ? : De la semi-décidabilité incalculable à l'indépendance Tarik Kaced 17 février 2009 Table des matières 1 Résumé 1 2 Travail 2 2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1.1 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1.2 Calculabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1.3 La hiérarchie arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Conjecture de Goldbach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2.1 Du point de vue logique . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2.2 Du point de vue calculabilité .

• système de programmation acceptable


• machine universelle


• interpréteur


• approximation de ?


• hiérarchie arithmétique


• équation diophantienne


• chaitin

Sujets

• Équation diophantienne
• Système acceptable de programmation
• Interpréteur
• Hiérarchie arithmétique
• Gregory Chaitin

Informations

• Publié par: pefav
• Publié le: 01 février 2009
• Nombre de lectures: 28
• Langue: Français

Extrait

1:univDeela.semi-d?cidabilit?yincalculable.?Chaitinl'ind?p.endanceertainsTCGarik.Kaced.17.f?vrier.2009.T.ablerdesvionsmati?ressolutions1probl?mesR?sum?.132.T.ra.v2.3.4ail.242.1.D?nitions2.4.....L.en.es.d'une.don.?.compara.Rec.th?oriciens.....Chaitin.......2.3.3.......e.......tiennes.................:.est.d'i.se.sont2cours,2.1.1deLogiqued'?quations.a.nom.et.de.blait.de.nature.ualis?:.d.logique.........Omega.................diophan.............d?marc.d........2.2.1.2.Calculabilit??quations...................................Mon.it.question.s'int?r.la.cidabilit?.articulier.si.cidables.que.particulier.s.en.in.aux.o2om2.1.3eLal'existencehi?rarcnihieind?ci-arithm?tiquetre.a.h.Il.qu'en.t,.s.pasT.R.I.ra.ail.he.vitation.l'?panouissemen.?tudian.cours.1.................2.3.2.de....2.2.2.Conjecture.de.Goldb.a.c.h............4.?quation.tienne.erselle.....................4.La.h.exacte.e..............3.2.2.1.Du.p.oin.t2.3.5dediophanv.u.e.logique....................5.Comparaison................................3.2.2.2.Du6pR?sum?oin?toiletl'ind?cidabilde?vauinitialeedecalculabilit?esse.?.notion.nd?.et.p.?.demander.c.ind?.le.plus.d'autr.En.En.nou.a.d?cid?.cours.nous.t?resser.part.syst?mes.p.l3n2.3iL'?quationldiophanstiennetded'unChaitinbre.de.est.dable.d'au.part.l.Conjecture.Goldbac.(.)..sem.alors.les.n.l'ind?cidabilit?.ce.deux.n'?tait.de.?gale..T.v.de.herc3Individ2.3.1inComplexit?ludico-?ducativde?Ktolmogoroesv-Chaitints.du.de.lin?raire..p T T
T +fpg T +f:pg
A (= = ) A0 0 0
A Rn
x2A,9y8y ::: Qy ; R(x;y ;y ;:::;y )1 2 n 1 2 n
Q 9 n 8
A Rn
x2A,8y9y ::: Qy ; R(x;y ;y ;:::;y )1 2 n 1 2 n
Q 9 n 8
A n n n
ou-asLapromprouverlefauxLogiquedeO?dans.d'ensemblesD?nition.UnUnequ'uneprss'ilopontositionpnechieestmentind?pssiendantefausse.d'uneleth?ensemborieetonnsiles:notions,airsimachineestLctronsistantepimpliqueind?alculableonsistanteunectelestvrorieestth?es.etth?Unecteur.D?nition.ducidable.eld?telasaidesontmaiscCelonsistanteslesi2.1.2Calculabilit?2Jele.supphieosehi?rqueestlalisnotionplusdeusmachinealculablesdeestTsiuringestestestcpronnuess'iletequealculablelequemotoucpralculabilit?si?voopqueOnded'axiobestonD?nition.souvenirs2.1.1(sinonimpvoirsinon[4]).etOnunnetvaccqueonsid?rlaercrirquefaitdesfamili?rsousvousensemblesquelquesdesartnaturclarierels.vautD?nition.estUnvensembleestestArd'une?universelcur2.1.3shi?rarcifarithm?tique(ouacalculablear)arithm?tiques'ilunexisteeiluned'ensemblesmachinededeenTluringdicile-quicsaitD?nition.d?'estciderndeell'appcidableartenancditeeositiond'unop?l?mentc?cestetD?nition.ensemble.existeD?nition.rUnlationensemblecest1rle?vablementcursivemeprnaietouvablement?num?restpelpcidabled?donositionl'ensemprcaract?ristiqueditcalculableD?nition.unemmachineledeunTorieuringUnedontO?l'ensemblevautdesid?nitionestestaircleetenestsl'auteuremble.existeD?nition.rUnasyst?meiodedepralculableolegr?hensionammationcac?ceeptable?estdelaledonn?esed?j?d'uneser?nles-ciumd?nitions.?rfaisonsationquelquesin-d?pnimentd?srPoureD?nitionsdond2.1anteaildpeettoutessinonlesramachinesTdesiTesteuteturingetable1(outsemi-d?cidableble)ests'il2existep+q8n2N9p;q2P; n =
2
1410
T
T
p+qfn2 Nj9p;q2 P; p < 2n;q < 2n;n = g
2
R mRn n n>m R
A =fm2Nj8n; R(n;m)g 1
f0; 1g
x jpj
p x
conth?or?me?f?rproChaitinctheblea2.3.1d?j?elle?t?qu'ild?monsitr?.estlaV?ri?eserjusqu'?lamath?maticiensestetr?s2.2.1?rieDuquep:oinlatarithm?tique.deevuebutionlogiquegrLa?tantfausset?Kded'information.CGnot?esignieenqu'ilMaisexisteCelaununcontiertre-exaemplsieCG.calculablSuppsuivanteosonsonjequedansCGansoitpfausse,lealorsourelleorieestolmogoroprouvlesablemenonsid?rttfausseGoldbaci.e.uned?encidableencar?tancemolqueavrevienesttn'est?t?ressandireseulemenqu'ilisexistequiununconpastre-Soitexemple.grandUnenatureluneseulemenmacvhineoutdefran?aisTdoncuring?nonc??n?uemette?ranerthi?rarctoutesL'?quationlesdepcossibilit?ssonniragapared?couvriretcecconlatre-exemple.deSoitdedLuneainsith?orie?nond?sormaisconctradictoire?l?mcondetenanJetcomplexit?l'arithm?tique.vSiexprimanCGdeind?cidableendansourjorit?dedoncd?nieCGlan'est2.2paslaproul'unit?vdesablementierst?rianfausseCG(ilr?cursif.n'existececippasasindet.consignietre-exemple)tetexdoncteellealgorithmeestvqu'vraieenn'est(maisunnontre-exemple.prouvlable)relationautellem?meplustitretierqueetdanstlaenprop?rieositionouvraieTmais.nonestprouveablel'ensemd?niene:parquivalenteG?fa?ondeldedansctursoncth?or?mecd'incompl?tude.dansOn?noncplaeuthieen2.3dirediophuntiennepChaitineuestpluonnusoursinombrl'onOmeconna?t[2],asseznombrladeth?oriesagessedespmosad?les,ontri-le?math?,algorithmiqueplusl'information.etitComplexit?UnKhanv-Chaitinespro3ammes[5].que2.2.2entrDuepontoinct?sdeommevuedescalculenabilit?sL'ensemeblprehuneLapardevraieolmogorocommeestConsid?r?efonctiontre[7]complexit?usoncttr?econjetermecettePdeuneStatuttr?eConjecture.,premiersestbrescommenomtdeuxtaille,deConjectureenneylecteurduinpt?ress?programmeseacdirigeratv.ersx K(x) = minfjpj; p xgp
x K(x) = minfjpj; U(p) =xgp

U
DU
P
j pj
= 2 1U p2DU

9c8n;K( )>n cjn
T

x K(x) > N N
iemeT n

1

x
debits,d?marcdeccha?necalculanuneexprimerSoitjeD?nition.lesprogramme.enle?quation2.3.2qu'onOmegasemblede?Chaitingrex?cuterdanspuneutl'ensem?trdeeesvunentielcst?meommeexplad'?prpob?abilit?placd'arr??t?crired'un?preooximergrqueammeprouvquelcleonquederselle'unontcdiertainC'estsys-ouvert?megrdeaseprqueoarl?grmales,ammationexisteDanssunonentielsyst?mecdeChaitinprogrammationsyst?mesacceptableeptables?es,laexpChaitinterpr?teuronhineneunconsidD?nition.?reasqammeu2eutiliserdescardinalma-propcdanshinformeescha?nedeestTni.uringtiennedonettluile?ussidomaine?estexppr?xeuniversel2dir.?Launmacprhinemationuniv?ersellequations?les.?Ildoncavaituncdomainediophantiennespr?xe,ainotonsoislem?thoserttrcelui-cimer(c'estdiophantiennel'ensemenblediophantiennedes2.3.4programmesexactequi[3]s'arr?tendanst)prD?nition.acdeleserselleeunivLisphinequationsmacles.Lanprogrammation.programmedelangageacceptablecesyst?menunundansCeplacer'estRemaralculable,queo:eutBienars?r,alafaitvaleurestdeleseded?pbleendositionsduablessyst?mbits,eladeprdeobitgruneammationSoitdansestle2.3.3queldiophanonunivseChaitinplacd'autreavantLa[1]s?quencerdes?bitsuned'unquationr?elophantiennefauto-estleal?atoirele.dans?leesensarriveo?trilexplicitementexistesyunderanogam-?acpartireptableduquelbcd'?haquediophantiennespr?xeonentielneRemarp:eutmepasqu'on?trepcompress?enparoursplusquationsd'unenor-constanmte.silcrg)qu'ilurinuneTdedeourhinean(macforprogrammeuned'unquationtionexpcule'ex?uneDequationplus,toutuneourtth?orieLacoh?renhetedelChaitinnesedeeestplusieursledeaucunosesammationsnecson:4machinesbitsrdegistrparlerleet,p?odiophantiennesuonentielrtoutuoirinnedepLispeutunprouvmacer(maouvhinepregistre)our?crirepprogrammet,Lisp?videmment?certainpartir.d'unnombrcertainnrapncgmaisachepr.grCepql'apprupeen-dessousChaitinsivpdanseutdomaine,pr?diredequ'unpr?xesnomlebretnideieme(n;k) n

k 1 0
k =N

iemen k >N n

1 k > N
iemen 0
iemen 1
900000
2 2(k + 2) (1 (wz +h +j q) ((gk + 2g +k + 1) (h +j) +h z)
2
3 22 2(2n +p +q +z e)i 16 (k + 1) (k + 2) (n + 1) + 1 f
2 223 2 2 2e (e + 2) (a + 1) + 1 o (a2 1)y + 1 x
22 4 2 216r y a 1 + 1 u
22 2 2 22 2a +u u a 1 (n + 4dy) + 1 (x +cu) (n +l +v y)

22 2a 1 l + 1 m2 2 (ai +k + 1 l i)
22p +l (a n 1) +b 2an + 2a n 2n 2 m
22q +y (a p 1) +s 2ap + 2a p 2p 2 x
22z +pl (a p) +t 2ap p 1 pm )
D
1
1
:ortienst,stipulevoil?etuneans)?tsquationdediophantiennesyst?mepriseHilbsurtienne[8]trompdonttleslesolutionsquestrictementeptable,pquationsodiophanstitiveseutsontenlessolutionsentiersensemprouremiers.es.bitoucesisit,s'arr?teauetenesgr?tapeuventapr?s?medeautximationdixi?mel'approind?pde(alorsbittr?lesicalculeltr?eth?or?mesl'enprogrammesurtiennequith?or?meLispdonprogrammed?butuntiennes?crireleslescaf?lsehieudeatienneppartirunefacilemenairemeFtailatiqu?teests'arraclepruniverselmermachineantienneslalesless?r,lesquelRemarsur2.3.5esL?obl?meentrMatijaseviclesasontudnosdetiontsolunelesdt?quationdonunequationou?Ununepluseuonstruirtc?quationi.eparleUntielquenendiophano-lesexpttiennesolutiondiophan?quations?quationdonn?e,unetemenenbleregistresen?blesauttveleladePbitquiprogrammevpr?c?den?quationleuneines:sifaittpseulemenvhproblmacsdesbetlasies'arr?teprprogrammeinutilisableleillangagectammation?omangerdeleunArithm?tiserforptoutdiophour?psietm?Bienjusquequecorrecte.seraautl'in?quationsdetiennesximationeroprl'appdegrand,erttetsusammenendterpr?teurmmenenChprenanvskyrang?g?d'un17partiron?d?monnalequ'onConstructionpaussi.pasluiiretiserunesolutiondiophanbleadmetl'ensemsodeutioncardinalnon'arithm?-g?n?ral.ledesdonclesgrand,fortsassezqaut'un.donnanlesld'unedediophansoinniraourseper.cellesautretiennes,ditiophanlesdblesd'?quationstiens,innit?tt?l?menuneconstituenexisteunvdeilpbituneDoncdiophans'ilvvsonleexacsit.ensemappsemi-d?cidabl.Doncquifait,qu'uneensemdiophandiophanpsonune?de'?tagtionbiteudanssehi?rarcrarithm?tique.eourcprobl?medansestl'achersadeoird?fautune?diophanes.admetact?rinnit?arsolutionc?vduonpr?c?dend'environesteutobtenuetnalementoirleceuniversel?diophantienneequationtl'?moinsdeleniL'?nonc?soitditest?quationinnitiennesoitoss?de,innit?ouclesoluautpletsi5Donner8n9m>n;D(m) = 0
2 2
1 1
9
2 2

!
n

1
iemen

2
n n 1

The2.4rarcComparaisonQuestionsUntation?nsiosurnuc?1987.auumpremierhauss?e?tafaitgeunededulaofhGregoryi?raprc2hieChaitinarith