WEBQUEST

¿Qué es una máquina de Turing y cómo funciona? La llamada “Máquina de Turing” es en realidad un modelo matemático consistente en un autómata que es capaz de “implementar cualquier problema matemático expresado a través de un algoritmo”. A pesar de esta definición tan complicada, en realidad la máquina de Turing destaca por su simplicidad pues manipula símbolos sobre una tira de cinta siguiendo una serie de reglas. A pesar de esta simplicidad, una máquina de Turing puede adaptarse para que simule la lógica de cualquier algoritmo de computador, de ahí su enorme potencial y valor. Como su propio nombre indica, la máquina de Turing fue creada por el matemático inglés Alan Turing, un genio en muchos campos pero especialmente en la criptografía y la lógica. Originalmente la denominó “Máquina de Computación Lógica” siendo una de las mayores aportaciones pues despejó el camino de la ciencia de la Computación, de la Informática moderna. Una Máquina de Turing consta de una cinta i...

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