Introducción

La computadora hoy en día #

Sin lugar a dudas la computación se ha convertido en un campo que ha impactado al desarrollo de nuestra sociedad. Hoy en día encontramos computadoras en muchos aspectos cotidianos, usualmente las identificamos cuando estamos frente a una tipo escritorio, o tipo laptop o recientemente también en tipo dispositivo móvil. 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, 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, también 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, las computadoras comienzan a entendernos cuando les hablamos y hay 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:

  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 aun 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 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 tratar de predecir como lucirá la computación basada en esas nuevas computadoras.

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.

Sin embargo, 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 a la situación del humano. 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 potencial del uso de diferentes maquinarias. 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, sin embargo se requería de una flexibilidad para calcular valores específicos a un problema particular. Como es imposible predecir qué calculo se necesitaría 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.

Es 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 dicha computadora, y todas las demás, hace posible ver que su propuesta de programa fue correcta y 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 no existía una computadora.

Paradojas #

En el corazón de estos límites están conceptualizaciones que producen contradicciones y 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:

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? 🤯

Enlaces para explorar #

comments powered by Disqus