Introduccion a la teoria de la computabilidad

63 %
38 %
Information about Introduccion a la teoria de la computabilidad
Technology

Published on February 18, 2014

Author: izyalyth

Source: slideshare.net

INTRODUCCIÓN A LA TEORÍA DE LA COMPUTABILIDAD

This page intentionally left blank

DOMINGO GALLARDO LÓPEZ PILAR ARQUES CORRALES IGNACIO LESTA PELAYO INTRODUCCIÓN A LA TEORÍA DE LA COMPUTABILIDAD PUBLICACIONES DE LA UNIVERSIDAD DE ALICANTE

Publicaciones de la Universidad de Alicante Campus de San Vicente s/n 03690 San Vicente del Raspeig Publicaciones@ua.es http://publicaciones.ua.es Teléfono: 965903480 Fax: 965909445 © Domingo Gallardo López, Pilar Arques Corrales, Ignacio Lesta Pelayo, 2003 de la presente edición: Universidad de Alicante I.S.B.N.: 84-7908-763-3 Depósito Legal: MU-1878-2003 2" edición Diseño de portada: candela + alenda Impresión y encuademación: Compobell, S.L. C/. Palma de Mallorca, 4 - bajo 30009 Murcia Reservados todos los derechos. No se permite reproducir, almacenar en sistemas de recuperación de la información ni transmitir alguna parte de esta publicación, cualquiera que sea el medio empleado —electrónico, mecánico, fotocopia, grabación, etc.—, sin el permiso previo de los titulares de los derechos de la propiedad intelectual.

PRÓLOGO A LA SEGUNDA EDICIÓN En esta segunda edición del libro, hemos querido aplicar las modificaciones que la experiencia docente de la asignatura «Modelos Abstractos de Cálculo», posteriormente denominada «Computabilidad», nos han aportado. Hemos creído conveniente aumentar el número de ejercicios en prácticamente todos los capítulos, y especialmente en el capítulo «Un programa Universal» y en el capítulo en el que se habla de «Decidibilidad e Indecidibilidad» de modo que estos ejercicios ayuden a nuestros alumnos a comprender mejor estos dos temas. También hacemos especial hincapié en el capítulo de «Funciones Recursivas Primitivas», ampliándolo con la notación matemática.

This page intentionally left blank

Prólogo El objetivo fundamental de la Teoría de la Computabilidad es formalizar y estudiar el concepto de computación. Esta teoría surge en los años treinta, mucho antes de que se construyeran los primeros computadores eléctricos. En esas fechas ya existía un tipo de computadores que se utilizaban en laboratorios y universidades, pero no eran máquinas, sino personas que llenaban una sala y que se dedicaban a realizar durante días tediosas operaciones y a pasarse los resultados unos a otros hasta concluir cálculos que hoy en día se realizarían en décimas de segundo1. Para evitar equívocos y malentendidos, querernos dejar claro desde el comienzo que vamos a formalizar en concreto la computación desde el punto de vista del cálculo de funciones matemáticas sobre números naturales mediante ejecución de un algoritmo secuencial. Entendemos un algoritmo (después lo definiremos con más precisión) como un cálculo realizado sobre un conjunto de datos de entrada y que produce un dato de salida. Sin embargo, no trataremos el problema de la computación concurrente, en la que diferentes procesos computan funciones en paralelo, se comunican datos, y los resultados finales dependen del momento en el que los procesos se comunican. La formalización de este tipo de computación es materia de investigación en la actualidad. Este texto tiene su origen en las notas y apuntes que hemos elaborado para la asignatura Modelos Abstractos de Cálculo, una asignatura cuatrimestral de cuatro créditos y medio de segundo curso de las titulaciones de Informática de la Universidad de Alicante. En los años en que la hemos venido impartiendo hemos configurado un temario y un estilo de explicar los contenidos que consideramos plenamente adecuado para las titulaciones informáticas. El texto está por ello principalmente orientado a alumnos de estas titulaciones, haciéndose especial énfasis en relacionar la mayoría de conceptos de la Teoría de la Computabilidad con la experiencia en lenguajes de programación que tienen estos alumnos. Sin embargo, no es necesario en absoluto dominar ninguno para 1 Para dar una idea del enorme salto que se ha dado en poder de computación presentamos la siguiente anécdota. El problema de calcular los movimientos de tres planetas sometidos a atracción gravitatioria fue resuelto en 1929, después de que 56 científicos calcularan las soluciones a las ecuaciones durante 15 (!) años. Hoy en día, esos mismos cálculos apenas ocuparían unas horas de procesamiento de un potente PC.

8 comprender el contenido del texto. En un primer capítulo se repasan los preliminares matemáticos necesarios, como son los conceptos más importantes de la teoría de conjuntos, los métodos de demostración y la numerabilidad. En el segundo capítulo se explica el modelo de Máquina de Turing y sus variantes, se demuestra la equivalencia entre ellas, se definen los conceptos de lenguaje recursivo y recursivamente enumerable y, por último, se enuncia la Tesis de Church. A partir de este capítulo abandonamos las máquinas de Turing y damos un giro al texto. Introducimos el lenguaje L2, un mínimo lenguaje de programación (únicamente tiene cuatro instrucciones), y basamos todo el estudio sobre la Teoría de la Computabilidad en el estudio formal de este lenguaje, de sus posibilidades y de sus limitaciones. En el capítulo tres se introduce, por tanto, este lenguaje de programación para calcular funciones de números naturales, se describe su sintaxis y su semántica. En el capítulo cuatro se presenta otro lenguaje, el lenguaje R, con el que también es posible definir funciones matemáticas, las funciones recursivas primitivas. Comprobaremos que este lenguaje es menos potente que el lenguaje L, en el sentido de que cualquier función que se puede definir en R puede ser definida en L, pero no al contrario. En el capítulo cinco se explica cómo codificar programas y estados de programas en ejecución mediante números naturales, y se introducen una serie de funciones que hace muy sencilla la explicación del Programa Universal, uno de los conceptos más importantes del texto. Por último, en el capítulo final se presenta la teoría de la decidibilidad e indecidibilidad, definiendo primero los conjuntos recursivos y recursivamente enumerables, siguiendo con la demostración de la indecidibilidad de varios problemas (como el del Castor Afanoso o el Problema de la Parada) y terminando con el Teorema de Rice. Cerramos el texto con las soluciones de los problemas que se han ido planteando a lo largo de los capítulos. Esperamos con ilusión que este libro sea un manual útil para todo aquel que desee iniciarse en los conceptos básicos de la Teoría de la Computabilidad. Y agradecemos profundamente las numerosas recomendaciones de los estudiantes que han venido utilizando las versiones iniciales de este texto y que han enriquecido enormemente su contenido. Los autores. Alicante, septiembre de 1997. 2 Hemos implementado un intérprete de este lenguaje, y del lenguaje R que presentamos más adelante, que puede ser usado por cualquier lector. Se encuentra en la dirección Internet ftp://ftp.dtic.ua.es/pub/soft/mac/interp.tgz. Consultar el fichero README del mismo directorio para comprobar sobre qué plataformas es ejecutable.

índice general 1. Preliminares 1.1. Conjuntos 1.2. Tupias 1.3. Funciones 1.4. Predicados 1.5. Alfabetos, cadenas y lenguajes 1.6. Métodos de demostración 1.6.1. Reducción al absurdo 1.6.2. Demostración por inducción 1.7. Codificación 1.7.1. Codificación de pares de números 1.8. Numerabilidad 1.9. Diagonalización 1.10. Problemas 13 13 18 19 21 24 27 27 28 30 30 33 36 38 2. Máquinas de Turing 2.1. Introducción 2.2. El problema de definir un lenguaje 2.2.1. Expresiones regulares 2.3. El modelo conceptual de Máquina de Turing 2.3.1. Funcionamiento de una MT 2.3.2. Representación de una MT 2.3.3. Definición formal de una MT 2.4. Equivalencia de modelos de MT 2.4.1. Máquina de Turing multipista 2.4.2. Máquina de Turing con registro acotado de memoria . . . . 2.4.3. Máquina de Turing multicinta 2.4.4. Máquina de Turing no determinista 2.5. Lenguajes computables y funciones 2.5.1. Lenguajes recursivamente enumerables y recursivos 2.5.2. Las MT como computadores de funciones de naturales ... 2.6. Caracterización de lenguajes con MT generadoras 41 41 42 42 43 44 45 46 50 50 51 54 56 58 58 59 60

