Máquinas de Turing en C

Una máquina de Turing es un dispositivo de cálculo lógico que utiliza un input en una o varias cintas que se van moviendo en función de la instrucción que tenga el estado de un autómata, para finalmente obtener un output mediante la reescritura de los datos en la misma cinta. La máquina tiene un cabezal de lectura y este lee el dato que se encuentra en la posición de la cinta. Por buscar una similitud lo mas parecido sería un casette de música, que se rebobina o se adelanta según la canción que nos interese, en la cual podremos borrar o grabar otra canción donde queramos. En el caso de una máquina de Turing de una cinta se define dicha máquina como una 7-tupla de la siguiente manera:

M=(Q, \Sigma, \Gamma, s, \_, F, \delta)

donde:

Símbolo Descripción
\Gamma Conjunto finito de símbolos que pueden aparecer en la cinta.
\Sigma Alfabeto de entrada a la máquina un conjunto finito de símbolos (menos el espacio en blanco).
Q Conjunto finito de estados.
s \in Q Estado inicial en el que empieza la máquina.
\_ \in \Gamma Símbolo denominado blanco y es el único símbolo que se puede repetir un número infinito de veces. Es muy habitual que el símbolo para referirse al blanco sea 'b' 'B' o '\#'.
F \subseteq Q Conjunto de estados finales de aceptación.
\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} Función de transición donde L es un movimiento a la izquierda y R es el movimiento a la derecha.

Cada función de transición se escribe así:

\delta(q_{0},0) = (X, R, q_{1})

Y se interpreta de la siguiente manera:

  1. La máquina se encuentra en el estado q_{0}
  2. Lee un 0
  3. Sobreescribe el 0 con una X
  4. El cabezal se mueve en la cinta una posición a la derecha (Right)
  5. Finalmente se cambia al estado q_{1}

Teniendo claros los conceptos mínimos de los que se compone una máquina de Turing se puede diseñar una para saber si una cadena de entrada cumple una expresión lógico-matemática determinada. A continuación algunos ejemplos.

Cadenas con un numero de 'x' seguidas del mismo número de 'y'

La notación de este Lenguaje Independiente del Contexto (LIC) o expresión regular es:

x^{n}y^{n} | n \geqslant 0

Esta notación representa cualquier cadena compuesta de un número de caracteres x seguido del mismo número de caracteres y, y que el número de veces que aparecen estos caracteres sea mayor o igual que 0. Cualquiera de las siguientes cadenas de entrada sería válida:

(cadena \ vacia)
xy
xxyy
xxxyyy
xxxxyyyy
\vdots

Y las siguientes serían cadenas no válidas o no aceptadas:

x
yx
xyxy
xxxyy
xyyx
\vdots

Donde x e y pueden ser otros símbolos. Para este ejemplo se van a usar los símbolos pertenecientes al conjunto binario, o sea 0 y 1, y n valdrá 3. Así pues, estos son los datos que conforman la máquina de Turing:

\Gamma \rightarrow \{0, 1\}
\Sigma \rightarrow 000111
Q \rightarrow \{q_{0}, q_{1}, q_{2}, q_{3}\}
s \rightarrow q_{0}
F \rightarrow q_{3}

Las funciones de transición serán las siguientes:

\delta(q_{0},0) = (X, R, q_{1})
\delta(q_{0},Y) = (Y, R, q_{3})
\delta(q_{0},\_) = (\_, STOP, q_{4})
\delta(q_{1},0) = (0, R, q_{1})
\delta(q_{1},1) = (Y, L, q_{2})
\delta(q_{1},Y) = (Y, R, q_{1})
\delta(q_{2},0) = (0, L, q_{2})
\delta(q_{2},1) = (1, L, q_{2})
\delta(q_{2},X) = (X, R, q_{0})
\delta(q_{2},Y) = (Y, L, q_{2})
\delta(q_{3},Y) = (Y, R, q_{3})
\delta(q_{3},\_) = (\_, STOP, q_{4})

