Máquinas de Turing

Unidad 6

Máquinas de Turing

Start

Integrantes del equipo

Roxana Erika Guadalupe PuigRicardo Arias OrdazAislinn Michelle Aguirre MoralesJosmar De La Paz Hidalgo

Índice

Introducción

6.3 Lenguajes aceptados por la MT

6.1 Definición formal MT

Conclusiones

6.2 Construcción modular de una MT

Referencias

Introducción

La máquina de Turing es un modelo teórico desarrollado por Alan Turing en 1936. Es un dispositivo que puede simular el funcionamiento de cualquier computadora o algoritmo, con el objetivo de estudiar la capacidad de cálculo y las limitaciones de las máquinas. La importancia de la máquina de Turing radica en que se demostró que puede resolver cualquier problema que pueda ser resuelto algorítmicamente.Es un modelo abstracto de computadora que ha sido crucial en el desarrollo de la ciencia de la computación, ya que proporciona una base teórica para comprender los límites y capacidades de los sistemas computacionales.

6.1 Definición formal MT

¿Qué es una máquina de Turing?

Es un dispositivo informático el cual consiste en un cabezal de lectura y escritura. Aunque en realidad es un modelo matemático consistente en un autómata. Está formada por una unidad de control, que puede describirse mediante un autómata finito, una cinta de lectura y escritura, que tiene un comienzo a la izquierda y se extiende indefinidamente hacia la derecha, y un cabezal, que indica la posición de la cinta sobre la que trabaja la máquina en cada paso. Su estructura consiste de un escáner y una cinta de papel la cual se encuentra dividida en cuadrados y cada cuadro contiene un símbolo el cual se encarga del almacenamiento de la máquina.

+ INFO

Maquina

Turning

Caracteristicas

Ejemplos

Uso

6.2 Construcción modular de una MT

La construcción de máquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.

+ INFO

6.3Lenguajes aceptados por la MT

Es el conjunto de todas las cadenas que son aceptadas por MT

Lenguajes Libres de contexto: Son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determínistico o no determínistico. Como toda gramática se definen mediante una cuadrupla G=N, T, S, P. Siendo: N un conjunto finito de símbolos no terminales. T un conjunto de símbolos terminales. P un conjunto finito de producciones. S es el símbolo distinguido o axioma.

Lenguajes formales: que pueden ser generados por una gramática de tipo 0: recursivamente innumerable (r.e).

Un lenguaje L sobre un alfabeto ∑ se dice que es recursivamente enumerable si es aceptado por alguna máquina de Turing, es recursivamente enumerable si para alguna máquina de Turing M tenemos que

Lenguajes regulares: Son las gramáticas más restrictivas y más simples dentro la Jerarquía de Chomsky. Se suelen expresar mediante expresiones regulares. Estan los lineales por la derecha y lineales por la izquierda, las cuales deben contener un símbolo Terminal y como máximo un símbolo no Terminal.

Un lenguaje L es recursivo si L es recursivamente enumerable y hay alguna máquina de Turing que para sobre todas las entradas que acepta L.

+ INFO

+ INFO

Conclusión

En conclusion la maquina de Turing a lo largo del tiempo ha permitido la clasificación de problemas complejos, además también una base teórica sólida para el estudio de la computabilidad y la complejidad computacional. Esta misma a establecido los límites y las capacidades de las computadoras. El tener conocimiento acerca de este tema es importante ya que es esencial para el diseño de algoritmos eficientes y para el avance de la ciencia de la computación.

Referencias

Gabriela, B. V. (2018, mayo 10). Máquina de Turing. Euston96. https://www.euston96.com/maquina-de-turing/ Juan, P. M. (s/f). Máquinas De Turing. Blogspot.com. Recuperado el 3 de junio de 2023, de https://maquinasdeturing.blogspot.com/2010/08/el-objetivo-de-la-creacion-modular-de.html Lenguajes Aceptados Por Máquinas DE Turing. (s/f). Idoc.Pub. Recuperado el 3 de junio de 2023, de https://idoc.pub/documents/lenguajes-aceptados-por-maquinas-de-turing-pqn81o658p41 thoth. (2016). ¿Qué es una máquina de Turing y cómo funciona? https://formatalent.com/que-es-una-maquina-de-turing-y-como-funciona/

Gracias por su atencion