10 ÍNDICE GENERAL 2.6.1. Caracterización de los lenguajes recursivos 2.6.2. Caracterización de los lenguajes r.e 2.7. Problemas 62 63 64 3. Funciones L-computables 3.1. Introducción de un lenguaje programación 3.1.1. El lenguaje L 3.1.2. Algunos ejemplos de programas 3.2. Definiciones formales 3.2.1. Notación BNF 3.2.2. Definición de L usando la notación BNF 3.2.3. Semántica de L 3.3. Definición de macros 3.4. Ejemplos de programas 3.5. Funciones L-computables 3.6. Macros genéricas 3.6.1. Asignación 3.6.2. Comparación 3.7. Tesis de Church aplicada al lenguaje L 3.8. Problemas 67 67 67 69 71 72 73 73 77 80 83 85 85 86 87 88 4. Funciones recursivas primitivas 4.1. Definición de las funciones recursivas primitivas mediante la notación matemática 4.2. Introducción al lenguaje R 4.3. Definición formal de R 4.3.1. Sintaxis del lenguaje R 4.3.2. Semántica del lenguaje R 4.3.3. Funciones recursivas primitivas 4.4. Constructores avanzados 4.4.1. Predicados 4.4.2. Iteradores acotados 4.4.3. Cuantificadores acotados 4.4.4. Minimización acotada 4.5. Una función L-computable total no recursiva primitiva 4.5.1. Minimización no acotada 4.5.2. Funciones recursivas-u 4.6. Problemas 91 91 93 98 99 99 101 102 102 105 106 107 111 113 114 114 5. Un programa universal 5.1. Numeración de Gódel 5.1.1. Función de codificación 5.1.2. Función de descodificación 119 119 120 121

ÍNDICE GENERAL 5.2. Codificación de programas L 5.2.1. Codificación de instrucciones 5.2.2. Codificación y descodificación de programas 5.3. Codificación de ejecuciones de programas 5.3.1. Codificación de instantáneas 5.3.2. La función Inst 5.4. El programa universal 5.4.1. El predicado PASOS 5.4.2. El programa universal 5.5. Problemas 11 122 123 124 128 128 130 133 133 134 136 6. Decidibilidad e indecidibilidad 6.1. El problema de la parada 6.2. El castor afanoso 6.3. Conjuntos decidibles e indecidibles 6.3.1. Conjuntos recursivos 6.3.2. Conjuntos recursivamente enumerables 6.3.3. Conjuntos recursivos y recursivamente enumerables 6.3.4. Conjuntos recursivamente enumerables y funciones 6.4. Conjuntos no recursivos 6.4.1. El conjunto K 6.5. Conjuntos no recursivamente enumerables 6.5.1. El conjunto K 6.5.2. El conjunto TOT 6.6. Reducción 6.6.1. El conjunto KQ no es recursivo 6.6.2. El conjunto NO_VACíO no es recursivo 6.6.3. El conjunto VACÍO no es r.e 6.6.4. El conjunto FINITO no es r.e 6.7. Teorema de Rice 6.8. Problemas 141 141 143 147 147 148 150 153 155 155 157 157 158 159 161 162 164 165 166 168 A. Soluciones 171 A.l. Preliminares A.2. Máquinas de Turing A.3. Funciones L—computables A.4. Funciones recursivas primitivas A.5. Un programa universal A.6. Indecidibilidad 171 182 190 201 208 219

This page intentionally left blank

Capítulo 1 Preliminares Para definir la computación de forma matemática vamos a necesitar una colección de conceptos que presentamos en este capítulo. De todos ellos los fundamentales serán los conceptos de conjuntos de números naturales y de lenguajes, con los que podremos definir formalmente un algoritmo. También tocaremos de pasada en este capítulo el concepto de infinito. Alguien puede comenzar a preguntarse por qué es necesario utilizar conjuntos infinitos para caracterizar la computación. De hecho nuestros computadores siempre tendrán características finitas: su memoria estará limitada, y sus cálculos se completarán en un tiempo finito. La necesidad de utilizar el infinito (suponer, por ejemplo, que el modelo de computador va a tener una memoria infinita) se comprende si entendemos este concepto en su acepción de no limitado. Si limitáramos las capacidades de los ordenadores (en memoria o tiempo de ejecución) existirían problemas que no podrían ser resueltos precisamente por causa de estos límites, porque necesitarían más recursos. Al suponer capacidades infinitas no imponemos límites al tamaño de los problemas que vamos a tratar. En capítulos posteriores veremos que, aun con esta suposición, habrá problemas que serán imposibles de resolver. 1.1. Conjuntos Uno de los retos fundamentales de la teoría de la computabilidad es el de encontrar mecanismos para representar efectivamente conjuntos de objetos, posiblemente infinitos, de forma que podamos decidir si un determinado objeto es o no un elemento del conjunto definido. A lo largo del texto exploraremos distintas cuestiones sobre la definición y representación computacional de conjuntos, como qué tipos de conjuntos son susceptibles de ser representados, qué formas de representación finita pueden utilizarse para codificar conjuntos infinitos y si existen conjuntos imposibles de ser definidos computacionalmente. Para comenzar, pues, es interesante partir de la noción de conjunto.

