WEBQUEST

Diseñar una máquina de Turing que acepta el lenguaje L = { 0 n 1 n   : n > 0 }

Links para adquirir los conocimientos necesarios y poder elaborar la tarea anteiormente planteada https://www.youtube.com/watch?v=dIVgs0rpcqQ https://www.youtube.com/watch?v=NS-NQ5mCSs8 https://www.youtube.com/watch?v=NS-NQ5mCSs8 Ejemplo: Si el número es par, su último bit es 0. La máquina sólo tiene que cambiar este 0 por un 1. Si el número es impar, su último bit es 1. En este caso, se tiene que cambiar por 0’s todos los 1’s seguidos que haya escritos de derecha a izquierda hasta llegar al primer 0, que se cambia por un 1. Si no hay ningún 0, entonces se tiene que añadir un 1 delante del número (añadir un bit). Es decir, escribir un 1 en la casilla en blanco (B) a la izquierda del número. Vamos a considerar tres estados: q 0 , q 1 , q 2 q 0 , q 1 , q 2 ·          Inicialmente, la MT está en el estado  q 0  con la cabeza señalando la primera cifra del número. La MT recorre todo el número para ver si es par o impar s...

Limitación del alfabeto                                                   5 puntos Idnetificación de estados                                               5 puntos Descripción del funcionamiento                                     5puntos Diseño del diagrama de la máquina de Turing               5 puntos                                                                               Total: 20 puntos

La importancia de la máquina de Turing en la historia de la computación es doble: primero, la máquina de Turing fue uno de los primeros (si no el primero) modelos teóricos para las computadoras, viendo la luz en 1936. Segundo, estudiando sus propiedades abstractas, la máquina de Turing ha servido de base para mucho desarrollo teórico en las ciencias de la computación y en la teoría de la complejidad. Una razón para esto es que las máquinas de Turing son simples, y por tanto amenas al análisis. Dicho esto, cabe aclarar que las máquinas de Turing no son un modelo práctico para la computación en máquinas reales, las cuales precisan modelos más rápidos como los basados en RAM. Link en caso de que se desee profundizar en los diferentes tipos de máquinas de Turing existentes

https://www.matesfacil.com/automatas-lenguajes/Maquina-Turing.html https://www.ecured.cu/M%C3%A1quina_de_Turing investigacionyciencia.es/revistas/investigacion-y-ciencia/miniceras-158/mquinas-de-turing-2271