Los artículos más influyentes en la historia de la ciencia de la computación

 (terriblesoftware.org)
6 puntos por GN⁺ 2025-01-24 | 1 comentarios | Compartir por WhatsApp
  • Siete artículos de ciencia de la computación publicados entre 1936 y 1998 dieron forma a las capas clave de la computación moderna: computabilidad, teoría de la información, bases de datos, complejidad, internet, la web y la búsqueda
  • El artículo de Alan Turing de 1936 se convirtió en el punto de partida del modelo moderno de computación al distinguir, mediante la Turing Machine, lo que una máquina puede y no puede calcular en principio
  • Claude Shannon, Edgar F. Codd y Stephen A. Cook crearon, respectivamente, un lenguaje común para la comunicación, los datos y la dificultad de los problemas mediante la medición de la información y la corrección de errores, el modelo relacional de datos, la NP-completeness y SAT
  • Los artículos de Vinton G. Cerf y Robert E. Kahn, Tim Berners-Lee, Sergey Brin y Larry Page definieron la estructura de la conexión entre redes, la conexión entre documentos y la búsqueda web con TCP/IP, la World Wide Web y PageRank
  • Al mirar también la lista extra —Lisp, programación estructurada, relojes lógicos, complejidad del software y Transformer—, entender los conceptos fundamentales se vuelve una ventaja competitiva más duradera que dominar herramientas nuevas

Criterios de selección y panorama general

  • La lista no es un ranking absoluto, sino una selección subjetiva basada en su influencia en el mundo actual
  • Los 7 artículos están ordenados cronológicamente y muestran una evolución que va de la computación a la comunicación, el almacenamiento de datos, la dificultad computacional, las redes, la web y la búsqueda
  • Aunque sigan apareciendo nuevos lenguajes, avances en IA, saltos cuánticos y frameworks de JavaScript, en la base de la computación moderna permanecen los conceptos creados por estos artículos

1. “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)

  • En la década de 1930, Alan Turing sentó las bases de lo que una computadora podía hacer en teoría mediante la Turing Machine imaginaria
  • El modelo central está compuesto por una cinta, un cabezal de lectura/escritura y un conjunto finito de estados
  • Este modelo define qué problemas pueden resolverse en un sentido mecánico y qué problemas no pueden resolverse
  • Todos los lenguajes de programación y el código operan dentro de las reglas definidas por Turing, y aun cuando se habla de computación cuántica se hace referencia a los límites planteados por Turing
  • Para leer más:

2. “A Mathematical Theory of Communication” (1948)

3. “A Relational Model of Data for Large Shared Data Banks” (1970)

  • Edgar F. Codd propuso el modelo relacional para almacenar y consultar datos a gran escala
  • La idea central es almacenar los datos en tablas y manipularlos mediante operaciones lógicas
  • Este diseño dio lugar a SQL y a la familia de bases de datos relacionales, que sostienen bancos, sitios de retail y sistemas empresariales
  • Incluso en la era NoSQL, conceptos de organización de datos como tablas, esquemas y consistencia siguen conectados con el modelo de Codd
  • Para leer más:

4. “The Complexity of Theorem-Proving Procedures” (1971)

5. “A Protocol for Packet Network Intercommunication” (1974)

  • El artículo de Vinton G. Cerf y Robert E. Kahn presentó las bases de TCP para conectar redes aisladas
  • Surgió un lenguaje universal que permitía que redes diferentes se comunicaran, y los datos se dividían en pequeños paquetes que recorrían múltiples rutas antes de reensamblarse del otro lado
  • Gracias a esta flexibilidad, la conectividad global se volvió posible sin necesidad de una única red gigantesca
  • Actividades como navegar por la web, enviar correos electrónicos o iniciar sesión en el sitio de un banco dependen de que TCP/IP mueva bits de forma confiable
  • Algunas aplicaciones en tiempo real usan UDP, pero la idea central de redes basadas en IP propuesta por Cerf y Kahn agrupa dispositivos bajo una sola red global
  • Para leer más:

6. “Information Management: A Proposal” (1989)

  • Después de que las máquinas pudieron comunicarse con facilidad, Tim Berners-Lee propuso la dirección de la World Wide Web, más fácil de usar para las personas
  • La idea central era un sistema global de hipertexto con hipervínculos, URL y HTTP
  • Al dejar de estar aislados y comenzar a conectarse entre sí, los documentos de todo el mundo hicieron que internet pudiera ser explorado no solo por científicos, sino también por usuarios comunes
  • Las semillas de experiencias web como las redes sociales, las compras en línea o leer una entrada de blog a las 3 de la mañana surgieron de esta propuesta
  • Para leer más:

