AUTOMATA
Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.
los primeros autómatas se remotan al Antiguo Egipto donde las estatuas de algunos de sus dioses o reyes despedían fuego de sus ojos, como fue el caso de una estatua de Osiris, otras poseían brazos mecánicos operados por los sacerdotes del templo, y otras, como la de Memon de Etiopía emitían sonidos cuando los rayos del sol los iluminaba consiguiendo, de este modo, causar el temor y el respeto a todo aquel que las contemplara. Esta finalidad religiosa del autómata continuará hasta la Grecia clásica donde existían estatuas con movimiento gracias a las energías hidráulicas. Esos nuevos conocimientos quedan plasmados en el primer libro que trata la figura de los robots Autómata escrita por Herón de Alejandría (10 dC -70 dC) donde explica la creación de mecanismos, muchos basados en los principios de Philon o Arquímedes, realizados fundamentalmente como entretenimiento y que imitaban el movimiento, tales como aves que gorjean, vuelan y beben, estatuas que sirven vino o puertas automáticas todas producidas por el movimiento del agua, la gravedad o sistemas de palancas. También cabe destacar su “The automaton theatre” sobre su teatro de marionetas mecánicas que representaban la Guerra de Troya.
El primero de ellos, “La Pianista”, es un autómata con forma de mujer que toca el órgano, con la particularidad de que es la propia figura la que intepreta las obras pulsando las teclas con sus dedos sin tener el sonido pregrabado o procedente de otro lugar. Compuesta por 2.500 piezas podía mover los ojos dirigiendo la mirada del piano a los dedos, inclina el cuerpo, respira y al finalizar cada tema hacía una reverencia.
COMPUTABILIDAD
La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing. La teoría de la computabilidad se interesa a cuatro preguntas:
- ¿Qué problemas puede resolver una máquina de Turing?
- ¿Qué otros formalismos equivalen a las máquinas de Turing?
- ¿Qué problemas requieren máquinas más poderosas?
- ¿Qué problemas requieren máquinas menos poderosas?
La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.
Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing.
Los computadores electrónicos, basados en la arquitectura de von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una máquina de Turing si dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, los lenguajes de programación tienen a lo sumo el mismo poder de expresión que el de los programas para una máquina de Turing y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión equivalente al de una máquina de Turing se denominan Turing completos.
Entre los formalismos equivalentes a una máquina de Turing están:
- Máquinas de Turing con varias cintas
- Máquinas de Turing con cintas bidimensionales, Turmite (o una infinidad de cintas lineales)
- Máquinas de Turing con número limitado de estados y símbolos para la cinta
- Máquinas de Turing con solo dos estados
COMPLEJIDAD
· Complejidad es la cualidad de lo que está compuesto de diversos elementos. En términos generales, la complejidad tiende a ser utilizada para caracterizar algo con muchas partes que forman un conjunto intrincado.
· Desde un punto de vista etimológico, la palabra complejidad es de origen latino, proviene de complectere, cuya raíz plectere significa trenzar, enlazar. El agregado del prefijo “com” añade el sentido de la dualidad de dos elementos opuestos que se enlazan íntimamente, pero sin anular su dualidad. De allí que “complectere” se utilice tanto para referirse al combate entre dos guerreros, como al entrelazamiento de dos amantes. La complejidad y sus implicaciones son las bases del denominado pensamiento complejo de Edgar Morin.
· El pensamiento complejo es una noción utilizada en filosofía y epistemología por autores como Anthony Wilden o Edgar Morin, en física y biología (por Henri Atlan), y en sociología e informàtica. La definición varía significativamente según el área del conocimiento.
· Edgar Morin ve el mundo como un todo indisociable y propone abordar de manera multidisciplinar y multirreferenciada para la construcción del pensamiento, contraponiéndose a la causalidad para abordar fenómenos como una totalidad orgánica.
