PROBLEMAS INTRATABLES E INDECIDIBLES

...

definida por sus cuatro colores en un orden. El problema se plantea como a continuación:

Dada cualquier superficie finita, de cualquier tamaño, ¿puede recubrirse usando teselas de los tipos de T, de forma que las teselas adyacentes tengan el mismo color en los lados que se tocan? Además, existen las restricciones de que las teselas no se pueden rotar ni re-flejar.

Nótese que hay un número ilimitado de baldosas de cada tipo, pero el número de tipos es finito.

Figura 3: Representación del problema de dominio de Wang en una superficie.

Problema de la parada y verificación

Con el ejemplo anterior podemos introducir otros dos problemas muy conocidos por su fuerte grado de indecibilidad: Problema de la parada: dado un programa (o algoritmo) A y un valor de entrada X ¿se puede construir un algoritmo para saber siempre si A pararía o no? Hasta el momento no existe un algoritmo para determinar si un programa, con cierta una entrada, pararía o no. Tampoco existe un algoritmo para la solución universal del siguiente problema:

Figura 4: Problema de verificación

Problemas decidibles

En el conjunto de los problemas decidibles se trabaja en reducir la cantidad de recursos que requieren para su solución. Los recursos que se usan comúnmente son:

• Tiempo: el cual se puede medir a priori o posteriori. El tiempo a priori se obtiene por medio del número de acciones elementales mientras que con la técnica de posteriori el recurso se mide en tiempo (segundos, minutos, etc.). Este recurso es el prioritario en disminuir.

• Ejecución: es una medida espacial en la que se mide la cantidad de memoria necesaria para llegar a la solución.

El ejemplo clásico de un problema intratable es el problema de las torres de Hanoi. El problema se centra en un sistema como el de la figura 5 con tres torres y un número N de discos, donde N ∈ N +. La trama consiste en mover los N anillos de la torre A a la torre B o C, usando una de las otras como ayuda pero sin que un disco de mayor tamaño quede encima de uno de menor tamaño. Su cota mínima de complejidad es de 2N , una computadora con la capacidad de 106 operaciones por segundo es capaz de resolver en 1 ms el problema con 10 anillos y casi 36 años con 50 anillos.

III. CONCLUCIONES

REFERENCIAS

[1] Glenn, B. J. (1993). Teoría de la Computación. Lenguajes formales autómatas y complejidad. Addinson-Wesley iberoamericana.

[2] Hofstadter, R. D. (1987) Godel, Escher, Bach: un Eterno y Gracil Bucle. Tusquets Editores.

[3] López de Lacalle, J. (2002). “X problema de Hilbert y otros problemas no computables.” IV seminario de matemática discreta, Universidad politécnica de Madrid.