Cada nodo del grafo es un capítulo del libro y las flechas (aristas) representan la prioridad de lectura. Por ejemplo, para leer el capítulo 4 podría leer los capítulos 1 y 2 o 1 y 3. O si usted prefiere, puede leer los capítulos 1, 2 y 3. Nada lo imposibilita. Asimismo, se añade a la derecha el enfoque de cada parte del libro.
Notas
De principio a fin de este libro, aparecen contenidos en un cuadro como este. Se trata de información extra, aclaraciones y comentarios que son relevantes como complemento a lo que se está tratando en dicho apartado. Por lo cual, le rogamos no omitirlo.
Ejercicios
Al final de cada capítulo de las partes II y III se encontrará con una sección de ejercicios. Cada uno de ellos tiene asociado el signo «*» que representa la dificultad del problema:
• (*) Fácil
• (**) Intermedio
• (***) Difícil
Cualquier otro signo indica que el autor de este libro le está proponiendo un desafío intelectual o, quizá, una broma.
Material
Toda la información está disponible en:
Ahí se encuentra el enlace al repositorio de GitHub que contiene lo siguiente:
• Cada código utilizado en la parte III.
• Cada figura en una mayor resolución y a color.
• Enlace para instalar Racket, Python y Haskell. (Usamos las últimas versiones de cada uno.)
• Enlace al intérprete web. Para este libro se ha creado un entorno que permite evaluar expresiones del cálculo lambda, por ello, usted podrá ejecutar cada ejemplo de la parte II y saber y verificar si ha podido resolver exitosamente cada ejercicio. Será su asistente en el aprendizaje.
PARTE I
INTRODUCCIÓN A LA COMPUTACIÓN Y LA PROGRAMACIÓN
La computación es esencial en nuestra vida. Y la programación la hace posible. Ambas se combinan a través de los lenguajes de programación, que son piezas vitales para entender su rol, contexto y relevancia.
Capítulo 1
¿QUÉ ES LA COMPUTACIÓN?
Si alguien me preguntara qué consejo le daría a un joven [...] Creo que una de las cosas que le diría es que no porque algo esté de moda significa que sea bueno. Probablemente iría más allá: si encuentro demasiada gente adoptando una cierta idea, probablemente pensaría que está mal o, ya sabes, si mi trabajo se hubiera vuelto demasiado popular, probablemente pensaría que tengo que cambiar.
Donald Knuth
Esta pregunta puede parecer simple en su formulación, pero nos puede llevar a confines que van desde aspectos técnicos hasta filosóficos. A su vez, la misma se ha vuelto relevante con el paso de los años y tuvo su mayor auge a comienzo del siglo XX, en particular, hacia la década de los treinta, cuando un grupo de científicos, matemáticos y lógicos buscaban comprender qué era la computación como tal, ya sea desde un punto de vista teórico o práctico.
Así como también sus posibilidades y limitaciones para tratar con diversos problemas. De esta manera, y producto de sus esfuerzos, fue como nació el concepto de «modelos de computación». Este concepto apareció antes de la existencia del primer ordenador digital (de nombre ENIAC, construido durante la segunda guerra mundial [1943]).
Pero ¿qué es un modelo de computación? Esta pregunta usa dos palabras relevantes: «modelo» y «computación». Primero, un «modelo» es una representación del funcionamiento de algo en particular (ya sea abstracto o concreto) que puede ser reproducible. Por otra parte, «computación» refiere a la capacidad de hacer tareas repetitivas que se puedan automatizar sin la intervención humana, de lo cual se desprenden dos cuestiones: (1) la acción de hacer estas tareas se llama computar y (2) si es posible realizar dichas tareas, entonces se suele decir que son computables.
Así, un «modelo de computación» es una representación abstracta que representa qué tareas son computables o no a través de computar operaciones. Dado que estos modelos son abstractos, podemos decir que un modelo de computación es equivalente a un modelo matemático. Con la salvedad de que el primero se enfoca en el contexto de la computación y hace uso de sus ventajas y desventajas.
Por ello la computación es en sí —al menos en su origen— es un área de las matemáticas. Por lo tanto, la computación es un conjunto de modelos de computación.
Sin embargo, la computación misma ha sufrido cambios en las últimas décadas, y decir que solo se trata de un conjunto de modelos de computación parece caer en un reduccionismo teórico. Más bien, tomaremos partido por ampliar esta definición a la siguiente: la computación es un conjunto de modelos de computación que se pueden expresar a través de artefactos abstractos (software) y concretos (hardware), mediante el uso de una metodología científica o ingenieril, teórica o práctica.
Objetivos de este capítulo:
• Conocer los principales modelos de computación.
• Conocer qué es la tesis de Church-Turing y cuáles son sus implicaciones en la computación.
• Comprender qué es la filosofía de la ciencia de la computación y cómo nos puede ayudar a ser mejores conocedores de nuestra propia área.
Nota:
Aún hoy, existe un debate sobre la naturaleza de la computación. ¿Es una ciencia? ¿Una ingeniería? ¿O algo totalmente nuevo? Son preguntas difíciles de responder que han suscitado libros, artículos y amplios debates en las últimas décadas. Pero tomaremos una postura. Creemos, como dicen Peter J. Denning y Peter A. Freeman en su interesante artículo «Computing’s Paradigm» («Paradigma de la computación») de 2009, que la computación es un «nuevo paradigma» que combina cuestiones de diversas disciplinas del saber: ciencias, ingeniería y matemáticas. Además, ellos dicen que la computación no trata sobre ordenadores, sino más bien sobre el procesamiento de la información, y los ordenadores son máquinas que implementan esos procesos.
Y no faltan motivos para creerlo, ya que la computación puede ser una herramienta muy útil para una innumerable cantidad de áreas, desde humanidades hasta ciencias, aparte de estudiarse a sí misma (procesos computacionales y sus límites