Capítulo 1

Modelos computacionales

Los albores de la informática moderna, en los años inmediatamente posteriores a la Segunda Guerra Mundial, se caracterizaron no sólo por el ingenio práctico en la construcción de las primeras máquinas calculadoras, sino también por el establecimiento de sólidos fundamentos teóricos que guiarían el desarrollo de la disciplina en las próximas décadas. En este capítulo, exploraremos algunos de los modelos computacionales más influyentes que han sentado las bases para comprender y construir sistemas informáticos.

1.1 La máquina de Turing:
Definición de los límites de la computación

En 1936, mucho antes de la construcción de las primeras computadoras electrónicas, el matemático británico Alan Turing publicó un artículo fundamental titulado "Sobre los números computables, con una aplicación al Entscheidungsproblem". En este trabajo, Turing propuso un modelo abstracto de computadora, ahora universalmente conocido como Máquina de Turing . No se trataba de una máquina física en el sentido tradicional, sino más bien de una construcción teórica, un experimento mental diseñado para responder a una pregunta fundamental y profundamente filosófica: ¿Qué problemas pueden resolverse mediante un proceso algorítmico, es decir, mediante una secuencia finita de instrucciones inequívocas?

Una máquina de Turing está compuesta conceptualmente por:

Una cinta infinita: Imagine una cinta ilimitada en ambas direcciones, dividida en celdas contiguas.

Cada celda puede contener un solo símbolo de un alfabeto finito, que incluye al menos un símbolo especial para indicar una celda vacía (a menudo denominada 'B' o '□').

Un cabezal: Un mecanismo capaz de posicionarse sobre una celda específica de la cinta. Este cabezal tiene la capacidad de leer el símbolo presente en la celda actual, escribir un nuevo símbolo en la misma celda y moverse una posición hacia la derecha o hacia la izquierda a lo largo de la cinta.
Un conjunto finito de estados: La máquina está en un estado específico en todo momento. Este conjunto de estados es finito e incluye un estado inicial (a partir del cual comienza el cálculo) y uno o más estados finales (o de aceptación), que indican el final de un cálculo exitoso.
Una función de transición: El corazón de la máquina de Turing es su función de transición. Esta función, que puede representarse como una tabla o un conjunto de reglas, determina el comportamiento de la máquina en cada paso. Según el estado actual de la máquina y el símbolo leído por el cabezal, la función de transición especifica de forma única tres acciones: El símbolo para escribir en la celda actual (que podría ser el mismo símbolo leído). La dirección en la que debe moverse la cabeza (izquierda, derecha o, en algunas definiciones, permanecer quieto). El nuevo estado al que debe entrar la máquina.
El símbolo a escribir en la celda actual (que podría ser el mismo símbolo leído).
La dirección en la que debe moverse la cabeza (izquierda, derecha o, en algunas definiciones, permanecer quieto).
El nuevo estado al que debe entrar la máquina.

La importancia conceptual de la Máquina de Turing es extraordinaria. Proporcionó una formalización precisa y rigurosa del concepto intuitivo de algoritmo. La idea clave es que cualquier proceso computacional que pueda describirse mediante un conjunto finito de reglas inequívocas puede simularse mediante una máquina de Turing.

Esta noción está formalizada en la Tesis de Church-Turing , un principio fundamental (no demostrable matemáticamente pero ampliamente aceptado) que establece que cualquier función computable por un ser humano siguiendo un conjunto de reglas mecánicas puede ser calculada por una máquina de Turing.

La máquina de Turing no sólo proporcionó una definición práctica de computabilidad, sino que también hizo posible explorar los límites intrínsecos de la computación. Por ejemplo, el propio Turing utilizó su modelo para demostrar la existencia de problemas indecidibles , es decir, problemas para los que no existe ningún algoritmo (y por tanto no existe una Máquina de Turing) capaz de proporcionar una respuesta definitiva (sí o no) para todos los casos posibles. Un ejemplo emblemático es el Problema de detención : dado un programa (o una Máquina de Turing) y su entrada, ¿es posible determinar si el programa finalizará su ejecución o continuará ejecutándose infinitamente? Turing demostró que no existe un algoritmo general para resolver este problema.

1.2 El modelo de Von Neumann:
La arquitectura de las computadoras modernas

Si bien la máquina de Turing representó un modelo teórico de computación, la arquitectura propuesta por John von Neumann, en colaboración con otros pioneros como John Presper Eckert y John William Mauchly, proporcionó el modelo conceptual en el que se basan la gran mayoría de las computadoras modernas. Esta arquitectura, descrita por primera vez en un influyente informe de 1945 titulado "Primer borrador de un informe sobre el EDVAC", introduce algunos principios fundamentales que aún definen la estructura de nuestras computadoras en la actualidad:

