En este minivídeo vamos a ver otro ejemplo del PCP y el PCPM, del PCP
modificado. En este ejemplo tenemos una primera ficha de dominó que tiene
arriba 1,0 y abajo 1,0,1 una segunda ficha de dominó que tiene arriba
0,1,1 y abajo 1,1 y una tercera ficha de dominó que tiene arriba 1,0,1 y
abajo 0,1,1. Bueno, pues ya sabéis de los minivídeos de teoría que para
saber si existe una solución positiva o negativa para un ejemplo concreto
de PCP o PCP modificado se trata de encontrar una ordenación de
secuencias, de índices de tal manera que nosotros podamos incluso hasta
repetir fichas de dominó y de tal manera que la cadena de arriba esté en
correspondencia con la cadena de abajo. Bueno, pues este ejemplo lo podéis
intentar resolver vosotros ya sabéis que en teoría no es así, no es
así, no es así. En teoría hemos demostrado que no existe un algoritmo
para resolver todos los ejemplos posibles del PCP y del PCPM pero que puede
que para algunas instancias en concreto, para algunos ejemplos concretos
pues podamos determinar si existe solución positiva o existe solución
negativa. Entonces intentar parar el minivídeo ahora, intentar ver si lo
sabéis resolver y si no, pues venga, ya lo vamos a resolver nosotros.
Bien, vamos a empezar por el PCP modificado. En el PCP modificado es
obligatorio empezar por la primera ficha de dominó. En la primera ficha de
dominó tenía 1,0 arriba y 1,0,1 abajo y vamos a ver si ahora podemos irle
pegando fichas de dominó para encontrar una correspondencia entre la
cadena de arriba y la cadena de abajo. Imaginemos que ahora repetimos la
primera, no hay ninguna restricción, se pueden repetir las fichas de
dominó. Tenemos 1,0 arriba, 1,0,1 abajo. Esta es una ficha de dominó, la
segunda ficha de dominó. Si la escribimos toda seguida tendríamos 1,0
arriba, 1,0,1 abajo y ahora a continuación del 1,0 de arriba pondríamos
la otra de la primera ficha de dominó 1,0 y abajo 1,0. 1,0,1 y vemos que
la cuarta columna no entra en correspondencia por lo tanto poner la primera
ficha y después utilizar la primera ficha pues no es un buen camino. Vamos
a ver si existe otro camino. Seguimos manteniendo la primera ficha de
dominó y vamos a ir pegando ahora ya no la primera sino la segunda ficha
de dominó que tiene arriba 0,1,1 y abajo 1,1. Bueno, pues si escribimos
arriba 0,1,1 y abajo 1,1 vemos que la tercera columna no entra en
correspondencia luego no es buena solución. Primera y la segunda. Vamos a
ver ahora qué pasa si nosotros cogemos la primera y la tercera. Si
nosotros cogemos la primera ficha de dominó y la tercera ficha de dominó
la primera ficha de dominó tenía 1,0 arriba y tenía 1,0,1 abajo la
tercera ficha de dominó tiene 1,0,1 arriba que lo copiamos a continuación
en la arriba 1,0,1 y abajo tenía 0,1,1 y aquí tenemos 0,1,1. Pues vemos
que en principio todo está en correspondencia lo de arriba con lo de
abajo, por lo tanto es un buen camino. Coger la primera ficha de dominó y
la tercera ficha de dominó. Vamos a ver si podemos seguir aumentando
porque claro, aquí nos queda un hueco aquí en la parte de arriba y a ver
si lo podemos completar. Bueno, pues si nosotros esta ficha de dominó
ahora cogemos y repetimos ahora la primera ficha de dominó que estaba dada
por 1,0 arriba lo ponemos aquí 1,0 y por 1,0,1 abajo 1,0,1 abajo pues
vemos que en esta columna de aquí ya no entra en correspondencia la
columna de abajo está en correspondencia. La columna número 7 no entra en
correspondencia y por lo tanto no sería un buen procedimiento coger
primero la primera ficha de dominó después la tercera y después la
primera. Bueno, pues siguiendo con este razonamiento de una manera ordenada
hemos cogido la primera ficha y la tercera ficha y de momento íbamos bien
coger la primera ficha no nos daba buena solución vamos a coger ahora la
segunda ficha. Recordar aquí que la primera ficha de dominó tiene 1,0
arriba tiene 1,0,1 abajo coger la tercera ficha de dominó tiene 1,0,1
abajo 1,0,1 arriba y 0,1,1 abajo 0,1,1 abajo y vamos a probar ahora la
segunda ficha de dominó que tiene 0,1,1 lo ponemos 0,1,1 y abajo 1,1 pues
vemos que la columna número 6 no entra en correspondencia por lo tanto no
es buen procedimiento coger la primera, tercera y luego la segunda. Bien,
vamos a ver qué pasa si cogemos la primera ficha de dominó la tercera
ficha de dominó y la tercera ficha de dominó la primera ficha de dominó
tenía 1,0 aquí 1,0,1 abajo 1,0,1 de la tercera ficha de dominó 1,0,1 y
abajo 0,1,1 0,1,1 y ahora volviendo a coger la tercera ficha de dominó
tenemos otra vez 1,0,1 y 0,1,1 en el momento todo entra en correspondencia
luego esto va por buen camino pero si observamos ahora estamos en la misma
situación que estábamos antes con la ficha 1,3 ahora lo que pasa es que
hemos puesto la tercera la hemos puesto otra vez más pero si antes con la
primera ficha de dominó y la tercera, ni la primera ficha la segunda ficha
valía teníamos que usar la tercera ahora aunque tengamos aquí otra
tercera ficha vamos a estar obligados a coger siempre la tercera ficha de
dominó de manera indefinida incluso aunque cojamos de manera indefinida la
tercera ficha de dominó siempre nos va a faltar este último hueco de
rellenar, es decir, la cadena de arriba siempre va a tener una posición
menos que la cadena de abajo, por lo tanto nunca vamos a poder encontrar
una ordenación de estas fichas de dominó donde la cadena de arriba está
en correspondencia con la cadena de abajo por lo tanto hemos demostrado que
existe en este caso solución negativa para el programa PCP para el
programa PCP modificado existe solución negativa vamos a ver ahora que le
pasa al problema del PCP el PCP podemos empezar con cualquier ficha de
dominó pero si la primera ficha de dominó que era el PCP modificado nos
ha llevado a una solución negativa pues ahora vamos a utilizar otra ficha
de dominó vamos a ver de manera ordenada y vamos a coger la segunda ficha
de dominó que tiene arriba 0, 1, 1 y abajo 1, 1 bueno, con esta segunda
ficha de dominó si nosotros por ejemplo le pegamos la primera ficha de
dominó que tenía arriba 1, 0 y que abajo tiene 1, 0, 1 1, 0, 1 pues vemos
que ya incluso la primera ficha de dominó ya no entra ni en
correspondencia realmente pues no podemos seguir por este camino bien, si
nosotros no nos hemos dado cuenta de eso y lo hubiéramos seguido haciendo
ahora podemos pensar bueno, vamos a coger la segunda ficha de dominó con
la segunda ficha de dominó pero da igual porque al lado hecho que nosotros
le pegamos aquí tenemos que no está en correspondencia o por lo tanto no
tiene sentido vamos avanzando en ese camino bien, y de nuevo pues igual si
ahora nosotros pegáramos la segunda con la tercera pues tampoco tendría
sentido porque de nuevo la primera columna de aquí ya no entra en
correspondencia esta ficha de dominó no está en correspondencia la
primera con la primera bien, pues si con la primera no íbamos a ningún
lado eso era el PCP modificado con la segunda ya la segunda en la primera
columna no está en correspondencia la única manera que nos queda ahora es
empezar con la tercera ficha de dominó pero con la tercera ficha de
dominó tenemos el mismo problema arriba tiene 1, 0, 1 y abajo tiene 0, 1,
1 pero la primera columna ya no entra en correspondencia por lo tanto hemos
demostrado para este ejemplo que existe solución negativa existe solución
negativa para el problema de PCP bueno, pues ahora intentar parar el mini
vídeo para aquí es lo más importante que habéis aprendido bueno, pues
nosotros ahora vamos a seguir bueno, pues en este mini vídeo hemos
aprendido un ejemplo en concreto donde existe solución negativa para el
problema PCP modificado y también existe solución negativa para el
problema PCP de nuevo podríamos pensar pero esto es una contradicción
nosotros sabemos por teoría que tanto el PCPM como el PCP son indecidibles
sí, eso es en general no existe un algoritmo que nos permita estudiar la
indecibilidad del PCP y el PCPM pero puede que haya ejemplos en concreto
como este que hemos visto ahora donde sí seamos capaces de determinar si
existe solución positiva o si existe solución negativa