Page 106 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

106

Efectivamente, la demostración de que existen funciones no computables nos dice, por un lado,
que existe todo un espacio de lenguajes que quedan dentro de las capacidades de la máquina: los
lenguajes recursivamente enumerarles y todas las subclases incluidas dentro de esta superclase,
que representan todo aquello que es efectivamente computable; pero, por otro lado, la
demostración también conlleva la existencia de lenguajes que no son ni recursivamente
enumerarles, cuya complejidad estructural es tal que ni siquiera un dispositivo tan potente como
la máquina de Turing puede con ellos.

De esta definición se desprende que dada una MT m con una función de transición δi, si al
procesar una cadena w en algún momento se detiene en un estado final, entonces decimos que m
ha aceptado w; si por el contrario, con la misma función de transición, m se «cuelga» en un estado
que no es final, entonces diremos que m ha rechazado w. Existe, sin embargo, una tercera
posibilidad, concretamente, que m entre en un «bucle» y no llegue nunca a detenerse.

De hecho, esta posibilidad también existe en otros autómatas de rango inferior que la MT,
especialmente en sus variantes no deterministas con transiciones espontáneas, pero en el caso de
la MT esta situación se corresponde con un caso particularmente interesante. Evidentemente,
podemos intentar corregir la función de transición para evitar el bucle, pero es posible demostrar
(cosa que no haremos) que hay ciertos lenguajes para los cuales esto no es posible y la MT
siempre, tarde o temprano, entrará en un bucle. “

Si los lenguajes que acepta un autómata lineal acotado son de naturaleza decidibles, o sea son
parte del subconjunto numerable o recursivo, entonces siempre hay un algoritmo que resuelve
totalmente el problema de aceptación atinente al lenguaje que ocupa. O sea, siempre para y acepta,
o para y decide no aceptar. Un indecidible aun aceptando puede que no pare.

Autómata linealmente acotado (ALA) (linear bounded autamation) es una máquina abstracta que
debe cumplir con dos condiciones especiales a saber:

El alfabeto de entrada incluye 2 símbolos especiales #, $ que son las marcas de inicio y final de
la palabra de entrada, respectivamente.

La cabeza de lectura de este autómata puede transitar fuera del espacio definido por el # y $ y no
puede tampoco reescribir sobre estos símbolos.

SE REPRESENTA:

# P P P P P P P P $

CABEZA DE LECTURA/ESCRITURA

Definición formal de ALA:

ALA = (Q, Σ, Γ, Δ, Q0, #, $, F) donde
Q = conjunto de estados