Esta lista de funciones de transición también se puede representar mediante la siguiente tabla:

Además de la lista de funciones o la tabla anterior, las funciones de transición también se pueden representar mediante el diagrama de un autómata. El ejemplo de máquina de Turing para el lenguaje 0^{n}1^{n} | n \geqslant 0 se representaría con el siguiente autómata determinista.

A continuación un vídeo que he hecho -como he podido- en el que se puede apreciar el progreso de cada una de las funciones sobre la cinta.

Una vez explicado en detalle cómo funciona una máquina de Turing se puede extrapolar dicho funcionamiento a un programa, por ejemplo en lenguaje de programación C. Existen varias maneras de hacer un programa en C que sea capaz de evaluar si una cadena de entrada contiene un número de x seguido del mismo número de y, y desde luego hacerlo con una simulación de una máquina de Turing como la que se explica a continuación no es la mejor manera, pero sirve para comprender "la lógica" sobre su funcionamiento, que es realmente el objetivo de este artículo.

El programa tendrá al inicio una serie de variables y constantes. También la declaración de algunos procedimientos que se invocarán durante varias partes del programa, según el flujo de datos que vaya leyendo la máquina. Son los siguientes:

void estado_q0(char*, int);
void estado_q1(char*, int);
void estado_q2(char*, int);
void estado_q3(char*, int);
void stop(bool);
void addBlankL(char *w);
void addBlankR(char *w);
void salidaTrue();
void salidaFalse();
void printLog(char *w, char *ea, int i, char x, char m, char *e);
void stop(bool resultado);
int linea(int s);
void printTablaMT();

Se trata de procedimientos que contienen la lógica de cada uno de los 4 estados definidos en Q, y además hay un último procedimiento 'void stop(bool)' que servirá para detener la máquina cuando se llegue a un estado de aceptación (en nuestro caso q_{3}) o también cuando se llegue a un estado en el que no existen instrucciones para un símbolo \in \Gamma + \{\_\} leído, como por ejemplo \delta(q_{0},X) o \delta(q_{2},\_).

Procedimiento 'void estado_q0(char *w, int i)'

Representa la lógica del estado q_{0}, el código es el siguiente:

void estado_q0(char *w, int i) {
	estadoActual = "q0";

	if (w[i] == '0') {
		printLog(w, estadoActual, i, 'X', 'R', "q1");
		w[i] = 'X';
		estado_q1(w, i += 1);
	} else if (w[i] == '1' || w[i] == 'X' || w[i] == '_') {
		stop(false);
	} else if (w[i] == 'Y') {
		printLog(w, estadoActual, i, 'Y', 'R', "q3");
		estado_q3(w, i += 1);
	}
}

Ejecuta un condicional que en función del símbolo leído por el cabezal solo continúa si dicho símbolo es 0 o Y. Si lee cualquier otro símbolo, o sea 1, X o un blanco \_, la máquina se detiene invocando el procedimiento 'stop(false);' e imprime por pantalla un mensaje indicando que la cadena de entrada no satisface (false) el lenguaje (LIC) definido para esta máquina de Turing. Tanto este procedimiento como los demás del tipo 'estado_qn' reciben dos argumentos, el primero es el puntero a la cadena o string de entrada y el segundo es la posición del cabezal de lectura. Esta posición del cabezal se incrementa +1 si el cabezal se desplaza hacia la derecha (R) y se decrementa -1 si el cabezal se desplaza a la izquierda (L).

Procedimiento 'void estado_q1(char *w, int i)'

Representa la lógica del estado q_{1}, el código es el siguiente:

void estado_q1(char *w, int i) {
	estadoActual = "q1";

	if (w[i] == '0') {
		printLog(w, estadoActual, i, '0', 'R', "q1");
		estado_q1(w, i += 1);
	} else if (w[i] == '1') {
		printLog(w, estadoActual, i, 'Y', 'L', "q2");
		w[i] = 'Y';
		estado_q2(w, i -= 1);
	} else if (w[i] == 'X' || w[i] == '_') {
		stop(false);
	} else if (w[i] == 'Y') {
		printLog(w, estadoActual, i, 'Y', 'R', "q1");
		estado_q1(w, i += 1);
	}
}

