Busca responder las preguntas ¿Qué se puede calcular?¿Que no se puede calcular?¿Cuál es el límite entre estas dos?
Es un objeto matematico definido en papel que nos permite analizar las capacidades, propiedades y límites de la computabilidad. Existen diferentes modelos donde cada uno de ellos permite resolver diferentes problemas. Se pueden comparar entre ellos para determinar su poder computacional. Algunos de ellos son; autómatas finitos, de pila, con dos pilas, celulares, maquinas de turing, calculo lambda y oraculo.
Conjunto finito y no vacío de símbolos.
Secuencia finita de simbolos de ese alfabeto, cada una tiene una longitud (cantidad de simbolos en la misma). La cadena vacía es aquella con longitud cero, se la describe mediante ε .
Conjunto de cadenas en un alfabeto.
Corresponden al modelo de computacion mas simple. Como caracteristicas no tienen memoria, reconocen un numero finito de mensajes y tienen un estado en el que se encuentran.
El automata recibe una cadena de entrada escrita en el alfabeto del mismo. Procesa esa cadena partiendo de un estado inicial y haciendo uso de la funcion de transicion. Retorna una salida de “aceptacion” si al termina de procesar la cadena el estado final corresponde a uno de aceptacion y “rechazo” en caso contrario.
Sea A el conjunto de todas las cadenas que la máquina M acepta, llamaremos A al lenguaje de la máquina M y diremos que M reconoce/acepta A ( L(M) = A ).