UNIVERSIDAD NACIONAL DE TRUJILLO
Ciencias Físicas y Matemáticas
Escuela de Informática
MÁQUINA DE TURING Y SUS LENGUAJES
LENGUAJES FORMALES Y AUTÓMATAS
Ortiz Suyón Gianmarco
Vargas Morán Vanessa Ximena
Febrero, 2021
1
DEDICATORIA
Dedicamos esta monografía completamente a nuestro maestro mentor Victor Fernando
Passiuri Noriega y a nuestro profesor del curso Carlos Castillo Diestra, quienes nos han
mantenido enfocados y en el camino correcto para la finalización exitosa de este proyecto.
Agradecidos por su preciosa orientación.
También queremos dedicar esta monografía a mis compañeros Alejandro Taboada que en
paz descanse, cuya dedicación y paciencia sirvieron como pilares de apoyo para la
realización de este trabajo. Agradecidos por todo.
Y mucho más importante le dedicamos a Dios, quien nos ha llenado de gran sabiduría y de
mucha paciencia para lograr los objetivos propuestos y por ende lograr la culminación de
nuestra monografía.
2
AGRADECIMIENTO
Agradezco a Dios, en primera
instancia, ya que sin él no tendríamos
la fuerza necesaria para desarrollar
este proyecto de investigación.
También agradezco a mis
compañeros porque con su apoyo
logramos complementar y culminar
muestra monografía, aportando todos
con diferentes ideas. parte de esta
investigación.
3
RESUMEN
En el presente trabajo se sintetizarán conceptos básicos a cerca de la Máquina de Turing:
como las definiciones de la MT, lenguaje y que es la MT, además, hablaremos sobre las
características más importantes de ella y explicaremos su funcionamiento y utilidad,
también sobre los tipos de Máquina de Turing y sus teoremas.
Todo este trabajo realizado en grupo es totalmente de investigación y compilación de
conceptos de diferentes bibliografías y fuentes investigadas. Además, se hará énfasis sobre
todo en el funcionamiento de la Máquina de Turing y como esta puede comprenderse
mejor con Teoría de Autómatas y Lenguajes Formales, finalmente se mencionarán algunas
de sus aplicaciones más importantes en la actualidad.
Y para culminar, se realizará el respectivo anexo del informe realizado y las conclusiones
como puntos de vista de los integrantes que conforman este grupo. También, haciendo sus
respectivas referencias bibliográficas de cada fuente investigada.
4
ABSTRACT
In this paper, basic concepts about the Turing Machine will be synthesized: such as the
definitions of TM, language and what TM is, in addition, we will talk about the most
important characteristics of it and we will explain its operation and usefulness, also about
the types of Turing Machine and their theorems.
All this work carried out in a group is totally research and compilation of concepts from
different bibliographies and sources investigated. In addition, emphasis will be placed
above all on the operation of the Turing Machine and as this can be better understood with
Automata Theory and Formal Languages, finally some of its most important applications
today will be mentioned.
And to conclude, the respective annex of the report made and the conclusions will be made
as points of view of the members that make up this group. Also, making their respective
bibliographical references of each researched source.
ÍNDICE
5
DEDICATORIA___________________________________________________________________2
AGRADECIMIENTO_______________________________________________________________3
RESUMEN_______________________________________________________________________4
ABSTRACT______________________________________________________________________5
INTRODUCCIÓN__________________________________________________________________7
CAPÍTULO 1_____________________________________________________________________8
CONCEPTOS BÁSICOS_____________________________________________________________8
1 DEFINICIONES GENERALES_____________________________________________________8
1.1 Definiciones preliminares:_________________________________________________________8
1.1.1 ¿Qué es la MT?________________________________________________________________________8
1.1.2 Definición de lenguaje__________________________________________________________________8
1.1.3 Definición de la Maquina de Turing________________________________________________________8
CAPÍTULO 2_____________________________________________________________________9
LA MAQUINA DE TURING__________________________________________________________9
2 CARACTERÍSTICAS, FUNCIONAMIENTO Y UTILIDAD_________________________________9
2.1 Características__________________________________________________________________9
2.2 Funcionamiento de la MT_________________________________________________________9
2.2.1 Acciones de la MT_____________________________________________________________________10
2.3 Utilidad de la MT_______________________________________________________________10
CAPÍTULO 3____________________________________________________________________11
CLASIFICACIÓN DE LAS MT________________________________________________________11
3 TIPOS Y TEOREMAS DE LA MAQUINA DE TURING__________________________________11
3.1 Tipos de Maquinas de Turing_____________________________________________________11
3.1.1 Máquina de Turing Multicinta___________________________________________________________11
3.1.2 Máquina de Turing Multiplista___________________________________________________________11
3.1.3 Máquina de Turing Multidimensional_____________________________________________________11
3.1.4 Máquina de Turing no Determinista_______________________________________________________12
3.2 Teoremas de la MT_____________________________________________________________12
3.2.1 Teorema 1___________________________________________________________________________12
3.2.2 Teorema 2___________________________________________________________________________12
3.2.3 Teorema 3___________________________________________________________________________12
3.2.4 Teorema 4___________________________________________________________________________12
3.2.5 Teorema 5___________________________________________________________________________12
CONCLUSIONES_________________________________________________________________13
ANEXOS_______________________________________________________________________14
REFERENCIAS BIBLIOGRÁFICAS_____________________________________________________15
6
INTRODUCCIÓN
En este documento damos a conocer que son las Maquinas de Turing, su clasificación,
características y teoremas que nos servirán de aporte en la resolución de ejercicios en
clase. Dado también su definición y que tipo de lenguaje usar. Por ello, presentamos este
documento con la finalidad de aprender el tema hasta su límite.
CAPÍTULO 1
CONCEPTOS BÁSICOS
7
1 DEFINICIONES GENERALES
1.1 Definiciones preliminares:
1.1.1 ¿Qué es la MT?
Es un módulo de identificación de lenguaje más general que cualquier
autómata finito y de pila, ya que tiene el trabajo de reconocer los lenguajes
regulares y, los independientes de entorno.
1.1.2 Definición de lenguaje
Un lenguaje se puede definir de distintas maneras: como un lenguaje
funcional lingüístico se define como una función relacionarse y comunicarse con
las personas. Como también un lenguaje formal se define como un conjunto de
frases infinitas y son combinaciones con las letras existentes en el alfabeto,
teniendo en cuenta un conjunto de reglas de formación y de sentido.
1.1.3 Definición de la Maquina de Turing
Es un dispositivo informático que se basa en un cabezal de lectura y
escritura, y de una cinta de papel que traspasar la máquina. Esta cinta está
fraccionada en cuadrados, y todos ellos tiene simultáneamente un símbolo. Esta
cinta es la delegada del almacenamiento de la máquina, como transporte de ingreso
y salida, además de funcionar como memoria de trabajo para guardar los resultados
de los pasos intermedios del cálculo.
CAPÍTULO 2
LA MAQUINA DE TURING
8
2 CARACTERÍSTICAS, FUNCIONAMIENTO Y UTILIDAD
2.1 Características
Las principales características de la MT:
Antes de realizar el cálculo la entrada de la cinta consiste en un número finito
de símbolos.
Su cinta tiene una longitud ilimitada.
Su cabezal de lectura y escritura son programables.
Operaciones Fundamentales de la MT: leer, escribir, mover hacia la izquierda
y la derecha, cambiar de estado y detenerse.
Posee la misma capacidad que una computadora moderna para computar
cualquier calculo.
Formada por un alfabeto de entrada y de salida y por un símbolo especial
llamado blanco.
2.1 Funcionamiento de la MT
La MT está formada por, una cabeza lectora, un control finito y una cinta
motorizada en la cual puede haber caracteres, y donde casualmente viene la palabra de
entrada. La distancia de la cinta es infinita hacia la derecha, llenándose los espacios con el
carácter blanco. Pero esta no es infinita hacia la izquierda, por eso hay un cuadro que viene
hacer el extremo izquierdo.
La cabeza lectora al mismo tiempo es de lectura y escritura, por lo que puede ser
modificada en el proceso. Además, la cabeza puede pasar varias veces sobre un mismo
espacio de la cinta generando un movimiento bidireccional.
9
2.1.1 Acciones de la MT
La MT consta de los siguientes pasos:
Lee un carácter en la cinta
Efectúa una transición de estado
Realiza una acción en la cinta
Acción que puede ejecutar la MT:
Escribe un símbolo en la cinta
Mueve la cabeza a la izquierda o derecha
De estas acciones se puede realizar una u otra, pero no ambas a la vez.
Al iniciar la operación, esta inicia en el carácter blanco a la izquierda de la palabra
de entrada. Y decimos que finaliza la operación, cuando se alcanza un estado especial
llamado halt, al llegar a este estado se detiene la operación, aceptando la palabra de
entrada, siendo halt el único estado final.
2.2 Utilidad de la MT
La MT es utilizada como generadora de lenguajes, en compiladores I y II,
máquinas de estado, máquinas autómatas y generadores de códigos.
CAPÍTULO 3
CLASIFICACIÓN DE LAS MT
10
3 TIPOS Y TEOREMAS DE LA MAQUINA DE TURING
3.1 Tipos de Maquinas de Turing
3.1.1 Máquina de Turing Multicinta
En este modelo, la MT tiene k cintas, infinitas en los ambos sentidos, y k
cabezales de L/E. En un solo desplazamiento, esta máquina de Turing: Cambia de
estado dependiendo del estado presente y del contenido de las celdas de cada una
de las cintas, que permanecen analizando en la actualidad las cabezas de
lectura/escritura. Escriben un nuevo signo en todas las celdas barridas por sus
cabezas de lectura/escritura.
3.1.2 Máquina de Turing Multiplista
Es aquella donde cada celda de la cinta de una maquina sencilla se parte en
subceldas. Se dice que la cinta tiene múltiples pistas. Los movimientos que haga
esta máquina requerirá de su estado actual y de la n-tupla que interprete el
contenido de la celda actual.
3.1.3 Máquina de Turing Multidimensional
Es Una MT multidimensional es aquella cuya cinta se expande
infinitamente en más de una dirección, Ejemplo más básico sería el de una maquina
bidimensional cuya cinta se expande infinitamente hacia abajo, arriba, izquierda o
derecha.
3.1.4 Máquina de Turing no Determinista
Es una MT con cinta con límite a la izquierda, que se caracteriza a partir de
un estado y un símbolo puede haber diferentes transiciones.
11
3.2 Teoremas de la MT
3.2.1 Teorema 1
Todo lenguaje aceptado por una Máquina de Turing de algunas cintas es
Recursivamente Enumerable.
3.2.2 Teorema 2
Todo Teorema 2 Sea L = L(M) el lenguaje que acepta una máquina de Turing no
determinista M, entonces hay una máquina de Turing determinista N que acepta
hablado lenguaje, o sea, L(M) =L (N). Idiomas de aparatos de Turing y de
Autómatas
3.2.3 Teorema 3
Sea L el lenguaje aceptado por una máquina de Turing, entonces existe cualquier
Autómata de 2 pilas que acepta L.
3.2.4 Teorema 4
Todo lenguaje Recursivamente Enumerable es aceptado por alguna máquina de 3
contadores.
3.2.5 Teorema 5
Todo lenguaje Recursivamente Enumerable es aceptado por alguna máquina de 2
contadores.
CONCLUSIONES
Hemos observado que, durante esta investigación, Alan Turing fue el hombre que
revoluciono el mundo con su máquina universal de Turing, siendo un concepto abstracto,
12
pero con la capacidad de hacer cualquier operación que los ordenadores modernos sean
capaces de hacer. Los ordenadores simulan la cinta con la memoria y el microprocesador
simula la cabeza y se encarga de leer y ejecutar los programas. De esta misma manera son
las mismas máquinas de Turing, pero mucho mas potentes.
ANEXOS
13
Figure 1: Porcentaje de Plagio
REFERENCIAS BIBLIOGRÁFICAS
Briceño V., Gabriela. (2018). Máquina de Turing., de [Link]. Obtenido de
[Link]
Emmanuel C. (4 de marzo del 2015). La máquina de Turing, sus tipos y aplicaciones.
Obtenido de [Link]
Wikipedia. (s.f.). Wikipedia. Obtenido de [Link]
%C3%A1quina_de_Turing
School, I. B. (08 de junio de 2020). IMF Business School. Obtenido de [Link]
[Link]/blog/tecnologia/procesamiento-lenguaje-natural-modelos-usos-practicos-
202006/
14
Sistemas. (2016). SISTEMAS. Obtenido de [Link]
Wikipedia. (s.f.). Wikipedia. Obtenido de [Link]
%C3%A1quina_de_Turing
Llopis, J. (s.f.). [Link]. Obtenido de [Link]
lenguajes/[Link]#:~:text=Uno%20de%20los%20teoremas%20m
%C3%A1s,(problema%20indecidible%2C%20NP).
M, J. P. (06 de Agosto de 2010). Blogspot. Obtenido de
[Link]
Master Hacks. (20 de Diciembre de 2017). Obtenido de
[Link]
Wikipedia. (26 de Enero de 2017). Wikipedia. Obtenido de
[Link]
(s.f.-e). Máquina de Turing - EcuRed. Recuperado 28 octubre, 2019,
de [Link]
15
