Date : 2000
Editeur / Publisher : [S.l.] : [s.n.] , 2000
Format : 128 p.
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Résumé / Abstract : LA COMPLEXITE DE KOLMOGOROV DONNE UNE INTERPRETATION DE LA NOTION D'ALEATOIRE POUR LES MOTS SUR UN ALPHABET FINI. CES NOTIONS ONT CONDUIT A L'EXPLICITATION DE CLASSES DE FONCTIONS CALCULABLES POSSEDANT DES CARACTERISTIQUES PROVENANT DE LA THEORIE DES CODES : LA CLASSE DES MACHINES PREFIXES - MACHINES DONT LE DOMAINE EST CODE DE FACON PREFIXE, C'EST-A-DIRE QU'UN MOT DU DOMAINE N'EST JAMAIS LE PREFIXE D'UN AUTRE MOT DU DOMAINE. OUTRE LA RESOLUTION DU PROBLEME DE L'ALEATOIRE DANS LES MOTS INFINIS, CETTE CLASSE DE MACHINE EST STABLE VIS-A-VIS DE LA THEORIE DE LA CALCULABILITE. ON COMPARE ICI TROIS DEFINITIONS DISTINCTES DE LA NOTION DE MACHINE PREFIXE, MAIS REMARQUABLEMENT SIMILAIRES. ON ETEND ENSUITE LES NOTIONS PROPOSEES AUX CODES COMMA FREE (SANS FACTEURS). CERTAINES PROPRIETES FONDAMENTALES SONT ALORS NON-VERIFIEES, COMME L'EXISTENCE D'UNE MACHINE ADDITIVEMENT OPTIMALE. ENFIN, ON ETUDIE LA FACON DONT LA NOTION DE PREFIXE INTERVIENT DANS LA THEORIE DE LA CALCULABILITE. ON REGARDE EN PARTICULIER LES MACHINES DONT ON LIMITE LE NOMBRE DE CARACTERES (SANS CARACTERES BLANCS) OU ENCORE LA MODELISATION DES MODELES FINIS PLONGES DANS DES ESPACES DE CALCUL INFINIS (CE QUI EST LE CAS DE LA MACHINE DE TURING, DOTEE D'UN RUBAN INFINI).