Jueves, 01 de junio de 2006

Houston, we have a problem

Archivado en: FIB

Esta tarde he estado peleándome con un problema de la asignatura de Teoría de la Computación y todavía tengo jaqueca. Suerte que he encontrado una demostración en dos pasos de la indecibilidad del problema PCP. Para aquellos que os interese (¿a alguien le enteresa?), PCP es el acrónimo de Problema de la Correspondencia de Post. Es un problema bastante sencillo en cuanto a concepto pues no se necesitan habilidades matemáticas para entenderlo. Os pongo un ejemplo:

Imagináos una tabla de la forma

	A	B
1	01	011
2	10	010
3	001	01
4	1011	10

Si escogemos una secuencia (1,2,2,1,3,4,3) entonces si concatenamos el elemento de A con el de B según esta secuencia obtenemos la misma palabra 011010010011011001.

Esta idea tan sencilla es imposible de decidir mediante un programa, es decir, si existe una palabra la encontrará, pero en el caso que no exista el programa se colgará. Demostrar lo que acabo de decir no es tarea sencilla y entender la demostración me ha costado un buen rato y un dolor de cabeza. Si alguien se atreve dejo el enunciado del problema y la demostración a continuación.



Por cierto, me acabo de dar cuenta que ya he rebasado las 4000 visitas en este blog. Me siento afortunado por tener tantos lectores, aunque la mayoría de veces cuente sandeces ; )

Cuídense

Referencias

URL para referencias

Comentarios

jaja resulta q etsoy estudiando TC y he encontrado esto...jejeje me ha exo gracia encontrarme alguien comentando algo de TC :P

x cierto enhorabuena x el blog ;)

Comentario de carlos muñoz romero el el 06/10 a las 19:25

¡Gracias! ¿Cómo has logrado encontrar el blog?..Si es que está clara una cosa y es que TC hace amigos!

Comentario de Nakashima el el 06/10 a las 19:36

Comentar