7. “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (1998)

  • Sergey Brin y Larry Page crearon un enfoque basado en análisis de enlaces para manejar una web donde los enlaces y las páginas crecían explosivamente, y eso evolucionó hasta convertirse en el motor de búsqueda de Google
  • PageRank, la idea central, considera los enlaces no como un simple factor de cálculo de palabras clave, sino como votos de confianza
  • Este método mejoró mucho la relevancia de los resultados de búsqueda e hizo que la web se volviera un espacio buscable
  • La experiencia de escribir una pregunta en Google y obtener una respuesta inmediata funciona sobre PageRank y muchas innovaciones posteriores
  • PageRank redefinió la forma de explorar información en línea y abrió una nueva era de tecnologías basadas en datos, como publicidad, analítica y machine learning
  • Para leer más:

5 artículos que casi entran en la lista principal

  • “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) – John McCarthy
    • Introdujo Lisp y el estilo de programación funcional, que sigue presente en lenguajes y frameworks modernos
  • “Go To Statement Considered Harmful” (1968) – Edsger Dijkstra
    • Criticó que goto producía código desordenado y no estructurado, y detonó la revolución de la programación estructurada
  • “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) – Leslie Lamport
    • En los sistemas distribuidos, los relojes reales no pueden sincronizarse a la perfección, por lo que se necesitan relojes lógicos
  • “No Silver Bullet—Essence and Accident in Software Engineering” (1986) – Fred Brooks
    • Sostuvo que no existe un único método mágico capaz de resolver la complejidad esencial del desarrollo de software
  • “Attention Is All You Need” (2017) – Vaswani et al.
    • Presentó la arquitectura Transformer que está detrás de GPT y varios modelos de IA famosos

