Idioma aceptado y idioma decidido
Una TM acepta un idioma si entra en un estado final para cualquier cadena de entrada w. Un lenguaje es recursivamente enumerable (generado por la gramática Tipo-0) si es aceptado por una máquina de Turing.
Una TM decide un idioma si lo acepta y entra en un estado de rechazo para cualquier entrada que no esté en el idioma. Un idioma es recursivo si lo decide una máquina de Turing.
Puede haber algunos casos en los que una MT no se detenga. Tal MT acepta el idioma, pero no lo decide.
Diseñar una máquina de Turing
Las pautas básicas para diseñar una máquina de Turing se explican a continuación con la ayuda de un par de ejemplos.
Ejemplo 1
Diseñe una TM para reconocer todas las cadenas que constan de un número impar de α.
Solution
La máquina de Turing M se puede construir mediante los siguientes movimientos:
Dejar q1 ser el estado inicial.
Si M es en q1; al escanear α, entra en el estadoq2 y escribe B (blanco).
Si M es en q2; al escanear α, entra en el estadoq1 y escribe B (blanco).
De los movimientos anteriores, podemos ver que M entra al estado q1 si escanea un número par de α, y entra en el estado q2si escanea un número impar de α. Por lo tantoq2 es el único estado que acepta.
Por lo tanto,
M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}
donde δ está dado por -
| Símbolo del alfabeto de cinta | Estado actual 'q 1 ' | Estado actual 'q 2 ' |
|---|---|---|
| α | BRq 2 | BRq 1 |
Ejemplo 2
Diseñe una máquina de Turing que lea una cadena que represente un número binario y borre todos los ceros iniciales de la cadena. Sin embargo, si la cadena consta de solo 0, mantiene un 0.
Solution
Supongamos que la cadena de entrada termina con un símbolo en blanco, B, en cada extremo de la cadena.
La máquina de Turing, M, se puede construir mediante los siguientes movimientos:
Dejar q0 ser el estado inicial.
Si M es en q0, al leer 0, se mueve a la derecha, entra en el estado q1 y borra 0. Al leer 1, entra en el estado q2 y se mueve a la derecha.
Si M es en q1, al leer 0, se mueve a la derecha y borra 0, es decir, reemplaza 0 por B. Al llegar al 1 más a la izquierda, entraq2y se mueve a la derecha. Si llega a B, es decir, la cadena consta de solo ceros, se mueve hacia la izquierda y entra en el estadoq3.
Si M es en q2, al leer 0 o 1, se mueve hacia la derecha. Al llegar a B, se mueve a la izquierda y entra en estadoq4. Esto valida que la cadena se compone solo de 0 y 1.
Si M es en q3, reemplaza B por 0, se mueve a la izquierda y alcanza el estado final qf.
Si M es en q4, al leer 0 o 1, se mueve hacia la izquierda. Al llegar al principio de la cadena, es decir, cuando lee B, llega al estado finalqf.
Por lo tanto,
M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}
donde δ está dado por -
| Símbolo del alfabeto de cinta | Estado actual 'q 0 ' | Estado actual 'q 1 ' | Estado actual 'q 2 ' | Estado actual 'q 3 ' | Estado actual 'q 4 ' |
|---|---|---|---|---|---|
| 0 | BRq 1 | BRq 1 | ORq 2 | - | OLq 4 |
| 1 | 1Rq 2 | 1Rq 2 | 1Rq 2 | - | 1Lq 4 |
| segundo | BRq 1 | BLq 3 | BLq 4 | OLq f | BRq f |