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 Faqs.Zone. Obtenido de

https://www.euston96.com/maquina-de-turing/

Emmanuel C. (4 de marzo del 2015). La máquina de Turing, sus tipos y aplicaciones.

Obtenido de https://es.slideshare.net/emmanuelcolon/la-maquina-de-turing
Wikipedia. (s.f.). Wikipedia. Obtenido de https://es.wikipedia.org/wiki/M
%C3%A1quina_de_Turing

School, I. B. (08 de junio de 2020). IMF Business School. Obtenido de https://blogs.imf

formacion.com/blog/tecnologia/procesamiento-lenguaje-natural-modelos-usos-practicos-
202006/

14
Sistemas. (2016). SISTEMAS. Obtenido de https://sistemas.com/lenguaje-natural.php
Wikipedia. (s.f.). Wikipedia. Obtenido de https://es.wikipedia.org/wiki/M
%C3%A1quina_de_Turing
Llopis, J. (s.f.). Matesfacil.com. Obtenido de https://www.matesfacil.com/automatas-
lenguajes/Maquina-Turing.html#:~:text=Uno%20de%20los%20teoremas%20m
%C3%A1s,(problema%20indecidible%2C%20NP).
M, J. P. (06 de Agosto de 2010). Blogspot. Obtenido de
http://maquinasdeturing.blogspot.com/2010/08/5-clasificacion-de-las-maquinas-de.html
Master Hacks. (20 de Diciembre de 2017). Obtenido de
https://blogs.masterhacks.net/ingenieria/informatica/tesis-de-church-turing/
Wikipedia. (26 de Enero de 2017). Wikipedia. Obtenido de
https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
(s.f.-e). Máquina de Turing - EcuRed. Recuperado 28 octubre, 2019,
de https://www.ecured.cu/M%C3%A1quina_de_Turing

15