Ejecuta un condicional que hace que el programa continúe solo si el símbolo leído es 0, 1 o Y. Así pues, si el símbolo leído es X o \_ la máquina se detendrá.

Procedimiento 'void estado_q2(char *w, int i)'

Representa la lógica del estado q_{2}, el código es el siguiente:

void estado_q2(char *w, int i) {
	estadoActual = "q2";

	if (w[i] == '0') {
		printLog(w, estadoActual, i, '0', 'L', "q2");
		estado_q2(w, i -= 1);
	} else if (w[i] == '1' || w[i] == '_') {
		stop(false);
	} else if (w[i] == 'X') {
		printLog(w, estadoActual, i, 'X', 'R', "q0");
		estado_q0(w, i += 1);
	} else if (w[i] == 'Y') {
		printLog(w, estadoActual, i, 'Y', 'L', "q2");
		estado_q2(w, i -= 1);
	}
}

Ejecuta un condicional que hace que el programa continúe solo si el símbolo leído es 0, X o Y. Así pues, si el símbolo leído es 1 o \_ la máquina se detendrá.

Procedimiento 'void estado_q3(char *w, int i)'

Representa la lógica del estado q_{3}, el código es el siguiente:

void estado_q3(char *w, int i) {
	estadoActual = "q3";

	if (w[i] == '0' || w[i] == '1' || w[i] == 'X') {
		stop(false);
	} else if (w[i] == 'Y') {
		printLog(w, estadoActual, i, 'Y', 'R', "q3");
		estado_q3(w, i += 1);
	} else if (w[i] == '_') {
		printLog(w, estadoActual, i, '_', 'R', "STOP");
		stop(true);
	}
}

Ejecuta un condicional que hace que el programa continúe solo si el símbolo leído es Y. Así pues, si el símbolo leído es 0, 1, o X la máquina se detendrá indicando que no satisface el LIC de entrada, pero si el símbolo leído es un blanco \_ la máquina se detendrá indicando que la cadena de entrada si satisface el lenguaje mediante esta máquina de Turing.

Programa completo

A continuación el programa completo con comentarios en el código.

/*
 * turinMachine v0.05
 * Copyleft - 2017  Javier Dominguez Gomez
 * Written by Javier Dominguez Gomez <jdg@member.fsf.org>
 * GnuPG Key: D6648E2B
 * Madrid, Spain
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Compilation: gcc -std=gnu99 -O0 -g3 -Wall -c -o turing.o "turing.c"
 *              gcc -o turing turing.o
 *
 * Usage:       ./turing
 *
 * Case {x^{n}y^{n} | n>=0}
 * +--------------------------------------------------------------------+
 * |        0           1           X           Y           _           |
 * +--------------------------------------------------------------------+
 * | q0     (X,R,q1)    -           -           (Y,R,q3)    (_,STOP,q4) |
 * | q1     (0,R,q1)    (Y,L,q2)    -           (Y,R,q1)    -           |
 * | q2     (0,L,q2)    (1,L,q2)    (X,R,q0)    (Y,L,q2)    -           |
 * | q3     -           -           -           (Y,R,q3)    (_,STOP,q4) |
 * | q4     -           -           -           -           (STOP)      |
 * +--------------------------------------------------------------------+
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdbool.h>

/* Longitud maxima + 1. */
#define MAX_LONG 256

/* Declaracion de variables globales. */
char *estadoActual;
char *funcion = "0^{n}1^{n} | n >= 0";
int i, longitudW;