Unidad central de procesamiento (CPU): El "cerebro" de la computadora, responsable de ejecutar las instrucciones. La CPU se divide a su vez en: Unidad de control (CU): Recupera instrucciones de la memoria, las decodifica y genera las señales de control necesarias para coordinar los demás componentes del sistema. Unidad aritmético-lógica (ALU): Realiza operaciones aritméticas (suma, resta, multiplicación, división) y lógicas (Y, O, NO) sobre datos.
Unidad de Control (CU): Recupera instrucciones de la memoria, las decodifica y genera las señales de control necesarias para coordinar los demás componentes del sistema.
Unidad aritmético-lógica (ALU): Realiza operaciones aritméticas (suma, resta, multiplicación, división) y lógicas (Y, O, NO) sobre datos.
Memoria: Se utiliza para almacenar tanto los datos a procesar como las instrucciones del programa. Esta memoria está organizada conceptualmente como una secuencia de ubicaciones, cada una identificada por una dirección única. La memoria permite el acceso directo a cualquier ubicación en un tiempo relativamente constante (memoria de acceso aleatorio o RAM).
Dispositivos de entrada/salida (E/S): Permiten que la computadora interactúe con el mundo exterior. Los dispositivos de entrada le permiten ingresar datos y comandos en la computadora (por ejemplo, teclado, mouse), mientras que los dispositivos de salida le permiten mostrar o transmitir los resultados del procesamiento (por ejemplo, monitor, impresora).
Bus: Sistema de conductores (cables o trazas en una placa de circuito impreso) que sirve como ruta de comunicación entre los diferentes componentes del sistema. Generalmente hay tres tipos principales de buses: Bus de datos: Transporta datos entre la CPU, la memoria y los dispositivos de E/S. Bus de direcciones: Especifica la memoria o la dirección del dispositivo de E/S al que se accede. Bus de control: Transporta señales de control que coordinan operaciones entre diferentes componentes.
Bus de datos: Transporta datos entre la CPU, la memoria y los dispositivos de E/S.
Bus de direcciones: Especifica la memoria o la dirección del dispositivo de E/S al que se accede.
Bus de control: Transporta señales de control que coordinan las operaciones entre los diferentes componentes.

Un elemento conceptual fundamental de la arquitectura von Neumann es el concepto de programa almacenado . Esto significa que tanto las instrucciones del programa como los datos sobre los que operan se almacenan en la misma memoria. Esta idea aparentemente simple representó un cambio crucial con respecto a las primeras computadoras, donde las instrucciones a menudo estaban conectadas directamente al hardware o almacenadas en medios separados.

El programa almacenado ofrece una enorme flexibilidad, ya que le permite cambiar el comportamiento de la computadora simplemente cargando un nuevo programa en la memoria. También le permite tratar las instrucciones como datos, allanando el camino para técnicas avanzadas como la modificación del código en tiempo de ejecución.

Si bien la arquitectura de von Neumann fue increíblemente influyente y subyace a la mayoría de las computadoras que utilizamos hoy en día, también tiene algunas limitaciones inherentes. El más conocido es el cuello de botella de von Neumann . Debido a que tanto los datos como las instrucciones deben pasar a través del mismo bus de memoria, la velocidad de ejecución del procesador puede verse limitada por la rapidez con la que se pueden recuperar los datos y las instrucciones de la memoria. Para superar esta limitación se han desarrollado varias técnicas, como el uso de memorias caché y arquitecturas alternativas. Una arquitectura alternativa importante es la arquitectura Harvard , utilizada en algunos sistemas especializados, como los procesadores de señales digitales (DSP), que separa físicamente la memoria de instrucciones de la memoria de datos, permitiendo acceder a ambas simultáneamente.

1.3 Teoría de la información de Shannon:
Medición de la incertidumbre

Simultáneamente con el desarrollo de las primeras computadoras y la formalización de los modelos computacionales, el trabajo pionero de Claude Shannon sobre teoría de la información , publicado en su artículo fundamental de 1948 "Una teoría matemática de la comunicación", proporcionó un marco teórico riguroso para cuantificar y comprender el concepto de información. Este trabajo ha tenido un profundo impacto no sólo en la informática, sino también en la ingeniería de telecomunicaciones y muchos otros campos.

Shannon definió la información en términos de reducción de la incertidumbre. Es decir, la información contenida en un mensaje es proporcional a la sorpresa que genera. Cuanto más inesperado es un evento o mensaje, más información transmite. Para cuantificar esta idea, Shannon introdujo la unidad fundamental de información: el bit (dígito binario). Un bit representa la cantidad de información necesaria para resolver una incertidumbre entre dos alternativas igualmente probables (por ejemplo, el resultado de un lanzamiento de moneda).

Matemáticamente, la cantidad de información (H) de un evento con probabilidad p de ocurrir se define como:

H = -log₂(p)

Donde el logaritmo es base 2, lo que refleja la naturaleza binaria del bit.

La teoría de la información de Shannon proporcionó las herramientas matemáticas fundamentales para:

Medición de la cantidad de información contenida en una fuente de datos o mensaje. Esto nos permitió definir la capacidad máxima de un canal de comunicación (el llamado teorema de Shannon-Hartley).
Comprensión de los límites teóricos de la compresión de datos . La teoría de Shannon establece un límite inferior al tamaño al que se puede comprimir un conjunto de datos sin pérdida de información (entropía).
Diseñar sistemas de comunicación confiables incluso en presencia de ruido o interferencias. La teoría de los códigos de corrección de errores, desarrollada a partir del trabajo de Shannon, permite agregar redundancia a los datos transmitidos para que los errores introducidos por el canal de comunicación puedan detectarse y corregirse.

El concepto de bit, derivado de la teoría de Shannon, se ha convertido en la unidad fundamental para representar y manipular información dentro de los sistemas informáticos. Cada dato, cada instrucción, cada imagen o sonido dentro de una computadora se codifica en última instancia como una secuencia de bits.

Los modelos computacionales de Turing y von Neumann, junto con la teoría de la información de Shannon, representan los pilares teóricos sobre los que se construyó el campo de la informática y continúa evolucionando. La Máquina de Turing proporcionó una definición formal de computabilidad y nos permitió explorar los límites de la computación algorítmica. La arquitectura von Neumann ofrecía un diseño práctico y flexible para fabricar computadoras electrónicas, que dominó la industria durante décadas.

Finalmente, la teoría de la información de Shannon proporcionó un marco matemático para comprender y gestionar la información, un elemento central de cualquier sistema informático. Comprender estos conceptos fundamentales no sólo es esencial para los estudiantes de informática, sino que también ofrece una perspectiva profunda sobre las raíces intelectuales de esta disciplina que continúa transformando nuestro mundo.