Numerarius, no sé si estamos hablando de lo mismo. Me imagino lo que es un autómata finito, pero no estoy seguro de lo que significa con toda exactitud.
Deseo poder expresar algoritmos ''finitarios'' en la PC, asumiendo que la memoria de la computadora puede crecer tanto como sea necesario.
La memoria RAM de una PC es de tamaño fijo, pero puedo pensar que ingreso los datos a través de un dispositivo de almacenamiento externo, como una colección de cintas o discos externos.
Si yo puedo colocar cintas o discos en serie, de modo que la capacidad de almacenamiento de datos vaya creciendo a voluntad, creo que puedo decir que mi ''máquina'' trabaja con longitud de datos potencialmente infinita, tan grande de finita como yo quiera
Tan sólo hay que lograr que la máquina que uno usa sea capaz de reconocer sin problemas que se ha agregado una nueva cinta o disco.
O sea, creo que es posible construir el símil de una máquina con memoria no acotada. ¿No es eso una máquina de Turing?
La cota real me la pondría el Universo mismo, si es que no dispongo de materia suficiente para crear más allá de \( 10^{80} \) discos duros... Pero eso no importaría mucho, porque sería una limitación de hardware y no de software: la máquina estaría configurada lógicamente para aceptar que se pueda agregar siempre un dispositivo más a la cadena en serie de cintas o discos, y se podría acceder secuencialente a ellos con la misma lógica de una lista enlazada.
El siguiente algoritmo en lenguaje C permite reconocer si un string de longitud desconocida, es o no es una expresión de un cierto lenguaje cuyos signos pertenecen al conjunto \( L = \{(,),\exists{},\Rightarrow{},-,=,x,|,0,S,+,\cdot\} \), que son los símbolos que eligió Gustavo:
#define bool unsigned int
#define false 0
#define true 1
bool is_in_L(char c)
{
#define MAX 10
const char L[MAX] = "()E*-=0S+."; /* Son los signos de L, y he puesto * para indicar 'flecha'. */
unsigned short int i;
for (i = 0; (i < MAX) && (c != L[i]); i++)
;
if (i == MAX) return true;
else return false;
}
bool is_in_language(char *s)
{
/* La longitud de la cadena s es arbitrario, y en esta subrutina no hace falta especificar cotas */
while((*s != 0) && is_in_L(*s)) /* Se usa la convención de que una cadena en C termina en su primer caracter nulo */
;
if (*s == 0) return true; /* Si terminó la búsqueda tras el último caracter, es que s pertenece al lenguaje */
else return false;
}
En el código que puse, se habrá notado que la función de reconocimiento no es capaz de darse cuenta si s es una cadena con longitud finita. Eso sería un problema, porque si se introduce una cadena s errónea, el programa podría no terminar.
Yo digo que esto se puede solucionar cambiando el tipo de datos char* por el de un FILE*, o sea, un archivo (de texto), ya que sabemos que los archivos ya tienen longitud finita desde el sistema operativo.
Una forma menos ''sucia'' de solucionar esto, sería irse a C++ y crear una class llamada STRING, que obligue al usuario a inicializarla en "", o sea vacía, y que el único modo de hacerla crecer sea agregando un caracter de uno en uno.
Tendríamos así un tipo de datos controlado, siempre de longitud finita, y que podría crecer tanto como haga falta.
O bien usar MATLAB o Python y aprovechar que ya tienen un manejo de listas. Un string sería una lista de caracteres, y el tamaño podría ser tan grande como haga falta.
Las subrutinas para reconocer fórmulas, enunciados, etc., podrían programarse con una filosofía similar en una computadora comùn y corriente, pudiendo tratar expresiones de tamaño finito aunque arbitrariamente grande.
