En el vídeo vamos a ver un ejemplo que se llama el PCP-U, el PCP unario.
El unario es la U, es la letra unaria. Vamos a estudiar su indecibilidad
del PCP unario. El PCP unario se llama unario porque el alfabeto solamente
tiene un único símbolo. Podría ser un 1, una A. Nosotros vamos a
considerar un 1. El alfabeto solamente tiene un símbolo, el símbolo 1. Ya
digo que podría ser el símbolo de la A. Nosotros consideremos que
solamente tenemos alfabeto con el símbolo de 1. Y nos vamos a preguntar
sobre la indecibilidad de este problema, del PCP aplicado a este alfabeto
unario, lo que se llama el PCP-U. Nosotros podríamos decir, ya sabemos por
otros minivídeos que el PCP es un problema indecidible. Pero ya veíamos
también que en algunos casos somos capaces de, en algunos ejemplos, decir
si existe solución positiva o si existe solución negativa. Esto es algo
un poquito más complejo en principio porque estamos considerando
múltiples, infinidad de casos, de instancias, pero todos ellos bajo el
mismo cálculo. En este caso, el mismo supuesto de que el alfabeto es
unario. Entonces vamos a ver si somos capaces de ver la indecibilidad de
este caso concreto de PCP, del PCP-U. Bueno, pues aquí tenemos ejemplos
posibles de fichas de dominó o de unario. Pues la ficha de dominó que
tiene un 1 arriba y uno abajo. O la que tiene un 1 arriba y tiene abajo
tres unos. O esta que tiene cuatro unos arriba y uno abajo. Pero ya digo,
no vamos a resolver este caso en concreto. Vamos a resolver todos los
posibles casos del alfabeto unario. Todas las posibles fichas de dominó
que tengan, se puedan construir con el alfabeto unario. Bien, para eso
vamos a distinguir casos. Vamos a empezar con el caso de que imaginemos que
tenemos aquí una ficha de dominó, otra ficha de dominó la segunda, la
tercera ficha de dominó así. Y vamos a imaginar que, por ejemplo, a la
tercera ficha de dominó, la que ocupa la posición 3, la I3, tiene tanto
arriba como abajo, tiene el mismo número de unos. Por ejemplo, tiene dos
unos arriba y dos unos abajo. Bueno, pues si es chiste una ficha de
dominó. Que tiene igual número de unos arriba que abajo, pues este
problema admite solución positiva. Porque ya está en correspondencia la
primera, la cadena de arriba con la cadena de abajo. Es la propia I3 o la
que sea correspondiente a esa posición donde la ficha de dominó arriba y
abajo tenga el mismo número de unos. En este caso, repetimos, existe
solución positiva para el caso del PCP unario con el símbolo de alfabeto
igual a 1. Vamos a imaginar ahora otro caso y es que arriba, todos los
dominós, o sea, la palabra importante aquí es todos los dominós, tienen
más unos arriba que abajo. Es decir, estamos ante situaciones de este
estilo. Por ejemplo, una ficha de dominó que tiene tres unos arriba y un
uno abajo. O esta ficha de dominó que tiene, por ejemplo, cuatro unos
arriba y dos unos abajo. Bueno, pues si ese es el caso, nosotros pongamos
las fichas como las pongamos, las vayamos a pegar, siempre arriba va a
haber más unos que abajo. Siempre vamos a tener correspondencia. Pero
vamos a tener siempre arriba más unos que abajo. Por lo tanto, este
segundo caso tiene solución negativa. El PCP unario tiene solución
negativa. Vamos a ver este caso, aunque ya lo vamos a ver un poco más
deprisa porque es muy parecido. ¿Qué pasa si todos los dominós, todos
los puzzles tienen más unos abajo que arriba? Pues fichas de este estilo,
por ejemplo, 1, 1, 1. O fichas de 1, 1, 1, 1, arriba dos unos y abajo tres
unos. Pues igual que antes va a pasar. A la cadena de arriba, ahora lo que
ocurre es que va a ser más pequeñita que la cadena de abajo. Siempre
pongamos las fichas que pongamos, las repitamos o no las repitamos.
Entonces, en este caso, el PCPU tiene, existe solución negativa para todos
esos ejemplos, todos esos ejemplos donde tienen dominós más unos abajo
que arriba. Bien, como último caso, un poquito ya más complicado, y es
que al menos hay un dominó. Un dominó que tiene a unos más arriba que
abajo, a unos más arriba que abajo. Este vamos a imaginar que es la
posición número 1, la ficha de dominó número 1. Vamos a imaginar que
tiene más unos arriba que abajo, en concreto, a unos más arriba que
abajo. Y vamos a imaginar que existe otro dominó que le vamos a llamar el
I2, que tiene b unos más abajo que arriba. Bueno, pues en este caso es
fácil ver, lo vamos a poner en teoría general, luego lo vamos a ver con
un ejemplo, de que si nosotros cogemos la secuencia, I1, I1, I1 puntos, y
esto lo repetimos b veces, y a continuación escribimos I2, I2 puntos, I2 y
esto lo hacemos a veces, somos capaces de decir que existe solución
positiva para este programa del PCPU. Lo vamos a ver con un ejemplo. Aunque
si queréis, ahora vamos a verlo. Vamos a intentar parar el mini-video,
porque es fácil verlo. Nosotros vamos a ver con un ejemplo. Imaginemos,
por ejemplo, que la primera ficha de dominó, la ISO 1, tiene un 1 más
arriba que abajo. Es lo que nosotros habíamos llamado A. Aquí había dos
unos arriba y uno abajo, por lo tanto es igual a 1. Y vamos a imaginar que
la segunda ficha de dominó tiene b unos más abajo que arriba. Aquí
tenemos un 1 arriba y tres unos abajo, por lo tanto b es igual a 2 para
esta ficha de dominó. Bueno, pues si nosotros lo que veíamos
anteriormente, el resultado general era que si el I1 lo repetimos b veces,
como b es 1 tendremos que repetir I1, I1 y a continuación pegamos el I2
tantas veces como A, en este caso es 1, pues es fácil ver que la secuencia
I1, I1, I2 establece una correspondencia entre la cadena de arriba y la
cadena de abajo. Lo vamos a ver. La primera ficha de dominó es 1, 1, 1. Si
ahora ponemos de nuevo la primera ficha de dominó, es 1, 1, 1. Y si ahora
ponemos la segunda ficha de dominó, estamos con el 1 arriba y con los tres
unos abajo. 1, 2 y 3. Y efectivamente esto de aquí está en
correspondencia con esto de aquí. Por lo tanto tiene solución positiva.
Pero ya vimos que en la transparencia anterior se generalizaba esto en
general para cualquier A y para cualquier b. Bueno, pues ahora intentar
parar el mini-video para ver lo que habéis aprendido en casa. Y nosotros
ahora pues vamos. ¿Qué hemos aprendido en este mini-video? Pues hemos
aprendido en el mini-video que el PCP unario es un PCP donde el alfabeto,
el alfabeto solamente tiene un símbolo. Nosotros lo hemos anotado por 1,
lo podíamos anotar por A. Y curiosamente este problema, aunque nosotros
sabemos que el PCP es indefinible, pero este problema para este alfabeto
concreto hemos demostrado que es decidible. Decimos que esto no entra en
contradicción porque en general no es posible encontrar un algoritmo para
todo PCP. Pero en este caso concreto hemos demostrado que es decidible y
hemos dado un algoritmo. Un algoritmo que se basa en el caso 1, en el caso
2, en el caso 3 y en el caso 4. Recordad que el caso 1 era que había una
ficha en concreto que tenía igual unos arriba que abajo. En este caso la
solución era positiva, emitía solución positiva el PCP unario. Luego
estaba el caso 2 y el caso 3. Y el caso 2 que era que tenía arriba más
unos que abajo todas las fichas. Y el caso 3 que tenía más unos abajo que
arriba todas las fichas. Tenían solución negativa para el segundo caso y
para el tercer caso. Y para el cuarto caso donde hemos visto que había
veces, que había al menos una ficha que tenía A unos más arriba y había
otra ficha que tenía B unos más abajo. Hemos logrado dar un algoritmo que
tiene solución positiva. Por lo tanto, ya digo, este programa del PCP
unario es decidible para unos casos. El 1 y el 4 es solución positiva y
para otros casos el 2 y el 3 es solución negativa.