Máquinas de Turing restringidas

En este artículo, vamos a describir los conceptos básicos de la máquina de Turing restringida y para una comprensión básica, primero puede leer el requisito previo que lo ayudará a comprender el tema con claridad.

Requisito previo: máquina de Turing

• Turing Machine acepta el lenguaje recursivamente enumerable. Es más poderoso que cualquier otro autómata como FA , PDA y LBA. Calcula la función recursiva parcial. Se puede dividir en máquina de Turing determinista (DTM) o máquina no determinista (NTM). De forma predeterminada, Turing Machine es DTM, y la potencia de DTM y NTM es la misma.
• Esta máquina actúa como Reconocedor o Aceptador y como Enumerador.
• Se dice que la máquina es un aceptador que acepta o reconoce las strings de un lenguaje recursivamente enumerable (L) sobre el alfabeto de entrada (∑) y se dice que la máquina es un enumerador que enumera la string de un lenguaje recursivamente enumerable sobre el alfabeto de entrada ∑.

Las máquinas de Turing restringidas pueden ser de los siguientes tipos:

1. Máquina de Turing que se detiene: se
   dice que una máquina de Turing es una máquina de Turing que se detiene si siempre se detiene para cada string de entrada. Puede aceptar el lenguaje recursivo y es menos potente que la máquina de Turing.
2. Autómatas acotados lineales:
   se comporta como una máquina de Turing, pero el espacio de almacenamiento de la cinta está restringido solo a la longitud de la string de entrada. Es menos poderosa que una máquina de Turing pero más poderosa que los autómatas de empuje hacia abajo .
3. Máquina de Turing unidireccional:
   el cabezal de este tipo de máquina de Turing solo puede moverse en una dirección. Puede aceptar el único lenguaje regular . Tiene el mismo poder que los autómatas finitos pero menos poderoso que los autómatas de empuje hacia abajo.
4. Máquina de Turing de sólo lectura:
   Es equivalente a los autómatas finitos. Contiene solo un cabezal de lectura que no tiene capacidad de escritura. Solo acepta idiomas regulares.
5. Máquina de Turing unidireccional de solo lectura:
   es similar a los autómatas finitos. Contiene un cabezal de solo lectura y solo puede moverse en una dirección. Acepta un lenguaje regular.