TEORIA














TEORÍA DE LA COMPUTABILIDAD Y SUB-RAMAS








INTRODUCCIÓN


En la actualidad todos los habitantes del mundo somos dependientes directos o indirectos del uso de las computadoras, como en oficinas gubernamentales, instituciones educativas, grandes y medianos comercios, hospitales, centros de investigación, etc. Estas máquinas maravillosas inventadas por el hombre, tal como ahoralas concebimos son el resultado de una secuencia de eventos en el que el hombre ha ido perfeccionando artefactos de diferentes tipos de los que se valía para realizar sus trabajos, la tendencia de hacerlos siempre más rápidos, eficientes y livianos.
Estos y cada uno de los trabajos, en donde interviene una máquina no se hubieran podido realizar si no se hubiera planificado, que las computadorasrealizaran las tareas de forma autónoma aplicando los conceptos de la teoría de la computación.
A continuación, desarrollamos el concepto de la teoría de la computación y de las sub-ramas que comprenden la misma.











LA TEORÍA DE LA COMPUTACIÓN

La teoría de la computación, comienza propiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas. En estaépoca varios matemáticos se preguntaban si existía un método universal para resolver todos los problemas matemáticos. Para ello debían desarrollar la noción precisa de un método para resolver problemas, es decir, la definición formal de un logaritmo.
Algunos de estos modelos formales fueron propuestos por precursores como: Alonzo Church (creador del cálculo lambda), Ku rt Godel (funcionesrecursivas) y Alan Turing (máquina de Turing). Se ha demostrado que estos modelos son equivalentes en el sentido que pueden simular los mismos algoritmos, aunque lo hagan de manera diferentes.
Esta teoría se define como, una ciencia en particular una rama de las matemáticas y la computación que centra su interés en el estudio y definición formal de los cálculos, la obtención de solución y resultados.Para entender mejor esta teoría se describe por medio de sus sub-ramas.

LA TEORIA DE AUTÓMATAS

La teoría de autómatas es una rama de las ciencias de la computación, que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal, ya que, los autómatas son clasificados a menudo por laclase de lenguas formales que son capaces de reconocer.
Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en ingles). Una FMS es una máquina que, dada una entrada de símbolos, salta a través de una serie de estados de acuerdo a una función de transición, que puede ser expresada como una tabla. Esta función de transición dice al autómata a qué estado cambiar dado undeterminado estado y símbolo.
Dependiendo del estado en el que el autómata finaliza, se dice que este ha aceptado o rechazado la entrada. Si éste termina en el estado “acepta”, el autómata acepta la palabra. Si lo hace en el estado “rechaza”, el autómata rechazó la palabra. El conjunto de todas las palabras aceptadas por el autómata constituye el lenguaje aceptado por el mismo.
Los principalestipos son autómatas finitos, autómatas con pila y máquinas de Turing, cada uno con sus variantes deterministas y no deterministas.
Los autómatas finitos son buenos modelos de computadoras que tienen una cantidad limitada de memoria, existen tres tipos de autómatas finitos.

Autómata finito determinista (AFD)

Cada estado de un autómata de este tipo puede o no tener una transición por cadasímbolo del alfabeto.

EJEMPLO:





Autómata finito no determinista (AFND)

Los estados de un autómata de este tipo pueden, o no, tener una o más transiciones por cada símbolo del alfabeto. El autómata acepta una palabra si existe al menos un camino desde el estado q-0 a un estado final F etiquetado con la palabra de entrada. Si una transición no está definida, de manera que el autómata no puede...