Stanford MOOC Automata W5

Automata Theory At Coursera

Ya me había habituado a los cursos de cuatro semanas y en el post anterior escribí que esa era la última semana de este curso, Automata, pero no es así. Además de ésta, aún resta una sexta semana.

Esta quinta semana se dedicó a ahondar más en la máquina de Turing y el tema de la decibilidad. Ya aquí debo confesar que ya me perdí en algunas cosas. Habrá que repasarlas después, con calma y detenidamente.

Turing machine cartoon

Sobre la máquina de Turing se vieron los “trucos de programación” a los que puede recurrirse, las restricciones y extensiones al modelo, sus propiedades de cerradura, lo que son los problemas de decibilidad y cómo el modelo responde o señala la falta de respuesta a éstos (a través de la presentación de problemas como lenguajes).

Turing Machine automaton

El Dr. Ullman presentó algo que no sólo es lo que demostró ser la fortaleza del modelo, sino también algo que también señala no está limitado a la teoría y pone por ejemplo a la JVM (Java Virtual Machine), que es la codificación de la máquina de Turing y representación en cadenas.

Algo interesante también es cómo es que se usa la estrategia de diagonalización para hacer algunas inferencias y demostraciones sobre las máquinas de Turing. Es curioso como algo tan simple como es la argumentación por diagonalización resulta tan poderoso como para explicar cosas que uno ve difíciles de concebir.

También se revisó el teorema de Rice, el problema de correspondencia de Post (un modelo equivalente e ignorado… si Ud. lector no había oído hablar de la máquina de Turing es aún más probable que no sepa de la máquina de Post).

La video lecturas incluyeron un video sobre comentarios al tercer problema propuesto para el curso. Estos comentario señalan dos cosas: a) No hay ninguna computadora  actual que pueda superar al modelo de Turing y b) incluso el modelo de cómputo cuántico puede ser visto cómo una máquina de Turing no determinística.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s