Clase Semana 1: Almacenamiento y transmisión de información mediante algoritmos
Camilo Meza Gaete
Created: 2022-05-26 Thu 09:24
Historia de la computación
La máquina analítica de Charles Babbage
Descrita en 1837, mediante sus componentes mecánicos debería poder servir como calculadora general (antes modeló una máquina para calcular tablas de logaritmos). Podría almacenar 1000 números de 50 dígitos cada uno, en base 10 (aproximadamente 16,2 kB).
Esta máquina se modeló a partir de los telares mecánicos y funcionaría a base de vapor. Tristemente los primeros modelos funcionales recién se produjeron 150 años después de su instrucción.
La primera programadora
Augusta Ada King, condesa de Lovelace. Se interesa por la máquina analítica de Babbage y, con su entusiasmo por las matemáticas, diseña un conjunto de instrucciones en tarjetas perforadas para determinar los números de Bernoulli.
Y no solo esto, también Ada visualiza la capacidad de esta máquina programable para relacionar estos números almacenados y sus conversiones con música e incluso imágenes.
De esta manera es también la primera ingeniera en computación.
Cálculo Lambda
En la década del 30, Alonzo Church y Stephen Kleene establecen un sistema formal que permite definir el concepto de función matemática, su aplicación y la recursión.
Las funciones en cálculo lambda son anónimas, además de no poseer estado. Sólo transforman sus entradas en salidas.
\[\lambda_{x,y} \rightarrow x + y\]
Church y Kleene logran demostrar que cualquier cálculo (computación) se puede realizar con las definiciones recursivas del cálculo lambda.
Máquina de Turing
Al igual que su profesor, Alan Turing realiza un aporte a la práctica de las máquinas computacionales:
- Una máquina teórica que puede leer y escribir en una cinta sin fin.
- El problema de la parada.
La máquina de Turing, como se conoce a este modelo, trabajaría en una cinta desde la cual se pueden leer instrucciones, moverse, y finalmente escribir en la cinta, de acuerdo a algún código.
El problema de la parada es algo más complejo: Si se tiene una máquina M, y se le da una instrucción I, ¿Podemos determinar si la máquina procesará I en un número finito de pasos?.
Hipótesis de Church-Turing
Gracias a estos aportes, se pudo obtener dos grandes avances:
- Una máquina que era capaz de modificarse siguiendo un conjunto de instrucciones.
- Un lenguaje formal en el que expresar estas instrucciones.
El cálculo lambda y la máquina de Turing son equivalentes.
Modelo de Von Neumann
El equipo de físcos a cargo de Jon Von Neumann, describe una arquitectura que permitiría emular (con limitaciones físicas) una máquina de Turing.
Conceptos matemáticos
Algoritmos
Habíamos propuesto que la algorítmica es dar instrucciones por medio de patrones, por ejemplo para calcular la suma de todos los enteros entre dos números:
\[\sum_{i=0}^{i=n} n = (n+1) \frac{n}{2} \]
Cálculo de una raíz cuadrada
Se podría expresar la raíz cuadrada como:
\(\sqrt{x} = y\) tal que \(y \geq 0\) y \(y^{2} = x\)
En pseudo-LISP se podría escribir lo siguiente:
(define (sqrt x) (the-y (and (>= y 0) (= (square y) x))))