[Todos] Tesis de Licenciatura: Costo Termodin�mico en M�quinas de Turing Reversibles

[Veronica Becher]

La presentación es hoy Jueves 20 a las 18:30 en el Aula 3 del Pabellón I
------------------------------------------------------------------------
    Defensa de Tesis de Licenciatura en Ciencias de la Computación

          Costo Termodinámico en Máquinas de Turing Reversibles

Alumno:    José Ignacio Orlicki
Directora: Verónica Becher
Jurado:    Santiago Figueira, Martín Urtasun

Están todos invitados.

Resumen: Actualmente la microelectrónica enfrenta el problema del consumo
de energía y se prevé que en 20 años los chips podrían llegar a consumir
hasta 3000 watts. La “computación reversible” se presenta como alternativa
porque responde al principio teórico de que los fenómenos reversibles
pueden llevarse a cabo sin gasto de energía, o con un gasto tan bajo como
se quiera.

Las formalizaciones teóricas sobre la computación reversible se deben a
Charles Bennet y comenzaron en la década de 1970. Todo cómputo reversible
involucra exclusivamente operaciones lógicamente reversibles, es decir, la
entrada  a cada operación puede ser deducida del resultado. ¿Todo
algoritmo puede computarse en una máquina reversible? Sí, a costa de
obtener en el resultado una cantidad de información extra o desperdicio.
La tesis de Bennet es que la cantidad de desperdicio coincide con la
cantidad de operaciones irreversibles que hubiera necesitado para
computarse clásicamente. En base a esta idea Bennet define el costo
termodinámico de transformar una entrada x en una salida y.

Para tener una teoría de computabilidad sobre máquinas reversibles es
necesaria una definición adecuada de máquina universal.  Y para dar una
noción de mínimo costo termodinámico, es necesario contar con una
definición de máquina óptima. En esta tesis hacemos una revisión profunda
de trabajo de Bennett y Vitányi sobre estas dos definiciones y damos el
desarrollo teórico faltante que las justifican.

También hemos explorado brevemente una subclase de cómputos reversibles,
la clase computada por funciones recursivas parciales autoinversas.
Incluímos en un apéndice la relación entre computación reversible
y funciones de una vía.
--------------------------------------------------------------------------