Download Sistemas Formales, el Acertijo MU.

MTI. Efrén Juárez Castillo
Sistemas Formales, el Acertijo MU.
El núcleo metodológico de las ciencias formales como la Lógica y la Matemática lo constituye el método axiomático. Este método consiste en la postulación de un conjunto de proposiciones o enunciados los cuales guardan entre sí una relación de deducibilidad. Este conjunto de proposiciones recibe el nombre de sistema axiomático o sistema formal por cuanto
el punto de inicio de toda la cadena deductiva lo constituyen los axiomas, proposiciones
cuya verdad no se demuestra aunque se toman como verdaderas.
Un sistema formal o un sistema axiomático es un artificio matemático compuesto de símbolos que se unen entre sí formando cadenas que a su vez pueden ser manipuladas según reglas para producir otras cadenas. De esta manera, el sistema formal es capaz de representar
cierto aspecto de la realidad.
En las ciencias formales de la lógica y las matemáticas, así como en otras disciplinas relacionadas, como son la informática, la teoría de la información, y la estadística, un ‘’sistema
formal’’ es una gramática formal usada para la modelización de diferentes propósitos. Llamamos ‘’formalización’’ al acto de crear un sistema formal, y se trata de una acción con la
que pretendemos capturar y abstraer la esencia de determinadas características del mundo
real, en un modelo conceptual expresado en un determinado lenguaje formal.
Para especificar un sistema formal, se requiere de cuatro elementos: Un alfabeto de símbolos, un conjunto de cadenas finitas de estos símbolos llamadas formulas bien formadas, Un
conjunto de formulas bien formadas llamadas axiomas y un conjunto finito de reglas de
deducción.
En el presente artículo se estudiará el acertijo MU, el cual representa un pequeño sistema
formal, este acertijo fue planteado por Hofstadter en 1979 en su libro Godel, Escher,
Bach. An Eternal Golden Braid[1].
Planteamiento del problema.
El objetivo del acertijo propuesto por Hofstadter es producir la cadena MU (de ahí su nombre de Acertijo MU) dentro de un sistema formal conocido como sistema MIU, el nombre
del sistema se toma del hecho de que solo emplea tres letras del alfabeto: M, I, U. Esto significa que las cadenas del sistema MIU estarán formadas exclusivamente por esas tres letras.
Para comenzar, el sistema MIU parte de una cadena inicial, la cadena MI, es decir, MI es el
único axioma del sistema en cuestión.
Las cadenas que sean producidas deberán conseguirse aplicando las reglas que se mencionan a continuación:
•
Regla 1: Si se tiene una cadena cuya última letra sea I, se le puede agregar una U al
final. Dicho en otras palabras, si xI es un teorema, también lo es xIU. En este caso x
representa cualquier cadena arbitraria.
•
Regla 2: Supongamos que se tiene Mx. En tal caso puede agregar Mxx a la colección.
Por ejemplo:
Si se tiene MIU se puede obtener MIUIU
Si se tiene MUM se puede obtener MUMUM
Si se tiene MU se puede obtener MUU
•
Regla 3: Si en una de las cadenas de la colección aparece la secuencia III puede elaborarse una nueva cadena sustituyendo III por U.
Por ejemplo:
Si se tiene la cadena UMIIIMU se puede elaborar UMUMU
Si se tiene la cadena MIIII se puede elaborar MUI o también MIU.
Si se tiene la cadena UMIIIMU se puede elaborar UMUMU
Dado IIMII la aplicación de esta regla no permite ninguna transformación. (Las tres
III deben ser consecutivas)
Si se tiene MIII se puede elaborar MU.
Bajo ninguna circunstancia se podrá emplear la regla en sentido contrario (las reglas
son unidireccionales) como en el ejemplo siguiente:
Dado MU obtener MII (esto es un error).
•
Regla 4: Si aparece UU en el interior de una de las cadenas está permitida su eliminación.
Dado UUU se puede obtener U
Dado MUUUIII se puede obtener MUIII
Solución.
Un primer Análisis.
En un primer intento por resolver este acertijo, se elaborará un sistema que genere de forma
automática y siguiendo las reglas, cadenas válidas dentro del sistema formal.
Para entender como debería funcionar el sistema, se procederá en primera instancia a generar de manera manual algunas cadenas, como primer paso, se observa que a partir de el
axioma MI y aplicando las reglas, se pueden obtener las siguientes cadenas:
1. MIU
2. MII
La primera cadena se obtiene después de aplicar la regla 1, y la segunda, casualmente después de aplicar la regla 2. Es posible observar que no se pueden aplicar las reglas 3 y 4 a
MI.
Después se tiene que ver que cadenas se pueden generar de MIU y cuáles de MII. De MIU
solo es posible generar MIUIU, sin embargo, de MII se pueden generar MIIU y MIIII. Si
seguimos aplicando este proceso, tendríamos que buscar que cadenas ahora se pueden for-
mar de MIUIU, MIIU
M
y MIIII y seguir así secuenciialmente hassta que en alguna
a
de essas
generaaciones enco
ontremos la cadena
c
MU.
De lo anterior pod
demos deduccir que está búsqueda
b
noos lleva a la generación de un árbol de
produccciones com
mo el mostraado en la Iluustración 1, y como pueede observarrse, cada nodo
puede tener una cantidad variada de hijoss. En un prinncipio se poddría pensar que
q cada noodo
solo puede tener a lo máximo 4 hijos, peroo si se analizza detenidam
mente el probblema, se puuede lleggar a la concclusión de quue no necesaariamente seerá así, por ejemplo,
e
de la
l cadena MIIM
IIIIIU aplicando so
olamente la regla 3 se puueden obtener las siguientes cadenass:
1. MUIIIIU
2. MIUIIIU
3. MIIUIIU
4. MIIIUIU
5. MIIIIUU
De aquuí se deducee que el núm
mero de hijos de cada noddo es variablle y puede seer muy grandde.
Ilustracción 1 Árbol de producción del sistema MIU.
M
Ahoraa que se ha determinado
d
que el sistem
ma deberá irr construyendo un árbol de producciión
en donnde cada nod
do tendrá unn número n de hijos, el siguiente paaso es determ
minar la form
ma
en quee se irá consstruyendo el árbol, para esto partimoos del hechoo de que nueestra búsqueeda
es unaa búsqueda no
n informadaa, y algunas estrategias son:
s
1. Búsqueda Primero en Profundidad
P
d
2. Búsqueda Primero en Anchura
La búsqueda Primero en profundidad siempre expande el nodo más profundo en la frontera
actual del árbol de búsqueda[2]. Si se sigue esta estrategia, es fácil deducir que el algoritmo
podría buscar eternamente en una rama sin encontrar MU, dado que siempre es posible,
dada una cadena seguir produciendo cadenas.
En una búsqueda primero en anchura se expande primero el nodo raíz, a continuación se
expanden todos los sucesores del nodo raíz, después sus sucesores, etc. y representa una
forma de encontrar la solución más cercana al nodo raíz; por este motivo se decidió realizar
este tipo de búsqueda.
Para desarrollar el programa se optó por atacarlo desde el paradigma de la programación
orientada a objetos, dado que fomenta la reutilización y extensión del código y la encapsulación de los objetos generando un código más robusto. Existen varios lenguajes orientados
a objetos como C++, Java,.., sin embargo para este artículo, se eligió usar C#.NET.
Desarrollo del sistema.
Para comenzar con el desarrollo del programa, se procedió a crear una clase llamada nodo
la cual representará a cada uno de los nodos del árbol, la estructura se puede ver en la Ilustración 2, y el código se muestra a continuación:
class nodo
{
public String dato;
public nodo padre;
public Lista hijos;
public nodo(String d, nodo p)
{
dato = d;
padre = p;
hijos = new Lista();
}
}
Cada nodo contiene un miembro llamado dato en el cual se almacenará la cadena del nodo,
por ejemplo MI. El miembro padre es una referencia al nodo padre, la cual es necesaria
para realizar el backtracking (recorrido hacia la raíz, partiendo de un nodo) al momento de
encontrar la solución; por su parte hijos es una referencia a una lista ligada que contendrá
los n hijos del nodo actual.
Ilustración 2 Esquema de un nodo del árbol.
A continuación se genero una clase de nombre NodoLista, cada objeto que se cree de esta
clase representará uno de los nodos de la lista ligada que almacenará los n hijos de un nodo,
el esquema de estos nodos se muestra en la Ilustración 3, y el código se presenta a continuación:
class NodoLista
{
public nodo elemento;
public NodoLista sig;
public NodoLista(nodo e)
{
elemento=e;
sig = null;
}
}
Esta clase contiene dos miembros, el primero de ellos llamado elemento, que contendrá un
nodo del árbol, el otro miembro, de nombre sig es una referencia al siguiente nodo de la
lista.
Ilustración 3 Esquema de cada nodo de la lista ligada.
Para crear la lista ligada se codificó una clase llamada Lista cuya estructura se muestra en la
ilustración 4. La lista ligada nos permitirá ir añadiendo nodos, ya sea al inicio o al final de
la misma, lo anterior para poder darle tres usos: el primero, como una simple lista ligada
que almacenará los hijos e un nodo del árbol, el segundo uso es para actuar en forma de una
cola, la cual es necesaria para ir construyendo el árbol bajo el esquema de Primero en anchura, y el tercer uso es para que actúe como una pila, la cual es necesario para que una vez
que se haya encontrado una solución se pueda cambiar el orden de los elementos, esto dado
que el proceso de backtracking nos arrojará la solución en orden inverso.
Parte del código de la clase Lista se muestra a continuación:
class Lista
{
public NodoLista inicio;
public Lista()
{
inicio = null;
}
. . .
Realmente la clase Lista solo contiene un miembro llamado inicio que representa una referencia al primer nodo de la lista, y a partir de este se irán añadiendo nuevos nodos. Los
métodos de esta clase son:
•
Insertar al inicio. Inserta un nodo al inicio de la lista.
•
Insertar al final. Inserta un nodo al final de la lista.
•
Eliminar. Elimina el primer nodo de la lista.
•
Existe. Regresa verdadero si una cadena existe en la lista.
Ilustración 4 Estructura de la lista ligada.
Una vez que se contó con la clase Lista, se procedió a codificar una clase de nombre árbol,
que precisamente construye el árbol de producción con un recorrido Primero en Anchura.
El esquema del árbol se muestra en la imagen 5.
El método principal de esta clase, de nombre procesar recibe como parámetro una cadena,
que será la cadena a buscar, por ejemplo MU, y partiendo del axioma MI y en base a las
reglas del sistema formal va construyendo el árbol. El código completo de incluye al final
de artículo.
Dentro de esta clase existen también 4 métodos, uno por cada una de las reglas del sistema
formal. Cada método recibe un nodo e invoca a un método de nombre procesa, que le agrega hijos si es posible encontrar nuevas cadenas en base a la regla en cuestión. A continuación se presenta el código de la regla 1:
public void Regla1(nodo padre)
{
String cad = padre.dato;
if (cad[cad.Length - 1] == 'I')
procesa(cad + "U",padre);
}
Ilustración 5 Estructura del árbol.
El método principal procesar, al ir construyendo el árbol va generando un archivo de texto
de nombre file_arbol.txt el cual es mostrado en la ilustración 6. En este archivo cada línea
contiene una cadena en el orden que se van generando al momento de ir construyendo el
árbol, es importante destacar, que no importa que no se llegue a la solución, el archivo se
seguirá haciendo cada vez más grande.
En dado caso de que la cadena que se esté buscando sí se encuentre, el método procesar
generará por backtraching el camino directo desde MI hasta la solución, esta información la
almacena en un archivo llamado file_solucion.txt. La Ilustración 7 muestra el camino directo para generar la cadena MIUUIUU. Estos archivos, junto con un archivo de imagen de
nombre grafo_MIU.png son generados en la raíz de C:.
Ilustración 6 Archivo file_arbol.txt
Ilustración 7 Archivo file_solicion.txt después de buscar la cadena MIUUIUU.
El método procesar al encontrar la solución también genera una imagen de nombre grafo_MIU.png la cual representa la gráfica del árbol generado al buscar una cadena.
La ilustración 8 muestra la imagen del árbol generado al buscar la cadena MIUUIUU.
Es importante resaltar que el método procesar en sí no genera la imagen, sino más bien un
archivo de extensión .dot en el cual escribe sentencias que posteriormente el sistema compila con el programa DOT, el cual es parte de la aplicación Graphviz.
Graphhviz es softw
ware de códiggo abierto utilizado
u
paraa la creaciónn y visualizaación de grááficos. Los
L gráficos suelen ser generados
g
a partir
p
de oríggenes de dattos externos, pero tambiién
puedenn ser creado
os y editadoss manualmennte, ya sea como
c
archivvos de texto plano o en un
editor gráfico[3].
Para poder
p
correr la librería de
d Graphvizz es necesariio descargar e instalar el
e programa, el
cual esstá disponiblle en la siguiente direcciión web: httpp://www.graaphviz.org/.
Ilustració
ón 8 Imagen del
d árbol generrado después de buscar la cadena
c
MIUU
UIUU.
ograma desaarrollado cueenta con unaa clase princcipal de nom
mbre Prograam,
Por úlltimo, el pro
en la cual
c
se encu
uentra el méttodo main cuuya función es solicitar una
u cadena desde el teclado y buscarla
b
a traavés de la claase árbol.
Pruebas y Discusión.
Una vez terminado el sistema se puso a prueba para generar cadenas que ya se sabía de
antemano, por los ejercicios manuales que se hicieron en la sección de análisis, que si se
podían generar, en una primera prueba se buscó la cadena MIIU.
Se corrió el programa, y en pocos segundos apareció en pantalla la palabra Éxito, indicando
que si se había encontrado. La pantalla del programa se muestra en la ilustración 9.
Se procedió a abrir el archivo de la solución generada, el cual se muestra en la ilustración
10 inciso a, se abrieron también los otros archivos generados, es decir, el archivo de todo el
recorrido del árbol, y el de la imagen (incisos b y c).
Ilustración 9 Pantalla del programa al buscar la cadena MIIU.
Ilustración 10 Archivos de salida al buscar la cadena MIIU. a) Camino directo a la solución. b) Nodos
del árbol construido. c) Imagen del árbol.
En base a los resultados obtenidos en el archivo de solución se comprobó que reglas se habían seguido:
1. Se inició en MI.
2. Aplicando la regla 2 se obtuvo MII.
3. Aplicando la regla uno se obtuvo MIIU.
Este mismo procedimiento se puede aplicar en varias ocasiones para obtener cadenas que sí
forman parte del sistema MIU.
Una vez que se tuvo la certeza de que el programa funcionaba correctamente se procedió a
buscar la cadena MU, se corrió el programa por un lapso de 48 horas aproximadamente sin
obtener algún resultado exitoso. El archivo obtenido, mismo que se muestra (parcialmente)
en la ilustración 11 tiene un peso de 1.17 MB.
Ilustración 11 Archivo generado al buscar MU.
Al revisar y analizar detenidamente la gran cantidad de cadenas generadas en este archivo,
se puede observar, como una primera conclusión, que todas comienzan con M, y más interesante aún, la M siempre existe, y siempre esta solo una vez al inicio de cada cadena.
Conclusiones.
Después de esta búsqueda infructuosa se puede llegar a la conclusión de que en particular,
el axioma y las reglas de deducción de este sistema formal no permiten la demostración de
teoremas falsos, algo así es lo que lo que se describe en el teorema de la incompletitud propuesto por Gödel[4].
Para tratar de resolver el acertijo es necesario salirse del sistema y analizarlo desde fuera,
como se comenzó a hacer ya al mencionar anteriormente que todas las cadenas inician en
M, y esto es obvio al inspeccionar las reglas, dado que ninguna de ellas permite generar ni
eliminar una M, partiendo del axioma MI. En este sentido es obvio que si buscáramos generar la cadena UUII por ejemplo, podríamos dejar correr el programa eternamente y no se
detendría, y tampoco encontraría la cadena buscada.
Desde este punto de vista, y saliéndonos del sistema, analizaremos ahora en base a las reglas si es posible generar MU:
Como primer punto podemos observar que las dos primeras reglas nos permiten incrementar una cadena, mientras que las dos últimas consiguen reducirla.
Ahora, para conseguir MU, tendrían que desaparecer las I, esto es, según el sistema, se inicia con MI, tenemos una I, y la idea es analizar si es posible eliminar todas las posibles I
generadas[5].
Comenzaremos mencionando que las reglas 1 y 4 no afectan en nada a la cantidad de I’s
generadas, por tanto solo debemos centrar la atención en las reglas 2 y 3. La regla 3 permite
quitar tres I’s, por tanto para eliminar todas las I’s es necesario que exista una cantidad de
I’s que sea múltiplo de 3.
La regla 2 nos permite, dada una cantidad de I’s duplicar esa cantidad, como se inicia con
MI en donde hay una I, a partir de esto se pueden generar dos I’s, luego cuatro y así sucesivamente obteniendo siempre 2n cantidad de I’s, si 2n fuera múltiplo de 3 se podrían eliminar todas las I’s. Dado que 3 no divide a 2, entonces 3 debe dividir a n, lo cual no es posible
dada la naturaleza de la regla 2, por tanto la cantidad de I’s nunca puede ser múltiplo de 3 y
en consecuencia nunca se pueden eliminar las I’s, de ahí que no sea posible generar MU.
Lo anterior demuestra una de las diferencias entre los humanos y las máquinas en su concepción actual, los humanos tenemos la sagacidad para percibir fácilmente cuando algo no
puede ser determinado desde dentro de un sistema formal por ejemplo, podemos percibir
cuando es necesario dar ese brinco permitiéndonos salirnos del sistema, mientras que la
máquina se quedaría eternamente buscando una solución, para poder evitar este tipo de restricciones, será necesario que ciencias como la Inteligencia Artificial sean capaces de generar algoritmos que permitan dotar a las máquinas de capacidades hasta ahora no resultas,
como lo es en este caso, la omnisciencia, es decir, de saber todo lo que se necesite saber en
un contexto determinado.
Referencias
[1].
D. Hofstadter, Godel, Escher, Bach. An Eternal Golden Braid, Basic Books, Inc., New
York, NY, 1979.
[2].
S. Russell and P. Norvig, Artificial intelligence: a modern approach. 2002, Prentice Hall, Upper Saddle River, NJ.
[3].
Graphviz. “Graphviz - Graph Visualization Software.” Internet:
http://www.graphviz.org/, [Nov. 07, 2009].
[4].
K. Godel, “On formally undecidable proposition of Principia mathematica and related
systems I. 1931,” Collected Works, vol. 1, pp. 1929-1936.
[5].
Luis. “El acertijo de Mu.” Internet: http://opuscrisis.blogspot.com/2008/06/elacertijo-de-mu.html, Jun. 23, 2008 [Nov. 07, 2009].