PDF de programación - Temas de Teoría de la Computación

AUTORES

Julio Ariel Hurtado Alegría

Raúl Kantor
Carlos Luna
Luis Sierra

Dante Zanarini

Temas de Teoría de la Computación

1a ed. - Iniciativa Latinoamericana de Libros de Texto Abiertos (LATIn), 2014. 97 pag.

Primera Edición: Marzo 2014
Iniciativa Latinoamericana de Libros de Texto Abiertos (LATIn)
http://www.proyectolatin.org/

Los textos de este libro se distribuyen bajo una licencia Reconocimiento-CompartirIgual 3.0 Un-
ported (CC BY-SA 3.0) http://creativecommons.org/licenses/by-sa/3.0/
deed.es_ES

Esta licencia permite:
Compartir: copiar y redistribuir el material en cualquier medio o formato.
Adaptar: remezclar, transformar y crear a partir del material para cualquier finalidad.

Siempre que se cumplan las siguientes condiciones:

Reconocimiento. Debe reconocer adecuadamente la autoría, proporcionar un
enlace a la licencia e indicar si se han realizado cambios. Puede ha-
cerlo de cualquier manera razonable, pero no de una manera que sugie-
ra que tiene el apoyo del
licenciador o lo recibe por el uso que ha-
ce.

CompartirIgual — Si remezcla, transforma o crea a partir del material, deberá difun-
dir sus contribuciones bajo la misma licencia que el original.

Las figuras e ilustraciones que aparecen en el libro son de autoría de los respectivos
autores. De aquellas figuras o ilustraciones que no son realizadas por los autores, se

coloca la referencia respectiva.

Este texto forma parte de la Iniciativa Latinoamericana de Libros de Texto abiertos (LATIn),
proyecto financiado por la Unión Europea en el marco de su Programa ALFA III EuropeAid.
El Proyecto LATIn está conformado por: Escuela Superior Politécnica del Litoral, Ecuador
(ESPOL); Universidad Autónoma de Aguascalientes, México (UAA), Universidad Católica de
San Pablo, Perú (UCSP); Universidade Presbiteriana Mackenzie, Brasil(UPM); Universidad de
la República, Uruguay (UdelaR); Universidad Nacional de Rosario, Argentina(UR); Universidad
Central de Venezuela, Venezuela (UCV), Universidad Austral de Chile, Chile (UACH), Uni-
versidad del Cauca, Colombia (UNICAUCA), Katholieke Universiteit Leuven, Bélgica (KUL),
Universidad de Alcalá, España (UAH), Université Paul Sabatier, Francia (UPS).

Temas de Teoría de la Computación

Libro Colaborativo

Proyecto Latin

Julio Ariel Hurtado Alegria

Universidad del Cauca - Colombia 1

Raul Kantor

Universidad Nacional de Rosario - Argentina 2

Carlos Luna

Universidad de la República - Uruguay 3

Luis Sierra

Universidad de la República - Uruguay 4

Dante Zanarini

Universidad Nacional de Rosario - Argentina 5

2014

1Capítulo 2 : Complejidad Computacional
2Capítulos 3, 4 y 5 : Funciones Recursivas - Funciones de Lista - Máquina de Turing
3Ejercicios del Capítulo 1
4Capítulo 1 : Lenguajes, Pruebas y Funciones
5Ejercicios de los Capítulos 3, 4 y 5

Índice general

Definiciones de lenguajes

Definiciones por inducción

1
Lenguajes, Pruebas y Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Palabras y lenguajes
8
1.1
1.2
9
Una excursión a las funciones
1.2.1 Concatenación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3
10
1.3.1 Definiciones por extensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Definiciones por comprensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4
11
1.4.1 Definiciones inductivas por reconocimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.2 Definiciones inductivas declarativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.3 Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5
15
1.5.1 Extensión y comprensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Lenguajes inductivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.2
1.6
Más sobre definiciones inductivas
17
1.6.1 Relaciones inductivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.6.2 Varias definiciones de un mismo lenguaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.3 Definiciones inductivas libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7
20
1.7.1 Contar •: dominios definidos por extensión o comprensión . . . . . . . . . . . . . . . . . 21
1.7.2 Contar •: dominios definidos inductivamente . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
22
1.8

Probando propiedades

Definiciones de funciones

Ejercicios

2
Complejidad Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
25
Algoritmos
2.1
2.2
Corrección de los Algoritmos (Por Inducción)
25
2.2.1 Corrección de Algoritmos Iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2 Corrección de Algoritmos Recursivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
28
2.3
2.4
31
2.5
33
2.5.1 Propiedades de O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Notación Asintótica
Complejidad de Algoritmos Iterativos
Propiedades

2.5.2 Propiedades de Ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.3 Propiedades de Θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.4 Notación o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.5 Notación ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6
35
2.6.1 Enfoque Divide y Vencerás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6.2 Analizando Algoritmos Recursivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6.3 Resolviendo Recurrencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Complejidad de Algoritmos Recursivos

3
Funciones Recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1
Funciones Recursivas Primitivas
43
3.1.1
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.2
Funciones Numéricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.3
Funciones base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.4 Operador Composición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.5 Operador Recursión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.1.6 Conjuntos recursivos primitivos (CRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1.7 Relaciones recursivas primitivas (RRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Función Dupla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.8
Las FRP no alcanzan...
3.2
55
3.2.1
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
La serie de Ackermann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.2
3.3
Funciones Recursivas (FR)
59
3.3.1 Minimizador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Funciones de Gödel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3.2
3.3.3
Funciones Recorrido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3.4 Relaciones Semi-recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3.5
Tesis de Church . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
64
Ejercicios
3.4

4
Funciones Recursivas de Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.1
Introducción
67
4.1.1
Listas finitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2
Funciones de listas
68
4.2.1 Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.2 El poder de cálculo de las FRL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3
73

Ejercicios

5
5.1
5.2
5.3
5.4
5.5

Máquina de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Introducción
77
77
Descripción de la Máquina de Turing
Composición de Máquinas de Turing
79
79
Diagramas de composición
Máquinas elementales
80

Poder de cálculo de las MT
82
5.6
La Máquina Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.6.1
5.6.2 Representación de las funciones recursivas de lista . . . . . . . . . . . . . . . . . . . . . . 83
85
5.7
88
5.8
5.9
89
89
5.10 El problema de la parada
5.11 Ejercicios
91

Representación de MT por FR
Tesis de Church-Turing
Los límites del cálculo

1 — Lenguajes, Pruebas y
Funciones

Números.

Los números de los que hablamos en este texto son los llamados números naturales: 0, 1, 2,
etc. Llamamos N al conjunto de todos los números. Algunos conjuntos de números se representan
convenientemente con las siguientes notaciones:

[a..b]
(a..b]
[a..b)
(a..b)

:= {n ∈ N : a ≤ n y n ≤ b}
:= {n ∈ N : a < n y n ≤ b}
:= {n ∈ N : a ≤ n y n < b}
:= {n ∈ N : a < n y n < b}

Funciones.

Una relación entre dos conjuntos A y B es un subconjunto del producto cartesiano A× B.

Una función de A en B es una relación que además cumple las siguientes condiciones:
totalidad todo elemento de A está relacionado al menos con un elemento de B
funcionalidad todo ele