void estado_q0(char*, int);
void estado_q1(char*, int);
void estado_q2(char*, int);
void estado_q3(char*, int);
void stop(bool);
void addBlankL(char *w);
void addBlankR(char *w);
void salidaTrue();
void salidaFalse();
void printLog(char *w, char *ea, int i, char x, char m, char *e);
void stop(bool resultado);
int linea(int s);
void printTablaMT();

int main(int argc, char *argv[]) {

	/* Se asigna memoria para la cadena w. */
	char *w = malloc(MAX_LONG);

	printf("Introduce una cadena: ");

	/* Guarda la cadena w, con limite de longitud. */
	fgets(w, MAX_LONG, stdin);

	/* Se obtiene la logitud de la cadena de entrada,
	 * sin tener en cuanta el salto de linea. */
	longitudW = strlen(w) - 1;

	/* Elimina salto de linea del final, si existiera. */
	if ((longitudW + 1 > 0) && (w[longitudW] == '\n')) {
		w[longitudW] = '\0';
	}

	/* Primera condicion es que la cadena debe ser par */
	if (strlen(w) % 2 != 0) {
		salidaFalse();
	} else if(strlen(w) == 0){
		/* Acepta la cadena vacia. */
		salidaTrue();
	} else {
		printTablaMT();

		/* Se incorpora un blanco por la izquierda
		 * y otro por la derecha de la cadena w. */
		addBlankL(w);
		addBlankR(w);

		/* Le digo a la maquina de Turing que empiece
		 * por el caracter w[1] en el estado q0 */
		estado_q0(w, 1);
	}

	/* Se libera la memoria reservada para la daena w. */
	free(w);

	return 0;
}

void addBlankL(char *w) {
	/* Recorro el array de derecha a izquierda y desplazo
	 * los caracteres una posicion a la derecha */
	for (i = strlen(w); i > 0; i--) {
		w[i] = w[i - 1];
	}

	/* Concateno la cadena w con un blanco por la izquierda. */
	w[i] = '_';
}

void addBlankR(char *w) {
	/* Concateno la cadena w con un blanco por la derecha. */
	strcat(w, "_");
}

void salidaTrue() {
	printf("\n\nEnhorabuena! se cumple que %s\n\n", funcion);
}

void salidaFalse() {
	printf("\n\nNo se cumple que %s\n\n", funcion);
}

void printLog(char *w, char *ea, int i, char x, char m, char *e) {
	printf(
			"\nw es: \"%s\". Estoy en %s, leo \"%c\", lo cambio por \"%c\", me muevo a la %c y me voy al estado %s.",
			w, ea, w[i], x, m, e);
}

void estado_q0(char *w, int i) {
	estadoActual = "q0";

	// Si leo 0
	if (w[i] == '0') {

		printLog(w, estadoActual, i, 'X', 'R', "q1");

		// lo cambio por X
		w[i] = 'X';

		// me muevo a la derecha (R) y me voy al estado q1.
		estado_q1(w, i += 1);

		// Si leo 1, X o un blanco (_)
	} else if (w[i] == '1' || w[i] == 'X' || w[i] == '_') {

		// se para la maquina de Turing con un resultado false.
		stop(false);

		// Si leo Y
	} else if (w[i] == 'Y') {

		printLog(w, estadoActual, i, 'Y', 'R', "q3");

		// dejo Y sin cambiar, me muevo a la derecha (R) y me voy al estado q3.
		estado_q3(w, i += 1);
	}
}

void estado_q1(char *w, int i) {
	estadoActual = "q1";

	// Si leo 0
	if (w[i] == '0') {

		printLog(w, estadoActual, i, '0', 'R', "q1");

		// dejo 0 sin cambiar, me muevo a la derecha (R) y sigo en el estado q1.
		estado_q1(w, i += 1);

		// Si leo 1
	} else if (w[i] == '1') {

		printLog(w, estadoActual, i, 'Y', 'L', "q2");

		// lo cambio por Y
		w[i] = 'Y';

		// me muevo a la izquierda (L) y me voy al estado q2.
		estado_q2(w, i -= 1);

		// Si leo X o un blanco (_)
	} else if (w[i] == 'X' || w[i] == '_') {

		// se para la maquina de Turing con un resultado false.
		stop(false);

		// Si leo Y
	} else if (w[i] == 'Y') {

		printLog(w, estadoActual, i, 'Y', 'R', "q1");

		// dejo Y sin cambiar, me muevo a la derecha (R) y me voy al estado q1.
		estado_q1(w, i += 1);
	}
}

