Manual del estudiante de Ingeniería en Sistemas de UTN/Matemática Discreta/Lenguajes, Gramáticas y Autómatas

Definicion

Una máquina de Turing es un dispositivo imaginario capaz de leer en la unidad de tiempo un carácter del código externo, modificar o no su estado interno, sustituir o no el carácter que ha sido leído por un carácter del código de salida y moverse a la derecha o a la izquierda una posición.

Normalmente, tanto el código externo (input) como el de salida (output) son códigos binarios. Inicialmente el código externo está dispuesto de modo secuencial en una cinta de longitud potencialmente infinita, dividida en casillas. Cada una de estas casillas será leída por la cabeza lectora/ escrita de la máquina y el dígito binario contenido en ella será sustituido o no por la cabeza escritora. El código externo deberá ser de longitud finita (lo que corresponde a una cantidad finita de datos o instrucciones iníciales) y asimismo el número de estados internos de la máquina debe ser finito. Se requiere que la máquina complete sus cálculos en un tiempo finito. Un ordenador ejecutando un programa concreto es un buen modelo de una máquina de Turing. Usaremos un método de codificación de las máquinas de Turing debido a Roger Penrose.

Como ejemplo vamos a diseñar una máquina de Turing que multiplica por 2 un número natural. Para codificar el input codificaremos primero los datos:

a) Dada una instrucción cualquiera de T, por ejemplo: 101 11I, sólo codificaremos la secuencia final; es decir: 11I.

b) insertaremos en el listado de instrucciones de la máquina, y en la posición que corresponda, órdenes mudas necesarias para completar todas las combinaciones posibles estado-dígito. Esto es necesario dado que no se codifica la secuencia inicial de cada instrucción, y cualquier omisión corrompería el orden de dichas secuencias, que deberá ser de la forma: O0, O1, 10, 11, 1O0, 1O1, 110, 111, 1OO0, 1OO1, 1O10, 1O 11,… Por ejemplo, la máquina de la sección anterior carecía de una instrucción que le dijera qué hacer con 1O1, dado que esta combinación estado-dígito no se presentaba nunca. Introduciremos una instrucción que incluya este caso y cuya secuencia final sea que codificaríamos como O0D. también deberíamos incluir la instrucción 111 O0D, que codificaríamos como O0D. también deberíamos incluir la instrucción 111 O0D al final del listado. No obstante no incluiremos órdenes mudas al final, pues no perturbarán la codificación.

c) Omitiremos las parejas del tipo O0 que correspondan a estado O, dígito 0 u reemplazaremos las parejas correspondiente al estado O y al dígito 1 (es decir, parejas aisladas del tipo O1) por 1.

d) En el código resultante no distinguiremos los caracteres estándar de los caracteres en negrita.

e) Emplearemos el código binario expandido para la codificación final; esto es, O para O y 1O para 1. Usaremos 11º para la D, 111O para la I y 1111o para STOP.

f) Suprimimos los 11O inicial y final, que siempre aparecerán.

El listado del ejemplo de la sección anterior quedaría, después de los pasos a) y b), como O0D 10D O1D 1O0D 111D O0D 01STOP.

Después de c) y d) quedaría como D1OF1F1OOD111DD1STOP

Luego de e) quedará 11O1OO11O1O11O1OOO11O1O1O1O11O11O1O11IIO

Tras el paso f) resulta 1OO11O1O11O1OOO11O1O1O1O11O11O1OII

Obtener las tablas de verdad del modus ponens y del tollendo ponens para j = 0, 1/2, 1 . ¿Es tautológico el silogismo hipotético?

Solución

Como es sabido, el modus ponens tiene la formula (p q) ^ p q, y su tabla de verdad es la forma p q p q (p q)^ p (p q) ^ p q

0 0 1 0 1 0 1 / 2 1 0 1 0 1 1 0 1 1 / 2 0 1 / 2 1 / 2 1 / 2 1 / 2 1 / 2 1 / 2 1 / 2 1 / 2 1 / 2 1 1 1 / 2 1 1 0 0 0 1 1 1 / 2 1 / 2 1 / 2 1 / 2 1 1 1 1 1

El tollendo ponens tiene la forma (p V q) ^ ¬ p q, y su tabla de verdad es

p q p V q ¬ p (p V q)^ ¬ p (p V q) ^ ¬ p q

0 0 0 1 0 1 0 1 / 2 1/2 1 1 / 2 1 / 2 0 1 1 1 1 1 1 / 2 0 1 / 2 1/2 1 / 2 1 / 2 1 / 2 1 / 2 1 / 2 1/2 1 / 2 1 / 2 1 / 2 1 1 1/2 1 / 2 1 1 0 1 1 / 2 1 / 2 1 1 1 / 2 1 0 0 1 1 1 1 0 0 1

El puede comprobar que el silogismo hipotético, que es de la forma (p q) ^ (p r) (p r), no es tautológico. Basta notar que si v (p) = v (q) = v (r) = 1 / 2, el valor de verdad del silogismo hipotético es 1 / 2.