Mencione las extensiones de la máquina de Turing?

¿Mencione las extensiones de la máquina de Turing?

R= Son estas q se escriben a continuación.

¿En que consisten las Máquinas de Turing de varias cintas?

. Un modelo de MT extendido tiene una cierta cantidad fija de cintas mayor que uno. Un movimiento de esta MT se basa en el estado y en el vector definido por los símbolos señalados por la cabeza de cada una de las cintas. En un movimiento, la MT de varias cintas cambia de estado, sobre escribe los símbolos contenidos en las casillas señaladas por cada una de las cabezas dela cintas y mueve alguna o todas las cabezas de la cinta en determinada dirección. Aunque es capaz de reconocer ciertos lenguajes más rápido que la MT de una sola cinta convencional, la MT de varias cintas no puede reconocer ningún lenguaje que no sea recursivamente innumerable.

¿Mencione la Máquinas de Turing no deterministas?

Es una Máquina de Turing con cinta limitada a la izquierda, que se caracteriza por que a partir de un estado y un símbolo puede haber diferentes transiciones,

El número de transiciones asociado a cada para estado/símbolo SIEMPRE ES FINITO.

¿Mencione la Máquina de Turing con cinta semi-infinita?

. En esta podemos restringir una máquina de Turing para que tenga una cinta que sólo es infinita por la derecha, sin casillas a la izquierda de la posición inicial de la cabeza.

¿Describa la Máquinas multitarea?

Es una máquina de una pila realmente es una autómata pila determinista, mientras que una máquina con dos pilas puede aceptar cualquier lenguaje RE.

¿Que son las Máquinas contadoras?

. Podemos restringir aún más las pilas de una máquina de varias pilas para que sólo contengan un símbolo distinto del marcador de fondo de pila. Así, cada pila se comporta como un contador, lo que nos permite almacenar un entero no negativo y comprobar si el entero almacenado es un0, pero nada más. Basta una máquina con dos contadores para aceptar cualquier lenguaje RE.

¿Qué es la Simulación de una máquina de Turing mediante una computadora real?

. En principio, es posible, simular una máquina de Turing mediante una computadora real si aceptamos que existe un suministro potencial-mente infinito de un dispositivo de almacenamiento extraíble, como por ejemplo, un disco, para simularla parte en que no hay espacios en blanco de la cinta de la MT. Puesto que los recursos físicos con los que se construyen los discos no son infinito, este argumento es cuestionable. Sin embargo, dado que la cantidad de dispositivos de almacenamiento que existe en el universo es desconocida y, sin duda, muy grande, la suposición de

...