haha hola
no se si te sirva una respuesta dos años después haha
En fin este foro es genial y acabo de abrir mi cuenta
así que eres la primera persona a la que le contesto algo
Con AS2 una manera simpática de implementar una máquina de turing es mediante grafos
una máquina de este tipo se puede ver facilmente como un grafo dirigido en el que tienes nodos --los estados de la máquina--- que van hacia más nodos mediante apuntadores, uno para cada caracter del lenguaje de la máquina.
una manera sencilla de implementar nodos es mediante clases y en AS2 no es tan complicado hacer eso
un ejemplo que se me ocurre para un nodo sería el siguiente.
Código ActionScript :
class Estado {
private var direcciones:Array;
private var i;
//constructor de la clase
function Estado (){
direcciones = new Array ();
}
//añadir direccion debe contener lo que sería la quintupla de estado actual, caracter actual,
//stado siguinete, caracter siguiente y movimiento de cbeza lectora con exepcion de la primera
//tupla, ya que el estado actual se tiene en la memoria del autómoata "recordar que lo único que
//puede mantener en memoria una maquina de turing es el estado actual".
function anadirDireccion (caracterLlave, estadoDestino, caracterEscritura, desplazamientoCabeza){
if(!llaveRepetida(caracterLlave)){//el if es una pequeña comprobacion de que la entrada no se está repitiendo.
//direcciones puede ser un nombre algo abiguo, de cualquier manera es un objeto en el que se guardan
//las cuatro tuplas que nos interesan
direcciones[direcciones.length] = {estadoDestino:estadoDestino,caracterLlave:caracterLlave,caracterEscritura:caracterEscritura,desplazamientoCabeza:desplazamientoCabeza}
return true;
}else
return false;
}
//Regresa todos los datos de una tupla que se encuentre en el objeto actual
function obtenerDatos(caracterLlave){
for (i=0; i<direcciones.length; i++){
if(direcciones[i].caracterLlave == caracterLlave){//se busca la información del objeto pedido con la llave
if(direcciones[i].estadoDestino == "_")//si se encuentra pero la combinación lleva a halt se regresará null y la máquina se detendrá
return null;
return direcciones[i];//si se encuentra y no es halt se regresa la referencia al objeto
}
}
return null;//si no se encuentra el objeto igual se regresará null para detener la máquina.
}
//funcion para comprobar que la entrada no esta repetida :p
private function llaveRepetida (caracterLlave){
for (i=0; i<direcciones.length; i++){
if(direcciones[i].caracterLlave == caracterLlave)
return true;
}
return false;
}
}
Este estado puede contener un número ilimitado de caracteres para con los cuales dirigir el programa
estos se guardan en la lista direcciones.
Con esta clase podremos crear nodos de la máquina para empezar a hacer nuestro programa
hagamos un programa sencillo que solo cheque si un string es palíndromo
Código ActionScript :
//Con la clase estado ya creada nos dedicaremos a hacer u pequeño programa
//este programa ve si u string con el lenguaje A,B es palindromo
//primero creamos los estados necesarios para la máquina en este caso 15
estado1 = new Estado ();
estado2 = new Estado ();
estado3 = new Estado ();
estado4 = new Estado ();
estado5 = new Estado ();
estado6 = new Estado ();
estado7 = new Estado ();
estado8 = new Estado ();
estado9 = new Estado ();
estado10 = new Estado ();
estado11 = new Estado ();
estado12 = new Estado ();
estado13 = new Estado ();
estado14 = new Estado ();
estado15 = new Estado ();
//una vez que ya hemos creado los estados comenzamos a
//programarlos para que hagan lo que deben de hacer
//esto significa decirles a qué estado deben de ir cuando
//lean un caracter y que caracter deben de escribir
//por ejemplo el estado1 lee un campo vacio "representado por '_'"
//si lo lee con exito pasa al estado 2, escribe el caracter '#'
// y nueve el cabezal de lectura a la derecha
//como ven cada estado tiene 4 tuplas
// en la primera y en la tercera se meten caracteres siendo el caractér
// '_' el caracter de vacio
// en la segunda tupla se pone el estado destino o la referencia a este
//en caso de que se ponga '_' se interpretará como estado halt
//la última tupla es la de movimiento de la cameza lectora donde:
//> es movimiento a la derecha
//< es movimiento a la izquierda y
//_ es sin movimiento
estado1.anadirDireccion ('_',estado2,'#','>');
estado2.anadirDireccion ('A',estado3,'_','>');
estado2.anadirDireccion ('B',estado4,'_','>');
estado2.anadirDireccion ('_',estado7,'_','<');
estado3.anadirDireccion ('A',estado3,'A','>');
estado3.anadirDireccion ('B',estado3,'B','>');
estado3.anadirDireccion ('_',estado5,'_','<');
estado4.anadirDireccion ('A',estado4,'A','>');
estado4.anadirDireccion ('B',estado4,'B','>');
estado4.anadirDireccion ('_',estado6,'_','<');
estado5.anadirDireccion ('A',estado11,'_','<');
estado5.anadirDireccion ('B',estado12,'_','<');
estado5.anadirDireccion ('_',estado7,'_','<');
estado6.anadirDireccion ('A',estado12,'_','<');
estado6.anadirDireccion ('B',estado11,'_','<');
estado6.anadirDireccion ('_',estado7,'_','<');
estado7.anadirDireccion ('_',estado7,'_','<');
estado7.anadirDireccion ('#',estado8,'_','>');
estado8.anadirDireccion ('_',estado9,'Y','>');
estado9.anadirDireccion ('_',estado10,'E','>');
estado10.anadirDireccion ('_',estado15,'S','>');
estado11.anadirDireccion ('A',estado11,'A','<');
estado11.anadirDireccion ('B',estado11,'B','<');
estado11.anadirDireccion ('_',estado2,'_','>');
estado12.anadirDireccion ('A',estado12,'_','<');
estado12.anadirDireccion ('B',estado12,'_','<');
estado12.anadirDireccion ('_',estado12,'_','<');
estado12.anadirDireccion ('#',estado13,'_','>');
estado13.anadirDireccion ('_',estado14,'N','>');
estado14.anadirDireccion ('_',estado15,'O','>');
estado15.anadirDireccion ('_','_','_','_');
Listo ahora tenemos un programa pero necesitamos una cabeza lectora que lo ejecute
entonces escribimos dentro del fla en algún otro sitio lo siguiente
Código ActionScript :
//ya tenemos el programa de palíndromos, ahora necesitamos la cameza de lectura y
//escritura, que es la que llevará la ejecución del programa
function corriendo (){//esta sería la cabeza lectora
estadoTuring = estado1;//el estado con el que inciará la máquina es este
while(true){
//en esta parte se haría la parte de leer la cinta infinita
//recordar que para nuestro ejemplo cadenaInicial es la cinta
//indice es la posición de la cabeza lectora en la misma
datosNodo = estadoTuring.obtenerDatos(cadenaInicial[indice])
//datos nodo son los datos del estado contenido en el objeto de estado
//en el cual la máquina se encuentra
if(datosNodo!=null){//mientras no se ejecute un halt la máquina seguirá
//siguiendo con la ejecución
estadoTuring = datosNodo.estadoDestino ;
}else{//si se ejecuta un halt la máquina termina
trace("Se detuvo la máquina")
break;
}
//en esta sección se ejecutará la parte de escritura en la cinta
cadenaInicial[indice] = datosNodo.caracterEscritura;
//y en esta el movimiento de la cameza lectora
if(datosNodo.desplazamientoCabeza == ">")
indice ++;
if(datosNodo.desplazamientoCabeza == "<")
indice --;
}
trace("Resultado:"+cadenaInicial);
}
//una vez que se tienen los estados y el programa en sí se requiere poner una cadena inicial
//recordemos que la máquina de turing trabaja con una cinta infinita en este caso la
//representaremos con una array que contiene la candena que el autómata
//amalizará para ver si es palindroma.
var cadenaInicial:Array = new Array('_','_','A','B','A','B','A','A','A','B','A','B','A','_','_','_' );
//el indice es uno ya que es una posición antes del primer caracter
//lpsición que el automoata espera como posición inicial
indice = 1;
corriendo ()
//otro ejemplo
trace ("otro ejemplo");
var cadenaInicial:Array = new Array('_','_','A','B','A','B','A','A','A','B','A','A','A','_','_','_' );
indice = 1;
corriendo ()
//si todo sale bien deberían de ver YES para los que son palíndromos y NO para los que no lo son
pues bien aquí acaba esta pequeña cosa que escribo "mi primera cosa en CL"
Realmente estoy muy agradecido con esta pag ya que con ella inicie a programar
y en especial inicie a desarrollar en flash
pd con este mismo esquema generé esta máquina de turing animada :p por si la quieren ver
"claro con mucho código extra para animación y etc pero la idea e incluso la clase estado es la misma.
http://www.ebbstudios.net/animaciones/turingMachine/index.html
los archivos los pueden descargar de aki
http://www.ebbstudios.net/animaciones/turingMachine/turing.zip
Nota: perdón sino puse los links con hipoervínculo pero nu supe como :p
Escrito el 21 Abr 2008 10:34 am
.