Introducción

La computadora hoy en día #

Sin lugar a dudas la computación se ha convertido en un campo que ha impactado el desarrollo de nuestra sociedad, hoy en día encontramos computadoras en varios aspectos de la cotidianidad de nuestro actividades diarias. De hecho algunas de ellas pasan desapercibidas, las más fáciles de identificar son las tipo escritorio, o tipo laptop o recientemente en nuestros dispositivos móviles e “inteligentes”. Sin embargo si ponemos atención también encontramos computadoras en: tarjetas bancarias, en los coches y hasta en las lavadoras. Sus capacidades no nos dejan de sorprender, no sólo nos apoyan en nuestras tareas diarias a través de editores de texto, hojas de cálculo, editores de imágenes y en redes sociales sino que también son una fuente principal de entretenimiento, son base de la economía con sistemas que facilitan el comercio electrónico y el manejo de la banca, y nos ayudan a encontrar nuevas fronteras literalmente del universo o de las matemáticas a través de la exploración numérica. No solo eso, sino que hoy en día las computadoras están comenzando a romper barreras en tareas antes pensadas exclusivas del humano: los mejores jugadores de ajedrez son computadoras, el mejor jugador de Go también fue una computadora. Además ahora podemos conversar con las computadoras, estas comienzan a entendernos cuando les hablamos, crean imágenes y hay un esfuerzo gigantesco para que comiencen a manejar coches de forma autónoma.

Ante todo este avance, es importante preguntarse sobre la naturaleza de la computadora/computación:

  1. ¿Qué es una computadora?
  2. ¿Cuales son las propiedades esenciales de una computadora?
  3. ¿Cómo serán las computadoras en 10 años, en 100 años o 1,000 años?
  4. ¿Qué problemas estarán resolviendo las computadoras en 100 años o 1,000 años?
  5. ¿Qué problemas no podrán resolver aún en 1,000 o 10,000 años?

¿Por qué de lenguajes formales? #

Hay varias formas de tratar de responder a las preguntas anteriores, uno podría concentrarse en el aspecto tecnológico como lo son hoy en día los circuitos electrónicos y tratar analizar de ahí que elementos son básicos y qué hacen a una computadora. A partir de ahí uno podría extrapolar como serán las computadoras electrónicas, a lo mejor siguiendo leyes como la de Moore. Por otro lado, también podríamos estudiar nuevas tendencias como la computación cuántica que trata de cambiar el paradigma de la computación y podríamos predecir como lucirá una computación basada en esta nueva tecnología.

También uno podría fijarse en los algoritmos y su complejidad; uno podría concentrarse en tratar de identificar nuevos algoritmos que resuelvan problemas hasta ahora difíciles y de forma eficiente, de ahí uno podría extrapolar nuevos algoritmos para las computadoras del futuro, y a lo mejor familias de estos.

Este material ofrece otra perspectiva para responder a estas preguntas y en particular a la número dos. Para poder, responderla asumiremos un marco matemático-computacional. Partiremos de conceptos de la teoría de conjuntos para explorar los alcances y propiedades de máquinas que computan, e iremos escalando los elementos de estas máquinas para llegar a un modelo teórico de la computadora. Este mismo modelo nos abrirá las puertas para encontrar los límites de la computación.

Para lograr alcanzar a vislumbrar las respuestas a dichas preguntas iremos ahondando en conceptos como:

  1. Conjuntos
  2. Alfabetos
  3. Cadenas
  4. Lenguajes
  5. Máquinas
  6. Gramáticas
  7. Decidibilidad
  8. Paradojas

El origen de la idea de la computación #

La humanidad ha buscado tomar ventaja de su ambiente y no solo adaptarse a él, sino adaptar el ambiente en beneficio de la sociedad. A través del tiempo encontramos ejemplos de uso de herramientas y su aplicación para mejorar la situación de vida desde una persona, hasta pueblos y civilizaciones. En esta búsqueda han surgido máquinas que ayudan con tareas específicas. Fue durante el periodo que denominamos como revolución industrial que vemos un nivel nunca antes visto en el diseño y uso de diferentes materiales, máquinas y procesos. En particular se creó maquinaria para crear objetos de forma masiva. Esto implico un cambio socio-económico, donde por ejemplo uno de los fenómenos observados fue que la población se desplazó de estar dispersa en un ambiente rural a concentrarse en focos urbanos.