CAPÍTULO 1. PRELIMINARES 14 Definición 1.1 Llamaremos conjunto a toda agrupación de objetos bien definidos y diferenciables unos de otros. Utilizaremos la palabra clase como sinónimo de conjunto. Normalmente utilizaremos letras mayúsculas, como R, 5, T, [7,... para nombrar conjuntos, y letras minúsculas, como x, y, z,... para representar elementos de los conjuntos. En los capítulos siguientes definiremos algunos conjuntos, como por ejemplo PARES, KQ, Wx o VACÍO, cuyos nombres representaremos en negrita. Esta negrita indicará que el conjunto está definido para todo el texto1 y servirá para distinguirlos de nombres de conjuntos genéricos, como los vistos anteriormente .ñ, 5, T, [7, que utilizaremos como variables libres cuya definición tendrá el alcance de un teorema o una definición. Definición 1.2 Para indicar que un elemento x pertenece a un conjunto S escribimos x € 5. Al contrario, x ^ S denotará que el elemento x no pertenece al conjunto S. Los conjuntos fundamentales con los que vamos a trabajar en este texto son conjuntos de números naturales y conjuntos de cadenas (lenguajes). Más adelante definiremos el concepto de lenguaje. Definición 1.3 Denominaremos N al conjunto de números naturales. 0,1,2,3,4,5,... Siempre que se utilice la palabra número tendremos que entender que nos estamos refiriendo a número natural, salvo que se diga lo contrario. Por defecto, en las definiciones de conjuntos, las variables ar, y, z representarán números naturales, siempre que no se diga lo contrario. Definición 1.4 Llamaremos conjunto vacío al conjunto que no tiene elementos, y lo denotamos con el símbolo 0. La noción de conjunto vacío nos va a ser muy útil para simplificar notaciones y eliminar casos especiales en teoremas y demostraciones. Definición 1.5 El cardinal de un conjunto es el número de elementos del mismo. Denotamos por S al cardinal del conjunto S. Por ejemplo, el cardinal del conjunto vacío es O, |0| — 0. 1 Todos los conjuntos, funciones, predicados, nombres de programa, etc., que se utilicen en más de una ocasión aparecen en el índice de materias, situado al final del libro, para que sea sencilla la localización de sus definiciones.

15 1.1. CONJUNTOS Definición 1.6 Diremos que un conjunto es finito cuando tiene un número finito de elementos. La forma usual de expresar conjuntos que contienen un número finito de elementos es mediante una enumeración de dichos elementos. Ejemplo 1.1 Podemos escribir R = {0,1,2, 3,4} para representar el conjunto de los números naturales menores que 5. o2 En un conjunto no distinguimos ni el orden ni las repeticiones de elementos. Así, las expresiones {1,3,5}, {3,1,5} y {5,3,1} están denotando al mismo conjunto. Al intentar, sin embargo, representar conjuntos infinitos^, no son válidas expresiones como las anteriores. Como hemos mencionado antes, el problema de representar conjuntos infinitos de una forma finita es uno de los problemas centrales de la teoría de la computabilidad. Definición 1.7 Diremos que un conjunto es infinito cuando tiene un número infinito de elementos. Una notación muy utilizada para representar conjuntos infinitos es la siguiente, IMPARES - { 1 , 3 , 5 , . . . } , donde los tres puntos simbolizan una lista infinita, en este caso la formada por todos los números impares. Evidentemente, las limitaciones de esta notación son enormes. Por un lado deja al lector toda responsabilidad de interpretar cuál es el conjunto que se define y por otro sólo sirve para representar conjuntos elementales ya conocidos. Otra forma de representar estos conjuntos, más relacionada con técnicas de notación que avanzaremos posteriormente, es la que utiliza un predicado o una propiedad que deben cumplir aquellos elementos que pertenezcan al conjunto. Ejemplo 1.2 IMPARES = {x | x no es divisible por 2} denota el mismo conjunto de todos los números impares. 2 El símbolo O significa que se ha alcanzado el final de un ejemplo, de una demostración o de un teorema. 3 No vamos a dar aquí una definición formal de conjunto infinito, ya que tal definición va más allá del alcance del presente libro. Consultar [?].

16 CAPÍTULO1.PRELIMINARES Definición 1.8 Diremos que dos conjuntos R y S son iguales, y lo denotamos por R = S, cuando tienen exactamente los mismos elementos. Cuando existe algún elemento que pertenece a uno de ellos y no al otro, decimos que son conjuntos distintos, R ^ S. Definición 1.9 Decimos que un conjunto R es subconjunto de otro S, y se denota R C S, cuando todos los elementos de R pertenecen también a S. Así, R = S sii4 R C S y S C -ñ, por lo que para demostrar que R = S debemos demostrar las dos inclusiones. Hay que hacer notar que para cualquier conjunto R se cumple que 0 C R y RCR. Definición 1.10 Diremos que un conjunto R es un subconjunto propio de S, cuando R C S y R / 5. Dos conjuntos pueden combinarse para dar lugar a otro conjunto mediante operaciones de conjuntos. Definición 1.11 Dados dos conjuntos R y S definimos su unión, que se escribe como R U 5, como el conjunto de aquellos elementos que pertenecen a R, a S o a ambos: Ejemplo 1.3 Definición 1.12 Dados dos conjuntos R y S definimos su intersección, que se denota por R(~]S, como el conjunto formado por aquellos elementos que pertenecen a R y a S al mismo tiempo: Ejemplo 1.4 {1,2,3,4} n {4,5,6,7} = {4}. 4 Traducción literal del inglés iff. Es una abreviatura de la expresión si y sólo si.

17 1.1. CONJUNTOS Definición 1.13 Dados dos conjuntos R y S definimos su diferencia, escrita como R — S, como el conjunto formado por aquellos elementos que pertenecen a R y no pertenecen a S. Así, R- S = R-(RnS}. Hay que hacer notar que la diferencia de conjuntos no es una operación simétrica, con lo que R — S ^ S — R. Ejemplo 1.5 PARES = N- IMPARES. Normalmente, todos los conjuntos con los que trabajemos estarán definidos dentro de un determinado dominio o universo, esto es, todos ellos serán subconjuntos de un conjunto dado D. Siempre que no se diga lo contrario, el dominio de un conjunto será N. Definición 1.14 Definimos la operación complementario de un conjunto R, y lo escribimos como R, como el conjunto de aquellos elementos que pertenecen a D y no pertenecen a R, esto es, R = D — R. Ejemplo 1.6 Otra forma de definir el conjunto de los números pares es PARES=IMPARES. Ya que se definen los conjuntos como colecciones de elementos, sin hacer ninguna salvedad sobre el tipo de elementos que podemos considerar, es posible formar conjuntos que tengan otros conjuntos como elementos. Definición 1.15 Llamaremos colecciones a aquellos conjuntos cuyos elementos son otros conjuntos5. 5 El problema que sufren este tipo de conjuntos es que su utilización puede dar lugar a paradojas o contradicciones. Una de las más conocidas es definir S como la colección de aquellos conjuntos que no pertenecen a si mismos. La paradoja aparece al intentar determinar si S pertenece a si mismo o no.

CAPÍTULO 1. 18 PRELIMINARES Utilizando colecciones de conjuntos es posible definir uniones e intersecciones de más de un conjunto. Definición 1.16 Si S es una colección de conjuntos, definimos JS como el conjunto formado por todos los elementos que pertenecen a los conjuntos de S. De forma análoga se define f| S como el conjunto formado por todos los elementos que pertenecen a todos y cada uno de los conjuntos de S al mismo tiempo. Ejemplo 1.7 Si definimos S = {{O, 2,4, 6}, {1, 3, 5}, {10,12,16}, {11,13,15}}, entonces Definición 1.17 Denominamos conjunto potencia o partes de S, y denotamos 2 o P(S) a la colección de todos los posibles subconjuntos de un conjunto S. Ejemplo 1.8 P({1,2}) = {0,{1},{2},{1,2}}. Hay que hacer notar que el conjunto vacío y el propio conjunto siempre son elementos de cualquier conjunto potencia. 1.2. Tupias A diferencia de los conjuntos, en las tupias sí que importa el orden en que los elementos están definidos.

19 1.3. FUNCIONES Definición 1.18 Representamos una n-tupla como una lista de n elementos encerrados entre paréntesis, en lugar de entre llaves: (ari,x2,...,arn). Es posible que existan elementos repetidos dentro de las n-tuplas. Por ejemplo, una 4-tupla correctamente definida sería (1, 2, 2, 1). Las 2-tuplas se denominan pares ordenados y denominaremos a las 3-tuplas tripletas ordenadas. Una 1-tupla no se distinguirá del elemento propiamente dicho, a diferencia de los conjuntos. Definición 1.19 Decimos que dos n-tuplas son iguales, (xi,X2,...,Xn) = (2/l,y2,-..,2/n), su £i=2/i, #2 = 2/2, ••-, xn = yn. Definición 1.20 Dados n conjuntos Si,S<¿,...,Sn, representamos por S x 52 x . . . x Sn a el conjunto formado por todas las n-tuplas (#1, # 2 , . . . , x n ) tal que Este conjunto se denomina producto cartesiano de S,S-2,,...,Sn. En caso de que Si — 82 = • • • — Sn, denominamos Sn al producto cartesiano Si x S2 x . . . x SnEjemplo 1.9 Si 5 = (0,1, 2} y R = (2,3}, entonces 5 X j R = {(0,2),(0,3),(l,2),(l,3),(2,2),(2,3)}. 1.3. Funciones Uno de los conceptos que utilizaremos más frecuentemente es el de función.

20 CAPÍTULO 1. PRELIMINARES Definición 1.21 Definimos una función / como un subconjunto de pares ordenados (x, y) de D x R, donde D se denomina el dominio, u origen, de f y R el rango, o imagen, de f , tal que cumplen la propiedad de que un elemento del conjunto origen no puede tener dos imágenes: Se suele denotar una función f con dominio D y rango R como En la notación usual para funciones, decimos que f ( x ) — y para significar que (x,y)€f. De aquí en adelante restringiremos las funciones que estudiemos a aquellas en las que el dominio y el rango es el conjunto de números naturales (/ : N -> N). Esto no limita el alcance de los resultados que obtengamos, ya que, mediante una codificación adecuada, es posible expresar cualquier función definida sobre objetos arbitrarios como una función sobre naturales. Veremos más adelante ejemplos de tales codificaciones. Ejemplo 1.10 Como ejemplo de función, podemos considerar / como el conjunto de pares ordenados ( x , x2) para x £ N. En esta función para cada x E ./V, f ( x ) = x2. En general manejaremos también funciones definidas sobre más de una variable, (/ : TV x N x ... TV —> N] denotándolas por / ( n i , . . . , n¿). Estas funciones se dicen que son fc-arias. Como notación particular, las funciones I-arias y 2-arias se denominan uñarías y binarias. En ciertas partes del libro utilizaremos la notación f^ para hacer ver que la función / es fc-aria. Definición 1.22 Si el dominio de f es D y escogemos un x E D tal que (#, /(#)) £ /, decimos que f ( x ) está definido, y escribimos f ( x ) =|. Para todos los x G D tal que ( x , f ( x ) ) £ / decimos que f ( x ) no está definido, y escribimos f ( x ) =tDefinición 1.23 Decimos que una función es parcial, cuando no está definida para algunos valores de D, esto es, no está definida para ciertos elementos de su dominio.

1.4. PREDICADOS 21 Ejemplo 1.11 Un ejemplo de una función parcial es la función f ( x ) = ^/x, definida para el conjunto de cuadrados perfectos, pero no definida para el resto (recordemos que las funciones que manejamos son de N en TV). En el caso de f ( x ) = >/#, Definición 1.24 Denominamos función total, a una función definida para todos los valores de D. Cuando hablemos de funciones, en general, no estaremos especificando si son parciales o totales y los enunciados que realicemos serán aplicables a ambas. Las definiciones anteriores son fácilmente aplicables a funciones fc-arias. Podemos definir los siguientes tipos de funciones. Definición 1.25 Decimos que una función f : D —)• R es inyectiva cuando no existen valores del dominio que tengan imágenes repetidas, esto es, para toda pareja de valores x,y G D, f ( x ) — f(y) implica que x = y. Decimos que una función / es suprayectiva cuando para todo y E R existe un x tal que f ( x ) = y. Por ultimo, decimos que una función es biyectiva cuando es inyectiva y suprayectiva. Ejemplo 1.12 La función f ( x ) = x mod 7, donde a cada número x le corresponde el resto de su división por 7 no es inyectiva, ya que, por ejemplo, /(10) = /(24) = 3. La función f ( x ) = x2 es inyectiva, pero no es suprayectiva, ya que, por ejemplo, el 5 no es la imagen de ningún x. La función f(x) — x es biyectiva. 1.4. Predicados Definición 1.26 Definimos como predicado sobre un conjunto S a una función total P : 5 —> {0,1}; de forma que para cada a E S, o bien

CAPÍTULO 1. PRELIMINARES 22 P(a) = 1 o P(a) = O, donde 1 y O se definen como valores de verdad, y equivalen a VERDADERO y a FALSO, respectivamente. Normalmente, se dirá que el número a satisface P cuando P(a) — 1 y que a no satisface P cuando P(a) = 0. De esta forma, un predicado es una clase especial de funciones con valores sobre {0,1}. Normalmente el conjunto S al que se refiere la definición también será N. Utilizaremos las letras mayúsculas P, Q, R para denotar predicados genéricos. Ejemplo 1.13 Como ejemplos de predicados, podemos citar los siguientes x < 5, definido por la función Menorlgual5(x) = 1 si x = 0,1, 2, 3,4, 5 O en otro caso Par (o;), definido por la función Par(z) = 1 si existe t/ G -/V tal que x — 2y O en otro caso Definición 1.27 Dados una pareja de predicados P, Q, definimos las operaciones básicas sobre ellos: negación, disyunción y conjunción, denotadas por ->P, P V Q y P A Q según la siguiente tabla de verdad P II -P PQ i 0 i 1 i i 0 0 0 1 0 0 P V Q ||_P A Q 1 1 1 0 1 0 0 0 Ejemplo 1.14 Podemos utilizar los predicados vistos en el ejemplo anterior para construir nuevos predicados:

23 1.4. PREDICADOS -< Menor Igual5(:c) = 0 si x = 0,1,2,3,4,5 1 en otro caso Menorlgual5(^) A Par(x) = Menorlgual5(rc) V Par(x) = 1 si z = 2,4 O en otro caso 1 si existe y G N tal que x = 2y o x = O,1,3, 5 O en otro caso Comentábamos anteriormente la importancia de poder caracterizar formalmente conjuntos infinitos, de forma que: a) dado un número, podamos decidir si pertenece al conjunto y b) podamos listar aquellos números naturales que pertenecen al mismo. Las siguientes definiciones remarcan el papel de los predicados en la caracterización de conjuntos. Definición 1.28 Decimos que el predicado P es la función característica del conjunto R, cuando R es el conjunto de todos los naturales para los cuales P(a) = 1. Escribiremos que P(x) = 1 si x € R O en otro caso Ejemplo 1.15 El predicado Par (o?) es la función característica del conjunto PARES. Definición 1.29 De forma contraria, dado un predicado P, diremos que R es el conjunto asociado a P, si R es el conjunto de aquellos naturales para los que el predicado P es cierto. R = {x£N P(x}} Ejemplo 1.16 El conjunto PARES es el conjunto asociado al predicado Par(x).

24 CAPÍTULO 1. 1.5. PRELIMINARES Alfabetos, cadenas y lenguajes Alfabetos, cadenas y lenguajes son algunos de los objetos esenciales sobre los que, históricamente, se construye la teoría de la computabilidad. Esto es debido a que son los objetos con los que trabajan gramáticas y máquinas de Turing. Sin embargo, siempre será posible utilizar números naturales y conjuntos de naturales en su lugar, ya que es muy sencilla la conversión de cadenas en números naturales y viceversa. Definición 1.30 Definimos un alfabeto E, como un conjunto finito de objetos llamados símbolos. Normalmente utilizaremos como símbolos de alfabetos las letras a, 6, c , . . . los dígitos 0,1,2,... 9 y algún símbolo especial como $ o #. Cuando sea necesario utilizar un alfabeto con número n indefinido de símbolos, utilizaremos los símbolos «1,^2, • • • ianDefinición 1.31 Denominaremos cadena o palabra a una n-tupla de símbolos de E. En lugar de escribir (x, #2, • • • , xn) escribiremos simplemente xx^ ... xn. La longitud de la palabra u = xx<¿ ... xn es n, y se denota como |w| = n. Existe una palabra de longitud O, que denominaremos A y llamaremos cadena vacía. Normalmente utilizaremos las letras w, v, u>, x,y,z y las letras griegas a, /3,7,... para denotar palabras. A diferencia de los conjuntos, no distinguiremos el símbolo a G S de la cadena de longitud 1 formada por ese símbolo. Definición 1.32 Si u,v son dos cadenas del alfabeto S, denominamos concatenación de u y v a la cadena de S formada por colocar la cadena v a continuación de u, y denominamos a esta cadena u • v o, simplemente, uv. Ejemplo 1.17 Si S = {a, 6, c}, u — aabb y v = cbc, entonces uv = aabbcbc Para cualquier u se cumple que y vu = cbcaabb.

1.5. ALFABETOS, CADENAS Y LENGUAJES 25 y que, para cualquier v,w adicional u(vw) — (uv}w. También se cumple que si uv = uw y vu — wu, entonces v = w. Definición 1.33 Una cadena u es una subcadena de v si y sólo si existen dos cadenas x, y tales que v = xuy. Tanto x como y pueden ser A, por lo que un cadena es una subcadena de si misma. Si únicamente x = A, decimos que u es un prefijo de v. Si únicamente y = A, se dice que u es un sufijo de v. Ejemplo 1.18 La cadena aa es un prefijo de aaba y un sufijo de baa. Definición 1.34 Definimos la exponenciación sobre cadenas. Si u es una cadena, denotamos por un, donde n£Nyn>Qala cadena obtenida por concatenar n veces la cadena u consigo misma, esto es, Si n = O entonces un — A. Definición 1.35 Otra operación sobre cadenas es la inversión, denotada por UR. Podemos obtener el inverso de una cadena u, UR, escribiendo u en sentido inverso; esto es, si u = aia>¿ ... an, entonces UR = an ... a^ai. Se cumple que R = A y que, para toda cadena de E, (uv)R = VRUR. Denominamos palíndromos a aquellas cadenas que cumplen que u = UR. Ejemplo 1.19 Son palíndromos las cadenas 00100, 101 y O, definidas sobre el alfabeto {0,1}. Definición 1.36 Un lenguaje sobre E o un lenguaje con alfabeto E es cualquier conjunto L de cadenas de E.

26 CAPÍTULO 1.PRELIMINARES Ejemplo 1.20 Dado £ = {0,1} podemos definir los siguientes lenguajes de S : LI = {0,01,011,0111,...} L2 = {01,0011,000111,...} L3 = {10,11,101,111,1011,...} donde LI es el conjunto de todas las cadenas que comienzan por O y tienen a continuación O o más unos, L2 es el conjunto de las cadenas de forma O n l n y, L% es el conjunto de los códigos binarios de números primos. Uno de los problemas fundamentales en Teoría de la Computabilidad es la especificación de lenguajes. Un lenguaje finito puede especificarse listando todas sus cadenas. Veremos más adelante métodos para especificar lenguajes genéricos. Al ser los lenguajes conjuntos, podemos aplicar operaciones booleanas a los lenguajes. Definición 1.37 Sean LI y L2 dos lenguajes cualesquiera. Denotamos su unión como LI U L2, su intersección como LI fl L2 y su diferencia como LI — L2. La concatenación de dos lenguajes se define como la concatenación de todas las palabras que pertenecen a ellos. Definimos, por último, la cerradura estrella y la cerradura. Definición 1.38 Dado un lenguaje L, denominamos cerradura estrella de L (y se denota por L*) al conjunto de todas las cadenas que se pueden formar concatenando cadenas de L con otras cadenas de L un número finito de veces y denominamos cerradura positiva de L (y se denota por L+) al conjunto Utilizando esta operación, £*, es el conjunto de todas las palabras posibles generables con el alfabeto E, incluyendo la cadena vacía. Y E+ denota al conjunto de todas las cadenas no vacías

1.6. MÉTODOS DE DEMOSTRACIÓN 27 Ejemplo 1.21 Por ejemplo, supongamos que L — {a}, entonces Si S ={a,b}, entonces 1.6. Métodos de demostración Uno de los elementos propios de las matemáticas es su rigor. La corrección de las proposiciones que se realizan, que son llamadas teoremas (y también corolarios y lemas) deben ser demostradas de forma general. La necesidad de utilizar demostraciones rigurosas aparecerá clara en el siguiente ejemplo. Consideremos la proposición n 2 — n + 41 es primo para todo n E N. Para comprobar si la proposición es cierta o falsa, deberíamos comprobarla para todo número natural. No vale probar para unos pocos números naturales. De hecho, la expresión es falsa, pero es verdadera para los valores n < 40. Las técnicas de demostración pretenden resolver estos problemas y permitir comprobar aserciones que afectan a un número infinito de objetos. En una demostración se parte de una proposición cuya corrección es admitida por todos (que se denomina formalmente un axioma) y, mediante la aplicación de un conjunto de reglas de inferencia válidas se llega a la proposición que se quiere demostrar. La rama de las matemáticas que se ocupa de estudiar los sistemas formales de demostración es la Lógica. Al no ser este un texto sobre lógica, no vamos a ser demasiados estrictos en la aplicación de estos sistemas formales, sino que vamos a tratar de guardar un equilibro entre la claridad y el rigor en las demostraciones. Repasaremos en este apartado los métodos de demostración que van a ser más usados en el resto del libro, a saber, el método de la reducción al absurdo y el método de la inducción. 1.6.1. Reducción al absurdo Comencemos con el método de la reducción al absurdo. En este método se supone que la proposición que se intenta demostrar como verdadera es falsa.

28 CAPÍTULO 1. PRELIMINARES Entonces utilizamos su negación como punto de partida de una derivación de proposiciones que deben dar lugar a una contradicción. En su forma más sencilla, una contradicción es una pareja de proposiciones una de las cuales es la negación de la otra. Ya que ambas proposiciones no pueden ser ciertas, se demuestra entonces que el punto de partida de la derivación es falso, por lo que la proposición que queremos demostrar es cierta. Para explicar mejor el método veamos un ejemplo. Teorema 1.1 Sea x € {a, b}* una cadena que cumple que xa = ax. Entonces x = an, siendo n E N. Demostración Siguiendo el método de reducción al absurdo, negamos la proposición e intentamos derivar una contradicción a partir de ella. Esto es, suponemos que xa — ax, pero x contiene la letra 6. Supongamos que el símbolo b aparece en x en la posición i. Entonces podemos expresar x como al~lbw, siendo w una cadena cualquiera. Si la cadena x cumple el teorema, debe cumplir que a(al~lbw] ~ (al~lbw}a, esto es, albw = a1 lbwa. O sea, abw — bwa, lo cual es una contradicción, ya que una cadena no puede comenzar tanto por a como por b. Y esta contradicción demuestra el teorema. 1.6.2. Demostración por inducción La técnica de la demostración por inducción se utiliza para los casos en los que una determinada proposición P, que depende de n, es cierta para todo valor finito de n. Los pasos a seguir para aplicar la técnica son los siguientes: 1. Caso base. Debemos demostrar que P es cierto para n — 0. 2. Hipótesis de inducción. Suponemos que la proposición P es cierta para n = 1,...,/?.

1.6. MÉTODOS DE DEMOSTRACIÓN 3. 29 Paso de inducción. Usando la hipótesis de inducción, debemos de demostrar que P es cierta para n = k + 1. Un ejemplo de utilización de la inducción es el siguiente teorema Teorema 1.2 Para todo n E N se cumple que Demostración Caso base. El caso base, n = O, se demuestra trivialmente, ya que la proposición establece simplemente que 1 = I 2 . Hipótesis de inducción. Supongamos entonces que el resultado se cumple para n = k. O sea, que Paso de inducción. Entonces debemos demostrar que, suponiendo cierta la expresión anterior, la ecuación se satisface para n — k + 1 que es el resultado al que deseábamos llegar para k + 1. Otro ejemplo es la siguiente proposición. Teorema 1.3 Para cualquier conjunto S se cumple que P(S) = 2' 5 L Demostración Caso base. Si S = O entonces S = 0. En este caso, P(0) = {0}, cuyo cardinal es 1. Lo cual es consistente con la proposición, ya que 2° = 1. Hipótesis de inducción. Suponemos que la proposición es cierta para |5| < &. Estoes, que |P(5)| = 2 l 5 L Paso de inducción. Sea 5 cuyo cardinal es k + 1. Al ser |5| > 1, podemos afirmar que 5 = TU{SI}, siendo si algún elemento del conjunto 5 y T el conjunto S— {si}. El conjunto T cumple la propiedad, ya que su cardinal es k. Así, podemos afirmar, utilizando la hipótesis de inducción, que |P(T)| = 2 fc .

30 CAPÍTULO 1. PRELIMINARES También podemos asegurar que el conjunto potencia de S puede dividirse en dos subcolecciones con el mismo número de elementos: la colección de aquellos conjuntos de P(S) que no contienen el elemento si y la colección de aquellos que sí que lo contienen. El primero de ellos es P(T), y el segundo es precisamente el resultado de añadir s a cada uno de los conjuntos de P(T). Formalmente, De esta forma, y ya que 1.7. se cumple que Codificación En capítulos siguientes vamos a necesitar codificar elementos de un determinado conjunto en elementos de otro conjunto. Por ejemplo, veremos que es posible codificar programas definidos en un determinado lenguaje mediante números naturales , o que es posible codificar como un número natural cualquier tupia de naturales de cualquier longitud. Definición 1.39 Decimos que codificamos un conjunto Si mediante un conjunto 82 cuando podemos definir una función codificadora, / : 5i —>• 82, y una función decodificadora, g : 82 —>• Si, tal que para todo x £ Si se cumple que g(f(x)) = x. Para ello, f y g deben cumplir las siguientes propiedades: 1. Ambas funciones son inyectivas, esto es, para un elemento x de Si sólo existe un elemento y de 82 tal que f ( x ) — y, y para un elemento y de 82 sólo existe un elemento x de Si tal que g(y) = x. 2. Además, la función f debe ser total, esto es, debe estar definida para todo elemento de S. 1.7.1. Codificación de pares de números Veamos, por ejemplo, cómo codificar pares de números naturales, N x TV, mediante números naturales. Esto es, queremos encontrar una forma de asignar a cada par de números naturales (a, 6) un número c de forma que se cumplan las condiciones anteriores. Por ejemplo, una función que no serviría como función que codifica estos pares de números naturales sería la siguiente

31 1.7. CODIFICACIÓN /(o, 6) = 0 + 6, ya que, según esta función codificadora, los pares (1,2) y (2,1) (y, por extensión, cualquier par de tupias (0,6), (6,0)) tendrían la misma codificación. Definición 1.40 Definimos la función codificación de pares de números de la siguiente forma /(o, 6) =< (o, 6) >=< o, 6 >= 2°(26 + !)-!. Ejemplo 1.22 La codificación del par (3,2) sería < 3 , 2 > = 2 3 ( 2 - 2 + 1) -1 = 39. La función < a, b > es biyectiva, ya que para pares de números distintos se obtienen códigos distintos y, además, no existe ningún natural que no sea la codificación de un par de números. Una justificación informal de esta biyección puede verse en la figura 1.1. En la tabla a) aparece la función 2°(26 + 1) (esto es, < a, b > -fl) y se puede comprobar con ella cómo se construye la función codificadora. Para a = O, cuando b toma los valores desde O en adelante, la función codificadora devuelve los números impares. Para a = 1 en adelante, el resultado de la función se obtiene multiplicando por 2 la fila anterior. Por ejemplo, la fila de a = 3 (8,24,40,56,72,...) se obtiene multiplicando por 2 la fila correspondiente a a = 2 (4,12,20,28,36,...). De esta forma justificamos que la codificación de pares de números distintos da lugar a códigos también distintos. En la tabla b) se representa otra forma de entender la función. En cada fila se ha recuadrado los números escogidos para codificar los pares (O, 6),(1, 6),(2,6) y (3,6). En la primera fila se observa que se escogen números alternativos para codificar los pares (O, 6) con b desde O en adelante. En la segunda fila aparecen los números no usados en la primera (los números pares) y se comprueba que vuelven a escogerse de forma alternativa los códigos que codifican los pares (1,6). La operación se repite indefinidamente, de forma que se puede asegurar que cualquier número natural corresponde a un código de un par de números. Definición 1.41 Tenemos dos funciones decodificadoras que, a partir del número x =< a, 6 > (el número x que codifica el par (a, b}) obtienen los números a y

