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:

donde:

Símbolo Descripción
Conjunto finito de símbolos que pueden aparecer en la cinta.
Alfabeto de entrada a la máquina un conjunto finito de símbolos (menos el espacio en blanco).
Conjunto finito de estados.
Estado inicial en el que empieza la máquina.
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 '' '' o ''.
Conjunto de estados finales de aceptación.
Función de transición donde es un movimiento a la izquierda y es el movimiento a la derecha.

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

Y se interpreta de la siguiente manera:

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

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:

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






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






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





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












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 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 seguido del mismo número de , 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 , 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 ) o también cuando se llegue a un estado en el que no existen instrucciones para un símbolo leído, como por ejemplo o .

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

Representa la lógica del estado , 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 o . Si lee cualquier otro símbolo, o sea , 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 si el cabezal se desplaza hacia la derecha (R) y se decrementa si el cabezal se desplaza a la izquierda (L).

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

Representa la lógica del estado , 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 , o . Así pues, si el símbolo leído es o  la máquina se detendrá.

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

Representa la lógica del estado , 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 , o . Así pues, si el símbolo leído es o  la máquina se detendrá.

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

Representa la lógica del estado , 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 . Así pues, si el símbolo leído es , , o 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.

2 opiniones en “Máquinas de Turing en C”

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.