Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario.

Para llevar a cabo algún algoritmo, la maquina se inicializa en algún estado interno arbitrario. A continuación, se pone en marcha y la maquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). Después se mueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo por ejemplo.

Una instrucción típica podría ser:

La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta, entonces pasará al estado interno 1101 (13), escribirá 1 y se moverá hacia la izquierda un paso (la cinta se moverá hacia la derecha).

A continuación es conveniente inventar una notación para la secuencia del INPUT. Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen un cero a la izquierda y/o a la derecha del resultado si empieza o acaba en 1 respectivamente. Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con un cero delante por esta última regla 01010010. Para volver al original hay que ''contraer'' el binario expandido con la siguiente regla:

Empezamos a leer por la izquierda el bianrio expandido. Cuando encontremos un 0 tomamos nota de cuántos 1 hay hasta llegar al siguiente 0 y lo escribimos. Si encontramos que hay dos 0 seguidos, apuntaríamos un 0 porque no habría ningún 1.Veamos con el 13 cómo se haría. El primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3. Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente y encontramos: 1101 que es el número original.

Podría parecer que es una complicación, pero no lo es. Para ver que es de gran utilidad veamos la siguiente expresión en notación expandida:

Si hacemos la contracción, resulta que obtenemos 1112010121012! como pueden observar no toda combinación expandida de unos y ceros, al contraerla, da un número binario. Pero precisamente por eso es tan potente. Los doses que aparecen algunas veces en medio de la secuencia se pueden interpretar como comas:

Así la secuencia original, si se pusiera como INPUT en una máquina de Turing se podría entender como que la entrada consta de los números 7, 5 y 5. Por supuesto no hay limitación a la hora de hacer aparecer doses, treses, etc.. que podrían significar sumar, restar, etc...

A modo de ejemplo, describiremos la máquina de Turing que multiplica un número por dos en notación expandida (XN x 2):

Será interesante comprobar que efectivamente multiplica por dos. Hagámoslo para un número simple. Por ejemplo para el número 2. En notación binaria es 10. En binaria expandida es 0100 pero falta poner una coma al final para que la máquina sepa dónde está el final. O sea que queda al final: 0100110. Ya se observa que la máquina avanzará hacia la derecha siempre que lea 0 y esté en el estado interno 0. Por tanto las condiciones iniciales son: estado interno de la máquina 0 y el INPUT 0100 situado a la derecha del lector. Conectamos la máquina y estos son los pasos:

Lee 0. Aplica la instrucción (1) y se mueve hacia la derecha sin hacer nada.

Lee 1. Aplica la instrucción (2) que consiste en cambiar al estado interno 1, escribir 0 y moverse hacia la derecha. Por tanto la cinta queda: 00[`0]011000 (estado interno 1)

Lee 0. Aplica la instrucción (3) que consiste en cambiar al estado interno 0, escribir 1 y moverse hacia la derecha. Por tanto la cinta queda: 001[`0]11000 (estado interno 0)

Lee 0. Aplica la instrucción (1) y se mueve hacia la derecha sin hacer nada: 0010[`1]1000 (estado interno 0)

Lee 1. Aplica la instrucción (2) que consiste en cambiar al estado interno 1, escribir 0 y moverse hacia la derecha. Por tanto la cinta queda: 00100[`1]000 (estado interno 1)

Lee 1. Aplica la instrucción (4) que consiste en cambiar al estado interno 10, escribir 0 y moverse hacia la derecha. Por tanto la cinta queda: 001000[`0]00(estado interno 10)

Lee 0. Aplica la instrucción (5) que consiste en cambiar al estado interno 11, escribir 1 y moverse hacia la derecha. Por tanto la cinta queda: 0010001[`0]0 (estado interno 11)

Lee 0. Aplica la instrucción (6) que consiste en cambiar al estado interno 0, escribir 1 y parar. Por tanto la cinta queda: 001000110 (estado interno 0)

Acto seguido contraemos: 01002 que es lo mismo que 100 y una coma que indica el final. Este número binario es 1·2²+0·2¹+0·2⁰ = 4. O sea funciona!

687474703A2F2F7777772E627573636F637572736F732E6E65742F6D61726B6574696E672D736C6374656D6133392E68746D637572736F73206D61726B6574696E67cursos marketing.it