Diferencia entre revisiones de «Máquina de Turing»

La idea subyacente es el concepto de que una máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria 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 [[lenguaje formal|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.

 

== Definición ==