El impacto duradero de los conceptos fundamentales

  • Hoy siguen apareciendo nuevos lenguajes, innovaciones en IA, saltos cuánticos y frameworks de JavaScript cada semana
  • Si no se entiende de dónde vienen conceptos clave como estructuras de datos, algoritmos y la web, la situación se reduce a seguir acumulando herramientas nuevas
  • Estos 7 artículos y los trabajos extra nos invitan a repasar las ideas que se convirtieron en los cimientos de la computación moderna

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-01-24
Opiniones de Hacker News

  • También valdría la pena incluir Communicating Sequential Processes (Hoare), The Next 700 Programming Languages (Landin), As We May Think (Bush) y Can Programming Be Liberated from the von Neumann Style (Backus)
    Y este curso también parece bueno: https://canvas.harvard.edu/courses/34992/assignments/syllabu...
    “Este curso aborda los artículos que todo científico de la computación debería haber leído, desde la década de 1930 hasta la actualidad. Es una experiencia integradora que ayuda a estudiantes avanzados de ciencias de la computación a tener una visión de todo el campo; no es una simple panorámica, sino una forma de revivir su proceso de creación. Su objetivo es formar una perspectiva unificada del campo mostrando, a gran velocidad, toda la evolución de la informática a estudiantes que ya cuentan con cierto conocimiento previo”.

    • Parece que se necesita una cuenta de Harvard para ver el curso

  • Esta lista se siente como una combinación algo rara. No queda claro si está eligiendo artículos que influyeron en la ciencia de la computación, es decir, en la teoría de la computación; en la tecnología; o si simplemente llama ciencia de la computación a “todo lo relacionado con computadoras”
    El artículo de Turing es una base de la ciencia de la computación, pero me pregunto si la tecnología habría evolucionado de otra manera si no hubiera existido. La mayoría de los ingenieros de software ni siquiera lo ha leído. En cambio, el estándar IP es una piedra angular técnica, pero casi no tiene contenido científico; se parece más a una especificación de protocolo relativamente simple que hay que conocer si uno trabaja en temas de redes

    • Que el artículo de PageRank esté en una lista breve junto a los trabajos fundacionales de Turing y Shannon sobre computabilidad y teoría de la información se ve un poco fuera de lugar
      “On Computable Numbers, with an Application to the Entscheidungsproblem” ya tiene casi 90 años, pero sigue siendo tan verdadero y válido como entonces. No estoy tan seguro de que PageRank siga siendo tan relevante hoy como en 1998, y menos aún de que lo sea dentro de 50 años

  • Es una buena lista de artículos. Leí 5 de los 7 de la lista; los que todavía no leí son el de Cerf y Kahn, y el de Berners-Lee
    El artículo sobre computabilidad de Turing me resultó especialmente difícil de seguir, porque nombraba todo tipo de objetos con letras góticas mayúsculas y todas se parecían mucho entre sí. Tuve que consultar material complementario para poder leerlo, y hoy recomendaría leerlo junto con el libro comentado de Charles Petzold https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
    El artículo sobre NP-completitud de Cook también fue difícil y, como el de Turing, requirió material complementario. Hoy recomendaría leer primero un texto introductorio de complejidad computacional que siga la demostración de Cook
    El artículo de Shannon es como una obra de arte escrita con claridad y belleza, pero de ninguna manera es una lectura ligera
    Los artículos de Brin y Page, y de Codd, según recuerdo, no fueron muy difíciles, aunque para entender el trabajo de Brin y Page se necesita cierto conocimiento de álgebra lineal

    • No sé dónde hace falta álgebra lineal en el artículo de Brin y Page. La palabra “eigenvector” aparece una vez, pero es una mención secundaria
      El “algoritmo iterativo simple” es una forma de encontrar el punto fijo de una contracción arbitraria, sea lineal o no. El hecho de que también sea un eigenvector más bien estorba, y alguien que sepa del tema no usaría eliminación gaussiana
    • Si se puede conseguir el archivo fuente .tex, ayuda pedirle a GPT que haga los nombres de variables más legibles, cambiándolos por nombres de más de una letra

  • Si crees que A Mathematical Theory of Communication de Shannon es su contribución más fundamental a la ciencia de la computación, es que todavía no viste la tesis de maestría que escribió 10 años antes
    https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
    Él mostró que los elementos de conmutación de los circuitos, es decir, los transistores, podían definir lógica booleana
    Por supuesto, no quiero restarle importancia al logro de haber sentado las bases de toda la teoría de la información

  • La explicación de que “mostró que si algo es computable, en principio una máquina puede procesarlo, y dibujó una ‘Turing Machine’ hipotética” no es lo que Turing demostró
    Lo que demostró en ese artículo es que existen problemas que no pueden resolverse con una Turing Machine y, por lo tanto, probablemente no puedan resolverse con ninguna máquina. El Entscheidungsproblem del título, es decir, el problema de decisión, es precisamente eso
    A lo que apunta el texto original es a la llamada tesis de Church-Turing, que literalmente es más bien una tesis. En realidad no puede demostrarse, pero hay razones muy fuertes para creerla, porque en casi 100 años no se ha encontrado ningún sistema de cómputo más potente que una Turing Machine

    • Durante los últimos 100 años, la idea de dónde está la inteligencia artificial fue más bien en la dirección completamente opuesta
      En vez de construir una máquina que contenga todas las verdades conocidas, la exploración moderna de inteligencia artificial basada en máquinas terminó acercándose más a crear una máquina de folletín que rastrea y organiza comentarios humanos, algo distinto del enfoque axiomático leibniziano
    • Creo que es falso decir que “nadie ha encontrado un sistema de cómputo más potente que una Turing Machine”. Una Turing Machine no puede realizar no determinismo, pero el modelo de actores sí

  • Buen trabajo. Como venía haciendo algo parecido por mi cuenta, recomiendo algunos más
    RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
    PageRank: The PageRank Citation Ranking: Bringing Order to the Web (1999)
    MapReduce: MapReduce: simplified data processing on large clusters (2008)
    Bitcoin: Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
    retropropagación: Learning representations by back-propagating errors (1986)
    lógica de Hoare: An Axiomatic Basis for Computer Programming (1969)

  • ¿Dónde quedó el infame Evolution of Unix time-sharing systems de Dennis Ritchie?
    https://www.bell-labs.com/usr/dmr/www/cacm.pdf

  • Como todos están sumando sus recomendaciones, agrego una: aunque Cook fue quien presentó por primera vez la NP-completitud, el paper de Karp que presentó 21 problemas reducibles en tiempo polinómico a partir de 3SAT también fue una piedra angular enorme que despertó un interés más amplio por la teoría de Cook
    https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...

  • ¿Se les pasó New Directions in Cryptography (1976) de Diffie y Hellman?

  • No son papers, pero Why Software Is Eating the World de Marc Andreessen y la primera carta a los accionistas de Amazon, de 1997, merecen una mención especial
    “Las empresas de todas las industrias tienen que asumir que se viene una revolución del software. Esto incluye a las industrias que hoy ya se basan en software”
    https://a16z.com/why-software-is-eating-the-world/
    “Pero ahora es el Day 1 de Internet y, si ejecutamos bien, también es el Day 1 para Amazon.com”
    https://www.aboutamazon.com/news/company-news/amazons-origin...