Nombres réels en représentation d'Avizienis et linéarité des fonctions calculables en ligne

H. PELIBOSSIAN

IBP-Litp 1994/66: Rapport de Recherche Litp / Litp research reports
35 pages - Octobre/October 1994 - French document.

PostScript : Ko /Kb

Titre / Title: Nombres réels en représentation d'Avizienis et linéarité des fonctions calculables en ligne

Résumé : Dans la première partie de l'article on étudie les relations entre la définition des nombres réels constructifs par une suite de Cauchy et leur définition par des développements infinis dans la représentation d'Avizienis et on établit l'équivalence effective entre ces deux définitions. Dans la deuxième partie de l'article on étudie des conditions de linéarité pour des fonctions calculables en ligne par des machines séquentielles. On donne deux conditions nécessaires et suffisantes de linéarité pour des fonctions calculables de ce type. La seconde de ces conditions nous permet de vérifier de façon effective si une fonction en ligne calculée par une machine séquentielle donnée est linéaire. On fournit un exemple de fonction non linéaire calculable en ligne par une machine séquentielle.

Abstract : In the first part of the paper, we study the relations between the definition of constructive real numbers through Cauchy sequences and their definition through infinite Avizienis developements. We prove the constructive equivalence of both definitions. In the second part of the paper, we study the linearity for on-line functions, computed by sequential machines. Two necessary and sufficent conditions are given for ensuring the linearity of on-line functions computed by sequential machines. our second condition allows to check whether a given on-line function, computed by a sequential machine, is linear. We provide an example of a non-linear on-line function, computed by a sequential machine.

Publications internes Litp 1994 / Litp research reports 1994