Please enable JavaScript.

Coggle requires JavaScript to display documents.

la maquina de turing ((Máquina de Turing con movimiento de espera, La…

- - - - a máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.
        Las operaciones que se pueden realizar en esta máquina se limitan a:
      - Mover el cabezal lector/escritor hacia la derecha.
      - Visualización de una máquina de Turing, en la que se ve el cabezal y la cinta que se lee.
      - Mover el cabezal lector/escritor hacia la izquierda.
      - El cómputo se determina a partir de una tabla de estados de la forma:
      - (estado, valor) {\displaystyle \rightarrow } \rightarrow (nuevo estado, nuevo valor, dirección)
      - Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta,
        dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.
      - La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco".
        Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, "si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente,
        bien a la izquierda o bien a la derecha".
      - La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido, es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky.
        Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.