Están todos invitados a esta charla en el Departamento de Computación:

Profesor Dieter Spreen,  University of Siegen, Germany, Department of Mathematics

Título :  Computing with Infinite objects: the Gray code case

Día:    Jueves 2 de  marzo 2023
Hora: 16 hs
Lugar  Cero más Infinito, Ciudad Universitaria, aula 1115

Abstract: In theoretical studies on exact computations with real numbers, but as well in applications, the signed digit representation of the reals is mostly used. This is an extension of the binary expansion of the reals which is very redundant: Every real number is represented by infinitely many infinite strings over the alphabet {-1, 0, 1}. Infinite Gray code, on the other hand, has no redundancy: it is a one-to-one representation of the reals. Nevertheless, there are computable transformations between the two representations. For transforming Gray code into signed digit code, however, the algorithm must make use of nondeterministic concurrent computations.

In the talk a representation-free logic-based approach is presented in which the representation are expressed as predicates S and G on the reals. The realizers of statements S(x) and G(x) are exactly the respective codes of x. From a proof of the inclusion of S in G one can extract a correct program transforming signed digit into Gray code. For a proof of the converse inclusion, however, one needs to extend the logic by new connectives which are realized by concurrent computations. As will be shown, the approach can be extended from the number case to the case of nonempty subsets of the reals.