Modificaciones a la máquina de Turing estándar

Una máquina de Turing estándar es una máquina que al proporcionar una entrada se mueve hacia la izquierda o hacia la derecha y puede sobrescribir el símbolo existente.

Una TM estándar se puede describir como una tupla de 7:

(Q, X, *, f, q0, B, F) 

where
Q is a finite set of states
X is the tape alphabet
* is the input alphabet
f is a transition function; 
   f: Q × X --> Q × X × {Left_shift, Right_shift}.

q0 is the initial state
B is the blank symbol
F is the set of final states 

Una máquina de Turing estándar es capaz de aceptar algunos de los lenguajes, llamados lenguaje recursivamente enumerable. A ver si haciendo algún tipo de modificación podemos aumentar el número de idiomas aceptados por Turing Machine.

1. Máquina de Turing con opción de permanencia:
   si en lugar de moverse hacia la izquierda o hacia la derecha al ver una entrada, la cabeza también podría permanecer en una posición sin moverse a ningún lado, es decir

   f: Q × X --> Q × X × {Left_shift, Right_shift, Stay}.

   Aún así, la cantidad de idiomas aceptados por la máquina de turing sigue siendo la misma.

2. Máquina de Turing con cinta semi-infinita:
   sabemos que la máquina de Turing tiene una cinta de entrada infinita que se extiende en ambas direcciones (izquierda y derecha) infinitamente. Entonces, si restringimos que se extienda solo en una dirección y no en ambas direcciones, es decir, hacemos que la cinta sea semi infinita, entonces también el número de idiomas aceptados por la máquina de Turing sigue siendo el mismo.
3. Máquina de Turing sin conexión:
   en la máquina de Turing estándar, tanto la entrada como la salida están presentes en la cinta, el jefe tiene la autoridad para moverse a través de la entrada y puede cambiar o modificar la entrada, si no queremos modificar la entrada, podemos proporcionar la entrada en un archivo separado, que se lee solo, entonces el encabezado no puede realizar cambios en él.

   Si la máquina de Turing desea modificar la entrada, la entrada debe copiarse en la cinta y el cabezal puede realizar los cambios, pero aún así el archivo de entrada permanece sin cambios ya que los cambios se realizan en la cinta y no en el archivo. Al hacer tal modificación en la máquina de Turing, la cantidad de idiomas aceptados por la máquina de Turing sigue siendo la misma.

4. Jumping Turing Machine:
   la cabeza de la máquina de Turing estándar puede moverse solo un paso hacia la derecha o hacia la izquierda, pero en el caso de la máquina de Jumping Turing, la cabeza puede moverse no solo un paso hacia la izquierda o hacia la derecha, sino que puede moverse más uno, es decir , 2, 3, 4, 5, 6, etc., o puede saltar a cualquier celda a la derecha o izquierda de la cinta de entrada.

   f: Q × X --> Q × X × {Left_shift, Right_shift} x {n}

   n, es el número de pasos que deseamos mover hacia la derecha o hacia la izquierda. Pero aún así, los idiomas aceptados por la máquina de Turing siguen siendo los mismos.

5. Máquina de Turing sin borrado:
   en la máquina de Turing estándar, el símbolo de entrada se puede cambiar a blanco, pero si eliminamos esta función de cambiar el símbolo de entrada a blanco, este tipo de máquina de Turing se denomina máquina de Turing sin borrado. Podemos reemplazar la entrada con cualquier otro símbolo excepto en blanco. Al hacer esta modificación, la cantidad de idiomas aceptados por la máquina de Turing sigue siendo la misma.
6. Máquina de Turing siempre escribiendo:
   La máquina de Turing estándar nos da la libertad de que al ver una entrada podemos dejarla como está sin hacer ningún cambio, pero en la máquina de Turing siempre escribiendo es obligatorio modificar la entrada cada vez que la vemos, no podemos dejarla como está. es. Pero este tipo de modificación no ayudó a aumentar la cantidad de idiomas aceptados por la máquina de Turing.

Por lo tanto, vemos que a pesar de hacer tantas modificaciones a la máquina de Turing, la cantidad de idiomas aceptados por ella sigue siendo la misma. Por lo tanto, Turing Machine es la máquina más poderosa.