La introducción de la nueva maquinaria implicó el incremento del conocimiento necesario para los procesos de producción de la misma maquinaria. En particular se requirió avanzar en múltiples frentes como la química, la metalurgia, el diseño de materiales, etc. De forma interesante este avance recayó en el poder del cálculo numérico, esto se debió a que se requería de una flexibilidad para calcular valores específicos a un problema particular. Como es imposible predecir qué calculo se necesitaría para un problema particular se asumió una estrategia de precalcular muchos valores todo hasta cierta precisión, un ejemplo de esto son las tablas logarítmicas,esto permitiría después hacer el cálculo requerido tomando como base los cálculos hechos con anterioridad. Estos cálculos masivos fueron hechos por humanos, y los resultados incluían algunos errores.

En este contexto que surge la idea de qué si ya se automatizaban procesos que antes hacían humanos, por ejemplo la elaboración de textiles, porque ahora no se automatizaba el proceso de hacer cálculos. Es Charles Babbage el primero en proponer una primer máquina calculadora a este nivel: la máquina diferencial, mientras construía comenzó a idear otra: la máquina analítica, que asemeja a nuestras computadoras actuales pero que sin embargo no alcanzó a concluir. Ada Lovelace al conocer el diseño de esta máquina se convierte en la primera programadora de la historia de la humanidad, al programar una fórmula para números de Bernulli que nunca pudo ejecutar (ya que no existía la computadora). Sin embargo el marco teórico en el que funcionaría dicho calculo, hace posible ver que su propuesta fue correcta y así ella ideo el primer programa en toda la historia de la humanidad.

Esta no sería la última vez en que se dé un avance fundamental en la computación de forma teórica aun cuando no se tenga la máquina en su forma física. Alan Turing antes de comenzar a diseñar elementos físicos de computadoras, identificó uno de los límites más duros de la matemáticas y de paso creó el campo de la computación. Todo esto cuando todavía no existía una computadora, pero ya sabíamos sus límites.

El rol de las paradojas #

En el corazón de estos límites están conceptualizaciones que producen contradicciones y que en esencia son paradójicas. Por ejemplo la siguiente frase

¿Qué nos está tratando de decir esta frase? Si la frase es verdadera, la misma frase nos está diciendo que es falsa; si la frase es falsa, significa que lo dice no es verdad sino lo contrario, osea que la frase es verdadera, pero partimos que no lo era. Existe un elemento paradójico.

Otro ejemplo de paradoja, es la paradoja del barbero que va más o menos así:

Imaginen un pueblo donde todos los habitantes hombres están rasurados, todos. Entonces, podemos dividir a los habitantes del pueblo en dos grupos, aquellos que se rasuran a si mismo y aquellos que los rasura el barbero del pueblo ¿en qué grupo debe ir el barbero del pueblo? 🤯

Dude dónde está mi paradoja #

La siguiente es una lista de sentencias que establece el valor de verdad para cada sentencia en relación con la celda denominada realidad:

No. Sentencia sobre hecho Realidad Valor de verdad
0 El círculo es amarillo Verdadero
1 El círculo es amarillo Falso
2 No hay nada en la siguiente celda Verdadero
3 No hay nada en la siguiente celda I Falso

Por supuesto la “realidad” no se limita a una celda, y la podemos extender a la página o al mundo completo:

No. Sentencia sobre hecho Valor de verdad
4 Esta página tiene varias palabras Verdadero
5 La página está en blanco Falso
6 Las mascotas son fabulosas Verdadero
7 Los gatos tienen alas Falso

Un caso interesante es cuando la sentencia habla de si misma:

8 Esta sentencia contiene la palabra verde Verdadero
9 Esta sentencia contiene tiene la letra z Verdadero
10 Esta sentencia contiene tiene dos letras z Falso
11 Esta es una sentencia
¿?
Verdadero
12 Esto es una novela larga
¿?
Falso
13 Esto es un color
¿?
Falso
14 Esta sentencia es verdadera
¿?
Verdadera
15 Esta sentencia es falsa
¿?
🤔…🤯

¿Por qué es difícil esta última, la número 15?

Reflexión

Existen dos casos:

  • Si la sentencia es verdadera, nos dice que es falsa
  • Si la sentencia es falsa, entonces lo que dice no es cierto y en realidad nos diría que es verdadera

Es decir, es una paradoja

Enlaces para explorar #

Lecturas recomendadas #

  • Greibach, S. A. (1979, October). Formal languages: Origins and directions. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) (pp. 66-90). IEEE Computer Society. [ BiDi/UNAM], [ Liga]
  • O’Regan, G. (2012). A brief history of computing (Second edition). Springer. [ BiDi/UNAM], [ Liga]
  • Haigh, T., & Ceruzzi, P. E. (2021). A new history of modern computing. MIT Press. [ BiDi/UNAM], [ Liga]
  • Coello, C. A. C. (2004). Breve historia de la computación y sus pioneros. México: Fondo de cultura económica. [ Liga]
comments powered by Disqus