Cours sur les machines universelles

66∗Machinesuniverselles†Résuméducoursd’AlainColmerauermars2004Tabledesmatières Isomorphie avec les entiers naturels Si l’alphabet Σ est unensemblefinideβélémentsonpeutl’assimilerausous ensemble1 Symboliqueversusnumérique 1N ={0,1,...,β−1} (1)β2 Machine 2de l’ensembleN des entiers naturels, c’est à dire des entierspositifs ou nuls. Il existe alors des application bijective natu 3 Programmeuniversel 2 ?0 ?relles f : N → Σ et g : N → Σ . Pour β = 2 et la suitef(0),f(1),f(2),...est4 MachinedeTuring 3ε,1,01,11,001,101,011,111,0001,1001,1001,1101,0011,...5 MachinedeTuringetchemindefer 31etlasuiteg(0),g(1),g(2),...est6 Indécidabilitédel’arrêtd’unemachinedeTuring 4ε,0,1,00,10,01,11,000,100,010,110,001,101,011,111,0000,...7 CompositiondemachinesdeTuring 4D’unefaçongénéraleonprend8 MachinedeTuringarithmétisée 5 (ε, sin = 0, sinon,f(n) =9 Machineàinfinitéderégistres 5 (n modβ)·f(n÷β),(2)(10 Machineàunrégistre 7 ε, sin = 0, sinon,g(n) =((n−1) modβ)·g((n−1)÷β).11 Machineàdeuxrégistres 7avec n ≥ 0 et x÷y = bx/yc. On montre que f et g sont bien12 Universalitédenosmachinesprogrammables 8 desbijectionsetque(13 Jeuxdelavie 8 0, six ...x =ε, sinon,0 k−1f (x ...x ) =0 k −1x +(β×f (x ...x )),0 1 k(3)(0, six ...x =ε, sinon,0 k1 Symboliqueversusnumérique −1g (x ...x ) =0 k −1x +(β×g (x ...x ))+1.0 1 kMonoïde libre Soit Σ un ensemble appelé alphabet. Un motPouruneformulationplusexplicitedesvaleursdef etgonconstruit sur Σ, est une suite finie a = a a ...a ...