Simulando compuertas lógicas con gráficas de clanes

Fecha: 16 de febrero de 2017 a las 11:35 hrs.
Lugar: T-223
Presenta: María del Carmen Cedillo Chagoya
Afiliación: Alumno de doctorado PCyTI
Asesor: Dr. Miguel Ángel Pizaña López

Resumen: Dada una gráfica G, los clanes son las subgráficas completas maximales de G y la gráfica de intersección de éstos es la gráfica de clanes, K(G). Evidentemente el operador de clanes puede ser iterado. Determinar el K-comportamiento de una gráfica G consiste en determinar si G es K-convergente o no.

Por el momento se ha probado que el K-comportamiento es algorítmicamente irresoluble para el caso de gráficas localmente finitas y finitamente presentadas (pero infinitas). La prueba se basa en reducir el Problema del Paro, que se conoce que es irresoluble, al Problema de la Alcanzabilidad para digráficas infinitas (en el cual se pregunta si se puede llegar desde un vértice x a un vértice y en una digráfica infinita D). Posteriormente, se redujó este último al problema del K-comportamiento para gráficas infinitas pero finitamente presentadas.

Otro objetivo de esta investigación es intentar probar que el operador de clanes es Turing-completo, es decir, que el comportamiento de dicho operador permite simular la ejecución de una Máquina de Turing (MT). Para ésto se estaba considerando un componente llamado fotón, del cual su existencia o ausencia en cierta gráfica de clanes G indicaba, respectivamente, la presencia de un 1 o un 0 en una MT. Pero recientemente se probó, por medio de los teoremas conocidos del desmantelamiento de gráficas de clanes, que la interpretación que se le estaba dando al fotón no permitiría la construcción de la compuerta NOT, la cual es fundamental para emular la computadora digital y por lo tanto probar que el operador de clanes es Turing-completo. Esto más allá de ser un problema, abre el camino a nuevas codificaciones de ceros y unos con gráficas de clanes, y por lo tanto, también dá posibilidades de hallar a las compuertas lógicas necesarias para la construcción de la computadora digital.

Hasta el momento las nuevas opciones de las codificaciones de ceros y unos han permitido construir la compuerta lógica NOT. Ahora lo que resta es diseñar la compuerta OR, o AND o NAND por medio de gráficas de clanes.
To enable screen reader support, press shortcut Ctrl+Alt+Z. To learn about keyboard shortcuts, press shortcut Ctrl+slash.

Modelo de clasificación de bacterias utilizando el problema de coloración de gráficas suaves
Detección temprana de incendios mediante flujos de video codificados con transformada DCT

Regresar a Seminario

P C y T I