32 CAPÍTULO 1. < a, 6 > +1 a 0 1 2 3 PRELIMINARES b 0 1 1 3 2 6 4 12 8 24 2 5 10 20 40 3 7 14 28 56 4 9 18 36 72 Figura 1.1: Función codificadora de pares de números. b. Llamamos a estas funciones, respectivamente, l(x] y r(x), y las definimos a continuación Ejemplo 1.23

33 1.8. NUMERABILIDAD 1.8. Numerabilidad Numerabilidad y computabilidad son conceptos muy relacionados. Veamos en este apartado las nociones básicas sobre numerabilidad. Definición 1.42 Se dice que un conjunto R es infinito numerable si es posible establecer una biyección entre R y los números naturales. R = { a1, a2, a3, ...} N={ 1, 2, 3, ...} Ejemplo 1.24 El conjunto IMPARES es numerable, ya que la función /(n) = 2 n + l . establece una biyección entre dicho conjunto y N. La mayoría de las veces es difícil encontrar una formulación algebraica de la biyección que numera un determinado conjunto. La siguiente definición es equivalente a la anterior, y es la que utilizaremos normalmente. Definición 1.43 Un conjunto numerable es aquel cuyos elementos pueden ser numerados: dispuestos en una lista con una primera componente, una segunda componente, etc., de forma que todos los elementos del conjunto aparezcan tarde o temprano en la lista. Ejemplo 1.25 El conjunto N de los naturales se numera con la lista ¿ = (0,1,2,3,4,...) y el conjunto IMPARES impares se puede numerar con la lista ¿ = (1,3,5,7,...)

