9. Mencione 5 ejemplos de aplicación de una Máquina de Turing e ilustre sus funcionamientos.

 Ejemplo 1 - Verificaciones

Queremos construir una máquina que verifique si el número de 0s en una palabra es par:

 

    Supongamos que w = 00010:

    Conclusión: La máquina acepta w = 00010.

 Ejemplo 2 - Máquina de Turing con k cintas

 Ejemplo 3 - Máquina de Turing para cálculo de Funciones

 

Donde x, y están codificados en unario.

Inicialmente x e y se encuentran en la cinta de entrada C1, separados por un símbolo 0, en este orden.

El resultado de f(x,y) queda en C₄.

 

(**) El autómata más restrictivo para estos ejemplos es el Autómata Linealmente Acotado ya que son Lenguajes Sensibles al Contexto (tipo 1). Por razones prácticas se modelaron con una máquina de Turing general.

Ejemplo 4 – Máquinas de Turing como aceptores

 Máquina que acepta el lenguaje de palabras sobre {0, 1}  que comienzan y acaban con el mismo  símbolo.

 Ejemplo 5 – Máquinas de Turing como aceptores

     Máquina que acepta el lenguaje de palíndromos sobre {0, 1}