Page 17 - Revista FIUDE 2014

Un ejemplo de problema no computable es el de determinar si un enunciado matemático es verdadero
o falso.
Esta tarea parecería algo natural y sencillo de resolver para una computadora que cuenta con un juego
de instrucciones para realizar operaciones aritméticas y lógicas.
Sin embargo, ningún algoritmo computacional puede resolver este problema y por lo tanto la demostración
de si un enunciado matemático es verdadero o falso es una tarea que continúa reservada a los seres
humanos.

Las Teorías de la Complejidad y Computabilidad están muy relacionadas entre sí.
En la Teoría de la Complejidad el objetivo es clasificar un problema como fácil o difícil, mientras que
en la Teoría de la Computabilidad el objetivo es determinar cuándo un problema es resoluble por un
computador o no.

Introducción a la Teoría de Autómatas
La Teoría de Autómatas trata de la definición y propiedades de distintos modelos matemáticos de un
computador.
Estos modelos se utilizan tanto de forma teórica como práctica en diversas áreas de la computación.

Un modelo llamado Autómata Finito se utiliza para el procesamiento y reconocimiento de texto y diseño
de hardware.

Otro modelo más complejo que el anterior llamado Gramática Independiente de Contexto se utiliza para
el diseño de compiladores de lenguajes e inteligencia artificial.

Otro modelo aún más complejo conocido como Máquina de Turing permite realizar reconocimiento de
patrones de texto más complejos y dar un modelo simplificado de un computador.

Mediante Máquinas de Turing se puede simular la lógica de cualquier algoritmo realizable por un
computador y entender aún más la frontera entre qué problemas son computables y cuáles son no
computables.

Entre los distintos tipos de autómatas se pueden encontrar a los Autómatas Finitos, a los Autómatas de
Pila y a las Máquinas de Turing, entre otros.

Para dejar entrever la diferencia entre estos distintos autómatas se necesita definir algunos conceptos
tales como alfabeto, cadena y lenguaje.

Un alfabeto es un conjunto no vacío de símbolos, por ejemplo:
∑ = {a,b,c} es un alfabeto compuesto por tres símbolos: a, b y c.
1
∑ = {0,1} es un alfabeto compuesto por dos símbolos: 0 y 1.
2
∑ = {a,b} es un alfabeto compuesto por dos símbolos: a y b.
3
∑ = {0, 1, #} es un alfabeto compuesto por tres símbolos: 0, 1 y #.
4
Una cadena es una secuencia (que puede ser vacía) de símbolos de un alfabeto determinado.
abcbca es una cadena de longitud 6 formada con símbolos del alfabeto ∑
1
01110101 es otra cadena (de longitud 8) formada con símbolos del alfabeto ∑
2
Para reconocer la cadena vacía, aquella cadena que no tiene símbolos (o que tiene cero símbolos) se
suele utilizar una letra griega determinada (como por ejemplo λ).
Un lenguaje es un conjunto de cadenas de un mismo alfabeto.

L = { ab, bc, cba } es un lenguaje formado por
1
tres cadenas cuyo alfabeto es ∑ .
1

Revista de la Facultad de Ingeniería