34 CAPÍTULO 1. PRELIMINARES La definición de conjunto numerable mediante una lista es equivalente a la de conjunto numerable con una biyección. Esto es porque una lista infinita determina una función que toma el conjunto de los naturales (posiciones de los elementos en la lista) como argumentos y toma los elementos del conjunto como valores. Ejemplo 1.26 La lista £, = (1,3,5,7,...) que numera el conjunto de los naturales impares determina una función / en la que /(!) = !, /(2) = 3, /(3) = 5, /(4) = 7, Y, de forma contraria, también la función / determina la lista. Puntualicemos sobre qué cosas pueden ser listas infinitas numerables y cuáles no. 1. Los números naturales pueden ser numerados por una lista infinita de la forma vista previamente, pero la siguiente lista no es una forma aceptable de numerar N ¿ = (1,3,5,7,...,0,2,4, 6,8,...) Aquí se listan primero todos los impares positivos y después todos los pares. Esto no es admisible. En una lista aceptable, cualquier elemento debe aparecer tarde o temprano en el lugar n de la lista, para algún n finito. En la lista previa, sin embargo, ninguno de los números pares aparece de esta forma, sino que están situados, por decir algo, en la posición oo + 1, oo + 2, etc. 2. Al numerar un conjunto listando sus elementos, está permitido que alguno de estos elementos aparezca más de una vez en la lista. El requisito es que cada elemento aparezca al menos una vez. No importa si la lista es redundante; todo lo que se requiere es que sea completa. Claramente, una lista redundante se puede convertir en una no redundante. Para ello basta con examinar cada posición, comparando el elemento con la lista finita de elementos que le precede y borrar el elemento si ya aparece en esa lista finita.

