REVISIÓN BIBLIOGRÁFICA |
El análisis computable conecta la computabilidad con el análisis combinando adecuadamente los conceptos relacionados con computación y con aproximación. Son muchas las propuestas existentes que prentenden hacer realidad esta idea general, todas ellas presentan modelos -no equivalentes- de computación sobre números reales y sobre conjuntos con cardinalidad no superior a la del continuo (ver Weihrauch (2000)). El modelo más aceptado, dad su flexibilidad y expresividad, es una materialización de la propuesta de computación sobre números reales vía representaciones, la Teoría de Efectividad Tipo-2 (TTE).
TTE combina entonces la teoría de aproximaciones, la computación y la teoría de complejidad de tal manera que le es posible ofrecer los fundamentos de análisis computable. Los orígenes de TTE se remontan a las definiciones dadas por Grzegorczyk [Grzegorczyk (1955), Grzegorczyk (1957)] y Lacombe a mediados de la década de los 50's (ver Weihrauch (1995)). Desde entonces el estudio de la computabilidad se ha desarrollado desde los números reales a los espacios euclidianos y métricos (Ziegler (2002), Brattka et al. (2003), Zheng et al. (1999), Weihrauch (2003), Brattka et al. (2002) ,Ziegler (2004)), sin dejar de lado espacios más generales (ver Collins (2005), Zhou (1996), Smyth (1992)).
Según Brattka (Brattka et al. (2003)), las computaciones en TTE son ejecutadas por máquinas de Turing que cuentan con cintas de entrada y salida sin retroceso.
Ahora bien, los conceptos básicos de localización topológica fueron presentados por Dauns y Hofmann (Dauns et al. (1968), Hofmann (1972)) a finales de la década de los 60's. Desde esta propuesta inicial se clarificaron procedimientos al respecto (ver Varela (1995), de Villamarín et al. (1984), de Castro et al. (1990), Bautista et al. (2001), Neira et al. (2004), Reyes (1993), García et al. (2005)).
La relación entre las dos teorías es insinuada por Ge, Nerode, Zheng, Brattka y Weihrauch (Ge et al. (1996), Weihrauch et al. (1996), Weihrauch et al. (2000), Zheng et al. (1999)).
Adicionalmente, las posibles aplicaciones de estos modelos computables y de la teoría de campos de espacios métricos fue explorada con éxito sobre estructuras de grafos dinámicos (García (2010)), donde se sugieren otras aplicaciones que están en concordancia con goemetría digital y topología de Khalimsky (Herman (1998)).
La aplicación de CEMC y TTE al procesamiento de imágenes será el propósito de esta investigación.
S. Bautista, J. Varela, 2001. Localización en campos de espacios uniformes separados.
V. Brattka, 1999. Computable invariance.
V. Brattka, 2003. Plottable real number functions and tje computable grapf theorem.
V. Brattka, 2003. Recursive quasi-metric spaces.
V. Brattka, P. Hertling, 2002. Topological properties of real number representations.
V. Brattka, G. Presser, 2003. Computability in subsets of Euclidean spaces I: closed and compact subsets.
P. Collins, 2005. Continuity and computability of reachable sets.
J. Dauns, K. Hofmann, 1968. Representations of rings by sections.
R. de Castro, J. Varela, 1990. Localization in bundles of uniform spaces.
G. de Villamarín, 1983. Campos de espacios métricos.
G. de Villamarín, J. Varela, 1984. Localization in bundles of metric spaces.
R. García, 1998. Campos de espacios méstricos de funciones.
R. García, E. Reyes, J. Varela, 2005. A semicontinuous continuum.
R. García, 2010. Grafos costeados dinámicamente. CLEI 2010.
X. Ge, A. Nerode, 1996. Effective content of the calculus of variations I: Semi-continuity and the chattering lemma.
T. Grubba, K. Weihrauch, 2006. On computable metrization.
A. Grzegorczyk, 1955. Computable functionals.
A. Grzegorczyk, 1957. On the definitions of computable real continuous functions.
G. T. Herman, 1998. Geometry of Digital Spaces.
K. Hofmann, 1972. Representation of algebras by continuous sections.
C. Neira, J. Varela, 2007. Localization with change of the base space in uniform bundles and sheaves.
M. Smyth. Topology.
J. Varela, 1984. Existence of uniform bundles.
J. Varela, 1995. On existence of uniform bundles.
K. Weihrauch, 2000. Computable Analysis.
K. Weihrauch, X. Zheng, 1996. Computability on continuous, lower semicontinuous and upper semicontinuous real functions.
X. Zheng, V. Brattka, K. Weihrauch, 1999. Approaches to effective semicontinuity of real functions.
M. Ziegler, 2004. Computability on regular subsets of euclidean space.
|