void estado_q2(char *w, int i) {
	estadoActual = "q2";

	// Si leo 0
	if (w[i] == '0') {

		printLog(w, estadoActual, i, '0', 'L', "q2");

		// dejo 0 sin cambiar, me muevo a la izquierda (L) y sigo en el estado q2.
		estado_q2(w, i -= 1);

		// Si leo 1 o un blanco (_)
	} else if (w[i] == '1' || w[i] == '_') {

		// se para la maquina de Turing con un resultado false.
		stop(false);

		// Si leo X
	} else if (w[i] == 'X') {

		printLog(w, estadoActual, i, 'X', 'R', "q0");

		// dejo X sin cambiar, me muevo a la derecha (R) y me voy al estado q0.
		estado_q0(w, i += 1);

		// Si leo Y
	} else if (w[i] == 'Y') {

		printLog(w, estadoActual, i, 'Y', 'L', "q2");

		// dejo Y sin cambiar, me muevo a la izquierda (L) y me voy al estado q2.
		estado_q2(w, i -= 1);
	}
}

void estado_q3(char *w, int i) {
	estadoActual = "q3";

	// Si leo 0, 1 o X
	if (w[i] == '0' || w[i] == '1' || w[i] == 'X') {

		// se para la maquina de Turing con un resultado false.
		stop(false);

		// Si leo Y
	} else if (w[i] == 'Y') {

		printLog(w, estadoActual, i, 'Y', 'R', "q3");

		// dejo Y sin cambiar, me muevo a la derecha (R) y sigo en el estado q3.
		estado_q3(w, i += 1);

		// Si leo un blanco (_)
	} else if (w[i] == '_') {

		printLog(w, estadoActual, i, '_', 'R', "STOP");

		// se para la maquina de Turing con un resultado true.
		stop(true);
	}
}

void stop(bool resultado) {
	if (resultado) {
		salidaTrue();
	} else {
		salidaFalse();
	}
}

int linea(int s) {
	fprintf(stdout,"+");
	for (int i = 0; i <= s; i++) {
		fprintf(stdout,"-");
	}
	fprintf(stdout,"+\n");
	return 0;
}

void printTablaMT(){
	printf("\nMaquina de Turing para %s\n\n", funcion);
	linea(62);
	printf("|%-5.5s      %-5.5s      %-5.5s      %-5.5s      %-5.5s   %-10.10s |\n", " ", "0", "1", "X", "Y", "    _");
	linea(62);
	printf("|%-5.5s   %-8.8s   %-8.8s   %-8.8s   %-8.8s   %-10.10s |\n", " q0", "(X,R,q1)", "   -", "   -", "(Y,R,q3)", "    _");
	printf("|%-5.5s   %-8.8s   %-8.8s   %-8.8s   %-8.8s   %-10.10s |\n", " q1", "(0,R,q1)", "(Y,L,q2)", "   -", "(Y,R,q1)", "    _");
	printf("|%-5.5s   %-8.8s   %-8.8s   %-8.8s   %-8.8s   %-10.10s |\n", " q2", "(0,L,q2)", "   -", "(X,R,q0)", "(Y,L,q2)", "    _");
	printf("|%-5.5s   %-8.8s   %-8.8s   %-8.8s   %-8.8s   %-10.10s |\n", " q3", "   -", "   -", "   -", "(Y,R,q3)", "(#,R,STOP)");
	linea(62);
}