35 1.8. NUMERABILIDAD 3. También es perfectamente correcto que la lista tenga huecos, ya que podríamos construir a partir de ésta otra lista que no los tuviera. Ejemplo 1.27 Una lista que numeraría correctamente los naturales es 1, , ¿, , o, — , 4, , • • • La función h definida por la lista asigna valores a los números 1,3, 5, . . ., pero no tiene ningún valor definido para 2 , 4 , 6 , . . . . La función h se dice que es una función parcial, esto es, está definida únicamente para algunos naturales. Podríamos definirla como sigue h(n) = si n es impar indefinido en otro caso Ejemplo 1.28 Un ejemplo interesante de numerabilidad es la demostración de que el conjunto N x N, que contiene todas las parejas de números naturales, es numerable. Para demostrar que N x N es numerable construimos la siguiente lista infinita numerable en donde se enumeran todos y cada uno de sus elementos: L = ((0,0), (0,1), (1,0), (O, 2), (1,1), (2,0), (O, 3), (1,2), (2,1), ( 3 , 0 ) , . . . ) . La lista L se construye de la siguiente forma. Primero se enumeran las parejas de números ( i , j ) tales que i + j = O (únicamente la pareja (0,0)), a continuación las parejas tales que i + j = l (las parejas (0,1) y (1,0)), después las parejas tales que i + j = 2 (las parejas (O, 2), (1,1) y (2,0)), y así sucesivamente. Es fácil argumentar que cualquier pareja (¿,j) estará en una posición finita de la lista, ya que los números de esta pareja sumarán una cantidad finita i + j = k, con lo que la pareja se encontrará enumerada en el grupo de parejas de números que suman k. Ya que se cumple que para cualquier m el número de parejas de números que suman m es un número finito, también lo será el conjunto de los k — 1 grupos que existen antes de llegar al grupo de la pareja (¿,j). Otra posible lista que enumera las parejas de números es L = ((/(0),r(0)),(Z(l),r(l)),(/(2),r(2)),...),

36 CAPÍTULO 1. PRELIMINARES siendo las funciones l(x) y r(x) las funciones decodificadoras de parejas de números vistas anteriormente. Por último, decir que no es necesario que el dominio de la biyección que numera un conjunto sea N, ya que cualquier otro conjunto numerable también es válido. Por ejemplo, si hemos demostrado que el conjunto de los números racionales, Q, es un conjunto numerable, podemos demostrar que algún conjunto S es numerable encontrando una función s : Q —>• 5. 1.9. Diagonalización No todos los conjuntos son numerables: algunos son demasiado grandes. Un ejemplo de estos conjunto es el conjunto de partes de A/", P(N), el conjunto de todos los posibles conjuntos de números naturales. P(N) = {0, N, PARES, IMPARES, {0, 1, 2, 3, 4}, . . .} El matemático alemán Georg Cantor demostró que P(N) no era numerable mediante un método, conocido como método de la diagonal o de diagonalización, que ha sido aplicado, posteriormente, como técnica general de demostración a otros problemas similares. Este método se puede aplicar, en general, a cualquier conjunto R no numerable, para demostrar su no numerabilidad. Consiste en una reducción al absurdo sobre la afirmación de que R es numerable: 1. Para empezar, supongamos que R es numerable. Por ello, es posible definir la lista en la que se numeran sus elementos L= ( n , r 2 , r 3 , . . . ) 2. Ahora debemos (y ésta es la parte más complicada de la diagonalización) , basándonos en la ordenación impuesta en R por esta supuesta lista, definir un elemento, al que llamaremos r*, que pertenezca al conjunto R pero que sea distinto de todos y cada uno de los elementos de la lista Esto genera una contradicción, ya que se supone que en L se numeran todos los elementos de R y hemos encontrado un elemento r* que, perteneciendo a R, no se encuentra en ninguna posición de la lista.

37 1.9. DIAGONALIZACIÓN Vamos a aplicar este método a la demostración de que P(N] no es numerable. Teorema 1.4 El conjunto P(N] no es numerable. Demostración Supongamos que el conjunto P(N] es numerable, y que existe una lista L = (5i,5 2 ,...) que lo numera. No nos importa el orden en el que los conjuntos 5¿ aparezcan en la lista, ya que la demostración que sigue a continuación es independiente de dicho orden. Supongamos, como ejemplo, que 5i = PARES, 52 = IMPARES, S3 = {3,4,5}, ... A partir de la lista L construimos un conjunto 5*, definido de la siguiente forma: para cada número natural n, n pertenece a 5* si y solo si n no pertenece a <b n . La composición de 5* depende de la composición de la lista L, por lo que diferentes listas producirán diferentes conjuntos 5*, pero esto no es relevante para la demostración. En el caso de la lista anterior, por ejemplo, el número 1 sí que pertenecería a 5*, ya que 1 ^ 5i, el número 2 también pertenecería a 5*, ya que 2 ^ 62, pero el número 3 no pertenecería a S* porque 3 E S$. Al definir de esta forma 5* hemos conseguido que sea distinto de todos y cada uno de los subconjuntos de L, ya que, como mínimo, tendrá un elemento distinto de cada uno de ellos. Para demostrar formalmente que el conjunto S* no forma parte de L realizaremos otra reducción al absurdo. Supongamos que S* pertenece a L en la posición m-ésima, por lo que 5* se puede identificar con el conjunto Sm de L. Veamos, entonces, si el natural ra pertenece a 5*. Por definición de 5*, pero es entonces cuando nos encontramos con la contradicción: como S* es el conjunto ra—ésimo (Sm), entonces, o sea, dicho número debe pertenecer y no pertenecer a la vez a S*. Esto es una contradicción, por lo que la suposición de la que hemos partido debe ser falsa, esto es, 5* no puede pertenecer a L. Pero sin embargo 5* es un conjunto bien definido de números naturales, por lo que pertenece a -P(AT), con lo que la suposición inicial de que L lista todos los elementos de P(N) es falsa.