Por último aclarar que las máquinas de Turing, que no dejan de ser un autómata, actualmente en Ciencias de la Computación se utilizan para crear compiladores de algunos lenguajes de programación. También para desarrollo de inteligencia artificial y redes neuronales. Así pues, no tiene mucho sentido hacer un programa como el de este artículo para otro fin que no sea el de explicar el funcionamiento forense de una máquina de Turing.

Espero que os haya gustado. Como siempre, cualquier pregunta, sugerencia o corrección será bien venida.

Algoritmos de ordenación - método de selección directa

En otro post expliqué cómo podemos ordenar y hacer búsquedas en un array mediante el método de la burbuja, pero este no es el único algoritmo de ordenación que podemos emplear en programación. Esta vez aprenderemos a usar el método de selección directa. Este método es mas sencillo que el anterior, solo tenemos que tomar el elemento n del array, y recorrer uno a uno todos los elementos del array que tiene n a su derecha, incluido él mismo. Si encontramos un elemento a la derecha de n que tiene el menor valor de todos los recorridos (si quisiéramos un orden ascendente) lo intercambiamos, desplazando ese valor menor a la posición de n, y n a la posición de ese valor menor.

A continuación se repite todo el proceso tantas veces como longitud tiene el array, y de este modo obtendríamos un array ordenado. Vemos un ejemplo

#include <stdio.h>

int main(void) {
	/* Declaramos un array de enteros. */
	int vector[4] = { 3, 2, 4, 1 };

	/* Declaramos otras variables que
	 * nos serviran para iterar. */
	int i, j, k, aux;

	/* Ordenamos el array de enteros. */
	for (k = 0; k <= 2; k++) {
		i = k;
		aux = vector[k];
		for (j = k + 1; j <= 3; j++) {
			if (vector[j] < aux) {
				i = j;
				aux = vector[i];
			}
		}
		vector[i] = vector[k];
		vector[k] = aux;
	}

	/* Imprimimos el array de enteros. */
	for (i = 0; i <= 3; i++) {
		printf("%d ", vector[i]);
	}
}

Este ejemplo está hecho en lenguaje C, pero puedes probar a realizarlo en cualquier lenguaje de programación tradicional.

Algoritmos de ordenación - método de la burbuja

Muchas veces cuando estamos haciendo un programa nos puede interesar ordenar una lista de enteros de mayor a menor, o al revés. En todos los lenguajes de programación existen algoritmos de ordenación, y aquí voy a explicar uno de los mas conocidos y sencillo, el método de la burbuja. Tiene este nombre por que (en caso de orden ascendente) hace que el elemento menor de la lista "suba" como una burbuja hasta el principio del array.

El método de la burbuja es muy sencillo, consiste en coger los elementos de un array e ir comparándolos con sus adyacentes y si fuera necesario intercambiarlos, alterando así el orden de los mismos. Si queremos un orden ascendente el intercambio sucede cuando se da el caso en el que el elemento del array en el que nos hemos posicionado es mayor que el que tiene inmediatamente a su derecha. Veámoslo en la siguiente imagen:

En este ejemplo, hecho en C, podemos ver cómo se ordena un array de varios enteros:

#include <stdio.h>

int main(void) {

	/* Declaramos un array de enteros. */
	int vector[4] = { 3, 2, 4, 1 };

	/* Declaramos otras variables que
	 * nos serviran para iterar. */
	int i, j, aux;

	/* Ordenamos el array de enteros. */
	for (i = 0; i <= 2; i++) {
		for (j = 3; j >= i + 1; j--) {
			if (vector[j - 1] > vector[j]) {
				aux = vector[j];
				vector[j] = vector[j - 1];
				vector[j - 1] = aux;
			}
		}
	}

	/* Imprimimos el array de enteros. */
	for (i = 0; i <= 3; i++) {
		printf("%d ", vector[i]);
	}
}

Aunque este ejemplo esta hecho en C, realmente se se puede usar en prácticamente todos los lenguajes de programación tradicionales. ¡Pruébalo!

Quizás te pueda interesar ver este otro post donde explico el método de selección directa.