38 CAPÍTULO 1.PRELIMINARES 1.10. Problemas 1. Determinar si las siguientes expresiones son verdaderas falsas: 2. Calcular las siguientes expresiones: 3. Contestar las siguientes preguntas: a) Existe algún conjunto A tal que | P(A) |= 48? b) Si A = {a}. Quién es P(P(A))7 4. Demostrar, utilizando el método de inducción, que para todo número natural n > 1 se verifica que: 5. Un palíndromo puede definirse como una cadena que se lee igual hacia delante y hacia atrás, o si y sólo si cumple las siguientes propiedades: Pl: A es palíndroma. P2: Si a| = 1 entonces a es palíndromo. P3: Si a es cualquier símbolo y a es palíndroma, entonces aaa es palíndroma. Demostrar por inducción que las dos definiciones son equivalentes. 6. Demostrar que el conjunto Z de todos los enteros: . . . — 2, —1, O, 1, 2 , . . . , es numerable. Hacerlo de las dos formas siguientes:

1.10. PROBLEMAS 39 a) Encontrando una disposición de todos los números de Z en una lista aceptable. 6) Definiendo una función, expresada de forma matemática, de Z+ = N - {0} en Z. 7. Demostrar que el conjunto de los números racionales positivos Q+ es numerable. Hacerlo de las dos formas vistas en el ejercicio anterior. 8. Demostrar que el conjunto de todos los números racionales (positivos, negativos y cero) es numerable. Probarlo, igualmente, de las dos formas vistas en el ejercicio anterior. (Para el apartado (b), utilizar el conjunto Z, que ya se ha demostrado que es numerable). 9. Demostrar que el conjunto de todas las cadenas finitas formadas con los símbolos + y — es numerable describiendo una lista que las enumere. 10. Demostrar que el conjunto de todos los conjuntos finitos de números naturales es numerable, describiendo una forma en la que las cadenas finitas de + y — puedan codificar esos conjuntos. 11. Demostrar que los siguientes conjuntos son numerables: (sobre un alfabeto infinito numerable A — {ai, a<2,03,04, • • •} ). a) L2: Conjunto de las palabras de dos letras. 6) L3: Conjunto de las palabras de tres letras. c] Ln: Conjunto de las palabras de n letras, para un n fijo arbitrario. d) L*: Conjunto de todas las palabras de cualquier longitud finita (L* = ^UL^Í^U---). 12. Demostrar que la unión numerable de infinitos conjuntos numerables es numerable. 13. Para las siguientes listas (infinitas) de conjuntos, hallar 5* = {n | n <£ Sn}: a] 5i = {1,2}, 52 = {2,3}, S3 = {3,4}, 54 = {4,5}, 55 = {5,6},... b] Si = {2}, S2 = {3}, 53 = {4}, 54 - {5}, S5 = {6},... c) Si = {2}, S2 = {3}, S3 = {3,4}, 54 = {4, 5}, 55 = {5, 6},... d) Si = 0, 52 = {2}, S3 = 0, 54 = {4}, S5 = 0, 56 = {6}, . . .

40 CAPÍTULO 1.PRELIMINARES 14. Dada una lista L de conjuntos: Si, 6*2, 63,... , definíamos el conjunto 5* de la forma siguiente: a) Construir una lista con todos los conjuntos finitos de números naturales, incluyendo el conjunto 0. b) Para esta lista, ¿Qué conjunto es el que define 5*? c] ¿Pertenece S* a L?. d] ¿Qué conjunto es el definido por 5* = {n n 6 5n}? 15. Utilizando el argumento de la diagonal, demostrar que el producto cartesiano infinito de conjuntos infinitos numerables no es numerable. 16. Utilizando el argumento de la diagonal, demostrar que el conjunto de números reales en el intervalo (0,1) no es numerable. 17. Demostrar, utilizando el argumento de la diagonal, que el conjunto de todas las funciones totales con dominio y rango en los naturales no es numerable. 18. Demostrar que el conjunto de todas las aplicaciones (funciones totales) de N en {0,1} no es numerable.

Capítulo 2 Máquinas de Turing 2.1. Introducción En 1900 el matemático inglés David Hilbert presentó en el Congreso Internacional de Matemáticas de París el problema de la decisión; planteaba si podría existir un algoritmo para determinar si una fórmula lógica podía o no satisfacerse, o declararse verdadera. La solución de este problema llevó a la comunidad matemática directamente al problema fundamental de la Teoría de la Computabilidad: ¿qué se entiende por algoritmo?. Hasta entonces, el concepto de algoritmo se había dado por descontado, nadie se había preocupado de darle una definición formal. En respuesta a este problema, el matemático inglés Alan M. Turing propone en 1936 una formalización del concepto general de computación (algoritmo), mediante una máquina consistente en una cinta de longitud ilimitada dividida en celdas, y un dispositivo de lectura con un número finito de estados, en lo que se ha denominado Máquina de Turing(MT). A lo largo del capítulo se revisará este modelo. Actualmente la MT se acepta como una correcta formalización del concepto de algoritmo. No se puede demostrar que el concepto de MT es equivalente al concepto intuitivo de algoritmo pero existen muchos argumentos de peso que nos permiten realizar dicha afirmación (Tesis de Church-Turing). Entre ellos, el más importante es que la MT ha resultado tener la misma capacidad computacional (puede reconocer los mismos lenguajes o computar las mismas funciones) que cualquier otro modelo formal de algoritmo (lambda-cálculo, sistema de reescritura de Post, funciones recursivas, etc.). En este texto veremos otros dos modelos computacionales, las funciones recursivas (capítulo 4) y el lenguaje L (capítulo 3). En el capítulo 5 demostraremos que todos estos modelos son equivalentes. Aquí estudiaremos principalmente el modelo de MT desde el punto de vista de definición de lenguajes de cadenas y al final del capítulo veremos, brevemente, cómo es posible utilizar la MT para computar funciones.

42 2.2. CAPÍTULO 2. MÁQUINAS DE TURING El problema de definir un lenguaje Veíamos en el capítulo de preliminares la definición del concepto de lenguaje de cadenas y la posibilidad de que dichos lenguajes sean infinitos. Presentábamos los siguientes ejemplos de lenguajes infinitos sobre el alfabeto £ = {0,1}. LI = {0,01,011,0111,...} L2 = {01,0011,000111,...} L3 = {10,11,101,111,1011,...} donde LI es el conjunto de todas las cadenas que comienzan por O y tienen a continuación O o más unos, 1/2 es el conjunto de las cadenas de forma O n l n y, Z/s es el conjunto de los códigos binarios de números primos. Comencemos por una cuestión léxica. La expresión definir un lenguaje, que estamos usando en este apartado, no es muy común en la informática teórica. En su lugar se utiliza la expresión reconocer un lenguaje, debido a que los formalismos usados son normalmente autómatas que terminan en un estado de aceptación cuando la cadena que están reconociendo pertenece al lenguaje (veremos que la MT funciona igual). Nosotros utilizaremos ambas expresiones de forma intercambiable. ¿Cómo definir formalmente estos lenguajes (y cualquier otro que se nos pueda ocurrir)? ¿Tienen todos los métodos formales de definición de lenguajes la misma potencia, o algunos métodos pueden definir lenguajes imposibles de definir con otros? ¿Es posible definir todos los lenguajes existentes sobre un alfabeto, o existen lenguajes que no pueden ser definidos por ningún método formal? Las dos primeras preguntas se contestan desde el campo denominado Teoría de Lenguajes y Autómatas, y, aunque no es materia de este libro, veremos en este apartado una pequeña colección de conceptos relacionados con el asunto. La contestación de la tercera pregunta es materia de la Teoría de la Computabilidad, y sobre ella en concreto trata la última parte del libro. 2.2.1. Expresiones regulares Veamos como ejemplo de método formal de definición de lenguajes infinitos la notación de expresiones regulares, una de las notaciones más sencillas. Comencemos denotando por 1) a al lenguaje formado por el símbolo a ({a}), 2) a + b al lenguaje {a} U {&}, 3) ab al lenguaje {a&}, 4) a* al lenguaje {a}* ({A, o, aa, aaa,...}) y 5) a+ al lenguaje {a}+ ({a, aa, aaa,...}). Definimos el orden de precedencia como: * primero, la concatenación el siguiente y + el último. Definición 2.1 Una expresión regular sobre un alfabeto S se define de forma recursiva con las siguientes reglas:

2.3. EL MODELO CONCEPTUAL DE MÁQUINA DE TURING 1. 43 0 y A son expresiones regulares. 2. a es una expresión regular para todo a E S. 3. Si r y s son expresiones regulares, entonces r + s, rs y r* también lo son. Ejemplo 2.1 Por ejemplo, utilizando la notación de expresiones regulares, ya es posible definir formalmente el conjunto L = {0,01,011,0111,...} como 01*. Otros ejemplos de lenguajes definidos por expresiones regulares son los siguientes 0+ + 1+ = {0,1,00,11,000,111,...} (01)* = {A, 01,0101,010101,...} 0*1* = {A, 0,1,00, 01,11,000,001,...} ¿Qué potencia computacional tiene la notación de las expresiones regulares? Salta a la vista que poca, ya que existen lenguajes bastante sencillos de ser definidos informalmente, pero que no se pueden formalizar con esa notación. Un ejemplo sería el lenguaje L>¿ = O n l n de cadenas que tienen igual número de Os al comienzo que de Is al final. Se demuestra, aunque queda fuera del alcance del texto, que la MT sí que puede definir ese lenguaje en concreto y, en general, cualquier otro lenguaje definible por cualquier otro formalismo propuesto hasta el momento. Es por ello que la tesis de Church-Turing sostiene que la MT modela formalmente el concepto intuitivo de algoritmo. 2.3. El modelo conceptual de Máquina de Turing Un modelo formal que caracterice el concepto de algoritmo debe cumplir, básicamente, dos propiedades: ha de tener una descripción finita, y debe estar formado por operaciones discretas, cada una de las cuales pueda ser ejecutada mecánicamente . Ya que la MT es capaz de reconocer cualquier lenguaje reconocible por un algoritmo, debe cumplir estas propiedades genéricas.

CAPÍTULO 2. MÁQUINAS DE TURING 44 2.3.1. Funcionamiento de una MT A continuación se expone una variante del modelo teórico propuesto por Turing. Este modelo estará formado por una cinta de entrada y de trabajo dividida en celdas, una cabeza de lectura/escritura, y una unidad de control finita (unidad de ejecución). La cinta es infinita por ambos extremos, conteniendo un número infinito numerable de celdas. Cada celda contiene un único símbolo1 perteneciente a un alfabeto, denominado alfabeto de la cinta. Por defecto, todas las cintas contienen un símbolo especial (B), denominado carácter blanco, que marca las celdas que no contienen símbolos de la cadena de entrada. Los datos de entrada (símbolos distintos de B) ocupan n celdas, siendo siempre n > O finito. El cabezal de lectura/escritura se posiciona en la primera cinta distinta de B, y recorre la cinta, pasando por las celdas de una en una y accediendo al contenido de las mismas. Dependiendo del estado actual y del símbolo leído por el cabezal, la MT: 1. Cambia de estado. 2. Imprime un símbolo sobre la celda leída, que reemplaza al que se había leído. 3. Desplaza el cabezal de lectura/escritura a la derecha o a la izquierda de la posición actual. Figura 2.1: Estructura básica de una MT. Esta secuencia de acciones componen lo que se denomina paso de ejecución o movimiento. La MT continúa realizando pasos de ejecución hasta que lee un símbolo para el que no hay definida ninguna acción. Puede darse el caso de que la MT no se detenga nunca, entrando en una especie de "bucle infinito". 1 Se hablará indistintamente de símbolo o carácter para referirse a los elementos de un alfabeto.

2.3. EL MODELO CONCEPTUAL DE MÁQUINA DE TURING 2.3.2. 45 Representación de una MT Existen diversas formas de representar una MT. Como ejemplo vamos a utilizar una MT diseñada para reconocer el lenguaje L = {On | n es impar}. Este lenguaje no es complicado, de hecho podría reconocerse con una expresión regular (0(00)*), pero puede valer como primer ejemplo. • Representación de una MT mediante una tabla que define la función de transición. Estado 4o qi 0 (9i,0,£>) B too, o,0) (<? 2 ,£,£>) La tabla tiene las columnas encabezadas por el símbolo leído por el cabezal, y las filas por el estado en que se encuentra la máquina. Las componentes de la tabla representan la operación a realizar: estado al que pasa la máquina, símbolo a escribir y movimiento del cabezal (I=izquierda y D—derecha). Por ejemplo, si la máquina se encuentra en el estado qi leyendo un O, pasará al estado ¿70, escribirá un O y moverá el cabezal a la derecha. El estado q<¿ es un estado final, o de aceptación. Representación de una MT mediante un autómata. En este caso, los círculos representan estados en los que se encuentra la máquina, y las flechas cambios de estado cuando se lee un símbolo. Etiquetando las flechas se encuentran el símbolo leído, el símbolo escrito y el movimiento del cabezal. Representación mediante un conjunto de tupias. (9o,0,0,D,gi) (gi,0,0,J[>,9o) (qi,B,B,D,q2) Donde cada tupia está formada por: estado actual, símbolo leído, símbolo escrito, desplazamiento en la cinta y estado siguiente. Veamos cómo la máquina acepta la cadena 000: 1. Inicialmente, el cabezal está posicionado en el primer O, y el estado inicial es <?o. Tras consultarse la función de transición, se comprueba que, estando en <7o leyendo un O, la máquina debe pasar al estado <?i, escribir un O y mover el cabezal a la derecha.

46 CAPÍTULO 2. MÁQUINAS DE TURING 2. Ahora la máquina se encuentra leyendo el segundo O de la cadena y en el estado q. La función de transición hace que pase al estado <?o, escriba un O y mueva el cabezal a la derecha. 3. La máquina lee el último O encontrándose en el estado QQ. Para el estado qo y el símbolo leído O hemos visto que la máquina pasa al estado gi, escribe un O y mueve el cabezal a la derecha. 4. Ahora la máquina está en q leyendo un blanco. En esa situación la máquina pasa a <?2 que es un estado final o de aceptación, para el que no hay definida ninguna acción. 2.3.3. Definición formal de una MT Veamos más formalmente la definición de una MT. Definición 2.2 Una MT se define como una tupia donde Q es el conjunto finito de estados de la unidad de control, F es el conjunto finito de todos los símbolos permitidos sobre la cinta, B es el símbolo que representa la celda vacía, B € F. E es un subconjunto de F que no incluye el símbolo B, denominado alfabeto de entrada. S es la función próximo estado o función de transición, que no tiene porque ser total y que se define qo es el estado inicial de la MT, q$ £ Q F es el conjunto de estados finales, F C Q. Definición 2.3 Denominamos descripción instantánea (DI) de una MT M a una cadena

Add a comment

Related presentations

Related pages

Introducción a la teoría de la computabilidad - Buchhandel ...

D. Gallardo López , P Arques Corrales, I. Lesta Pelayo - Introducción a la teoría de la computabilidad - 2 - Buchhandel.de - Bücher lokal kaufen
Read more

Introducción a la teoría de la computabilidad: Amazon.de ...

Pilar Arqués - Introducción a la teoría de la computabilidad jetzt kaufen. ISBN: 9788479087630, Fremdsprachige Bücher - Computer & Internet
Read more

Introducción a la teoría de la computabilidad ebook ...

eBook Shop: Introducción a la teoría de la computabilidad als Download. Jetzt eBook herunterladen & bequem mit Ihrem Tablet oder eBook Reader lesen.
Read more

Hans Hermes - Introducci n a La Teor a de La ...

Teoría de la computación. Browse Browse. Interests. Biography & Memoir; Business & Leadership; Fiction & Literature; Politics & Economy; Health ...
Read more

Introduccion a la teoria de la computabilidad ...

Introduccion a la teoria de la computabilidad / Introduction to the theory of computability (Spanish Edition): 9788479087630: Computer Science Books ...
Read more

Tema 5: Introducción a la Teoría de la Computabilidad ...

Tema 5: Introducción a la Teoría de la Computabilidad Componentes físicos Componentes lógicosMáquinas de Turing ... la derecha, formada únicamente ...
Read more

Introducción a la teoría de la computabilidad by D ...

... presenta los conceptos fundamentales de la teoría de la computabilidad. Abarca los temas de computabilidad, máquinas de Turing, funciones ...
Read more

Introduccion a la teoria de la computacion: via palindromos

Introduccion a la teoria de la computacion: via palindromos J. Andres Montoya ... remos la computabilidad, y la computabilidad en tiempo real, del problema Pal
Read more

Introducción a la teoría de la computabilidad: Amazon.de ...

D.; Arques Corrales, P.; Lesta Pelayo, I. Gallardo López - Introducción a la teoría de la computabilidad jetzt kaufen. Kundrezensionen und 0.0 Sterne. …
Read more