Algorítmica y complejidad computacional. Muy breve historia (bibliográfica) de la teoría de grafos.

La primera versión, corta, de esta entrada se hizo el 15 de  mayo. Se ha actualizado para obtener una versión mas larga con actualizaciones el 16 y 17 de mayo.

Nota inicial. En una hora más o menos termina el día y “puente” de San Isidro, santo patrón de Madrid.

Este personaje muy real pero de vida en parte legendaria, además de serlo de Madrid, es también patrón de los labradores (oficio de la mayor parte de la población pre-moderna a nivel global y posiblemente todavía de gran parte de la población actual), y por lo tanto de casi todos los trabajadores, en general. Y por ello proponemos que sea también el patrón de los robots, que tarde o temprano heredarán casi todos nuestros trabajos.

Esto es así por uno de sus cinco milagros, el de los bueyes – En este milagro los bueyes aran y realizan las labores mientras Isidro reza. Al ser espiado por su amo, tras la acusación de que abandonaba el trabajo para rezar, éste ve cómo los bueyes aran solos. Esta escena contiene significativos paralelos con las hagiografías islámicas, pero muchos de estos aspectos quedan ahora cristianizados.  

Como no creemos en los milagros, pensamos que el santo estaría utilizando de alguna manera un robot. En la nota final tras el desarrollo de la historia principal de la entrada volvemos a este tema. En una visita a Madrid, recomendamos visitar lo que en el artículo de wikipedia llaman la Casa (Museo) de San Isidro.

Luego vamos a hablar de la importancia de las tablas matemáticas como aplicación principal cuya elaboración impulsó la automatización de la computación. Por ello, y ya que hablamos de  Madrid, conviene recordar a uno de sus primeros científicos conocidos, Maslama el Mayrití, muerto casi un siglo antes de que naciese Isidro Labrador y padre de la totalmente legendaria Fátima (wikipedia no es la única enciclopedia dónde aparecen erratas, más o  menos intencionadas).

Fin de nota  inicial.

Me interesa conocer el impacto de las ciencias y tecnologías computacionales sobre la teoría de grafos.

1.Ciencias y tecnologías computacionales.

a) Teoría computacional. Las  primeras, con una larga pre-historia,  nacen en 1936 con la publicación por parte de Turing del artículo Los números computables, con una aplicación al Entscheidungsproblem“.

El mismo año Church publica un artículo similar: An unsolvable problem of elementary number theory.

Sobre Turing y Church:

Su obra más conocida es el desarrollo del cálculo lambda, y su trabajo de1936 que muestra la existencia de problemas indecidibles. Este trabajo precedió el famoso trabajo de su alumno Alan Turing sobre el problema de parada que también demostró la existencia de problemas irresolubles por dispositivos mecánicos. Luego de revisar la tesis doctoral de Turing, demostraron que el cálculo lambda y la máquina de Turing utilizada para expresar el problema de parada tenían igual poder de expresión; posteriormente demostraron que una variedad de procesos mecánicos alternos para realizar cálculos tenían poder de cómputo equivalente. Como resultado se postuló la Tesis de Church-Turing

No  fueron los únicos. Por las mismas fechas Post estaba publicando en temas similares: In 1936, Post developed, independently of Alan Turing, a mathematical model of computation that was essentially equivalent to the Turing machine model. Y Kleene publicaba 1936. General recursive functions of natural numbers.

Todos estos trabajos que presentan la idea de universalidad computacional arrancan de la lógica matemática y están completamente desvinculados de la corriente de ingeniería computacional electrónica digital (que sustituye a la computación mecánica).

El punto de partida de estos primeros trabajos fueron las cuestiones fundamentales que D. Hilbert formuló en 1928, durante el transcurso de un congreso internacional:

1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración matemática?

2.- ¿Son las matemáticas consistentes, en el sentido de que no pueda probarse simultaneamente una aseveración y su negación ?

3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método definido que se pueda aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?.

La meta de Hilbert era crear un sistema matemático formal “completo” y “consistente”, en el que todas las aseveraciones pudieran plantearse con precisión. Su idea era encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. A este problema le llamó el `Entscheidungsproblem’. Si Hilbert hubiera podido cumplir su objetivo, cualquier problema que estuviera bien definido se resolvería simplemente al ejecutar dicho algoritmo.

Por desgracia para Hilbert, en la década de 1930 se produjeron una serie de investigaciones que mostraron que esto no era posible. Las primeras noticias en contra de esta idea surgieron en 1931 cuando K. Gödel publicó su famoso Teorema de Incompletitud.

El siguiente paso importante dentro de la teoría de la computabilidad lo constituye la aparición casi simultanea en 1936 de varias caracterizaciones independientes de la noción de calculabilidad efectiva. Estos artículos correspondian a los trabajos de Church, Kleene, Turing y Post. Los tres primeros mostraban problemas que eran efectivamente indecidibles; Church y Turing probaron además que el Entscheidungsproblem era un problema indecidible.

Finalmente, cabe reseñar el trabajo de E. Post. Este estaba interesado en marcar la frontera entre lo que se puede hacer en matemáticas simplemente por procedimientos formales y lo que depende de la comprensión y el entendimiento. De esta forma, Post formula un modelo de procedimiento efectivo a través de los llamados sistemas deductivos normales. Estos son sistemas puramente formales en los que puede `deducirse’ sucesiones finitas de símbolos como consecuencia de otras sucesiones finitas de símbolos por medio de un tipo normalizado de reglas y a partir de un conjunto de axiomas. Así pues, dada una sucesión finita de símbolos como entrada, las reglas permiten convertirla en una sucesión finita de salida. En su artículo, Post demostró resultados de incompletitud e indecibilidad en estos sistemas.

Post conocía los trabajos de Church-Kleene, si bien desconocia el trabajo de Turing, de tal forma que el modelo de procedimiento efectivo de Post, en esencia, difiere muy poco de las máquinas de Turing.

Fuente.

Además de los cuatro nombres citados debemos de añadir el nombre de Shannon y su tesis doctoral de 1938 en la que une la perspectiva teórica de la lógica matemática con la perspectiva ingenieril: Claude Shannon, whose 1938 master’s thesis in electrical engineering showed how to apply Boole’s algebra of logic to electronic switching circuits.

Desde el punto de vista teórico hoy el acento  se pone en la teoría de complejidad computacional: ¿ cuales son los algoritmos  más eficientes (en memoria, tiempo y otros parámetros) para  un problema dado ?.

b) Ingenieria computacional.

Para este apartado seguimos en parte el libro De Euclides a Java de Ricardo Peña Mari. También de interés el libro de Randell, The origins of digital computers: selected papers.

La linea ingenieril tiene un pedigree más extenso que la teórica. Los avances se han ido realizando en paralelo en software y hardware. Con respecto al hardware la tendencia innovadora ha seguido la linea del aligeramiento: masa física–>masa electrónica–>individuos cuánticos (cuyo potencial y factibilidad está en investigación). Y con respecto al software, la tendencia innovadora ha seguido la línea del aumento de flexibilidad: máquina diseñada para computar un problema  específico y sólo este problema–>máquina programable–>máquina universal. Explicamos muy brevemente esto en lo que sigue.

Nota. Creo que además de una historia de la teoría y de la ingeniería de la computación sería interesante hacer una historia de la práctica de la computación: ¿ que tipos de problemas eran los más exigentes desde el punto de vista computacional a lo largo de la  historia ?; todos los diseños anteriores al sXX, ¿ se utilizaron en la práctica o sólo fueron prototipos de circo ?. En definitiva una historia de la organización industrial del sector de la informática. Añadimos algunos comentarios al respecto.

Como veremos las principales aplicaciones durante mucho tiempo fueron las tablas matemáticas (ver también este enlace de la misma página web): astronómicas, de navegación, balísticas, actuariales etc….

Hoy el cálculo de estas tablas es trivial (más bien está informatizado). Sin embargo hubo un momento en el que su presencia en una civilización indicaba que ésta estaba en la vanguardia tecnológica, y su ausencia lo contrario.

La civilización islámica por ejemplo fue una gran productora  de este tipo de tablas. También conocían el concepto de automatización y de programación de autómatas, de herramientas de cálculo y por supuesto el concepto de algoritmo. Sin embargo finalmente no se desarrolló en esta civilización la  mecanización del cálculo.  Y lo mismo sucedió en Europa durante mucho tiempo. Desconozco la situación al respecto en la civilización China e India y en las civilizaciones pre-colombinas, que tuvieron todas ellas astronomías avanzadas.

¿ Pq hasta el sXIX la situación global no estaba madura para este tipo de mecanización  ?. Realmente hasta el computador puramente electrónico, la industria era muy de nicho. Y este paso dependía del desarrollo de la tecnología vinculada a la electricidad. Por otra parte, cuando en Occidente emergió un buen conocimiento de la electricidad ya existía la tenencia a la mecanización del cálculo. ¿ Existió esta en las otras tradiciones mencionadas ?.

Una historia de las tablas matemáticas. Muy interesante. Precisamente lo que estaba buscando. Los grandes hitos de las Tablas Astronómicas son bien conocidos: Ptolomeo y su Almagesto, en el marco de la Biblioteca de Alejandria; Al-Kwarizmi en el marco de la Casa de la Sabiduría de Bagdad (probablemente elinterés de este autor en el álgebra no era puramente teórico); las Tablas de Toledo / Tablas Alfonsinas en la España medieval; y las Tablas derivadas de la revolución astronómica del Renacimiento (Brahe, Kepler, etc…).

De las Tablas Astronómicas se derivan las Tablas de Efemérides.

Con Napier comienza la elaboración de Tablas Matemáticas. Luego se empezarían a elaborar tablas de otras  funciones.

Las Tablas Actuariales comenzaron más tarde pero no de manera totalmente independientes de las otras tablas, con las que aparentemente no tienen nada que ver. El factor común son los autores: Halley fue autor de Tablas astronómicas y actuariales. Y lo mismo Babbage, de tablas matemáticas y actuariales.

También hubo matemáticos implicados en la elaboración de Tablas Balísticas. De hecho el pionero de las tablas balísticas fue el conocido  matemático renacentista Tartaglia (one of Tartaglia´s greatest contributions to the science of ballistics was his firing tables, which he published in  Nova Scientia or The New Science. These firing tables listed ballistics for all guns built in his time, and were important in educating and training future ballisticians…Niccol`o Tartaglia (1500–1557), was the first to use mathematics to study of the paths of cannonballs. He published two books, Nova scientia (1537) and Quesiti et Inventioni diverse (1546), which deal with gunnery). Seguido por Galileo y Newton, aunque no se si estuvieron implicados en la elaboración de tablas (In the second half of his greatest work, The Dialogues of the Two New Sciences (1638), Galileo took up the question of projectile motion. He argued convincingly that the path of a projectile in a vacuum was a parabola. This conclusion served gunners well — at least in certain circumstances.2 Evangelista Torricelli wrote a book, De motu that greatly impressed Galileo. It contained a geometrical way of computing the range of a projectile.3 Also important in our pre-history of scientific gunnery is Newton’s Principia (1787) where he argued, among much else, that air resistance is proportional to the square of the speed of the projectile). En este campo se cita mucho a Robins. Euler trabajó también en balística.

También nos comentan: One can discern five distinct styles of table making: the solitary table maker; communal computing; computing bureaus; mechanized computing; and, finally, computerization.

Muy interesante como precedente de la computación distribuida: However, from the earliest times big table-making projects had to employ several human computers. One of the best known examples of such a group endeavour is the Nautical Almanac, published continuously from 1767. As described by Wilkins in Chapter 11,the Astronomer Royal Nevil Maskelyne employed a network of computers, many of whom served for decades.The computers were all freelance, located all over England, and their work was entirely coordinated though the postal system 

A finales del XVIII la escala de los proyectos es ya de mayor envergadura y se necesita reorganizar la actividad: In 1790, Gaspard Riche de Prony established the Bureau du Cadastre to produce a new set of tables for the French ordnance survey. The Bureau marked a transition from small, informal computing teams to a large-scale, highly organized bureaucracy….The Bureau du Cadastre 10 introduction Croar-intro.qxd 4/24/03 4:58 PM Page 10 was in every sense a computing ‘factory’.The Bureau employed three classes of labour: a small advisory group of eminent analysts; an executive group of between six and eight professional mathematicians; and a large number of between 60 and 80 relatively unskilled computers.

The computing bureau style of operation remained popular for major table-making projects until after the Second World War.The best documented was the WPA Mathematical Tables Project established in New York in the 1930s depression, described by Grier in Chapter 10. The WPA project was established partly as a make-work project for the unemployed, but also as a genuinely needed computing service. At its peak the project employed 200 computers, and it came into its own with the computation of LORAN tables in the early years of the war.The WPA project was by no means the only such computing organization in wartime America. For example, the Army’s Ballistics Research Laboratory and Moore School of Electrical Engineering at the University of Pennsylvania employed a team of 100–200 female computers (each equipped with a desk calculating machine) to make ballistics tables. This tide of table making,which threatened to overwhelm existing methods,led the Moore School to become the birthplace of the modern computer.

Claramente, como veremos el paso al computador electrónico se dio en un contexto (la IIGM) en el que se necesitaba producir a gran velocidad tablas balísticas precisas. ¿ La alternativa a ENIAC no eran millones de computadores humanos ?. En este artículo nos cuentan la historia del departamento de computación balística de EEUU. Ya en la IGM se experimentó la necesidad, pero no emergieron los computadores electrónicos. Hoy este problema no requiere mayor poder computacional, pero la velocidad en resolver problemas que se podrían resolver más lentamente sigue siendo uno de los mayores vectores de desarrollo del sector de supercomputación.

Muy interesantes las condiciones en las que se dio este gran salto tecnológico.

Fin de nota.

Toda computación implica movimiento de algún ente físico. Hasta el advenimiento del computador electrónico, la computación se hacía moviendo cuerpos físicos completos (masas de protones, neutrones, electrones, con su estructura química: computación mecánica). Estas máquinas eran complejas de diseñar y su dinámica era lenta y costosa. Por ello era más adecuado utilizar máquinas biológicas (seres humanos) para realizar cómputos. Las máquinas biológicas se apoyaban en herramientas computacionales como el quipu andino-américano, el ábaco euroasiático o la regla de cálculo. Todavía en el  s. XX operadores de ábaco japoneses competían con éxito con máquinas computacionales más avanzadas.

El quipu como sistema de registro es muy interesante. Quizás hagamos alguna entrada al respecto. El más antiguo, encontrado en un contexto Caral, se fecha en torno a 2500 BC. Por lo tanto la aparición de los sistemas de registro en esta zona de civilización son casi contemporáneos a la de su aparición en Mesopotamia. Aunque no he estudiado el tema en detalle, cada vez estoy más convencido de que su capacidad expresiva es equivalente al lenguaje. Esto nos comenta José de Acosta en 1590: Son quipus unos memoriales o registros hechos de ramales, en que diversos nudos y diversos colores significan diversas cosas. Es increíble lo que en este modo alcanzaron, porque cuanto los libros pueden decir de historias, y leyes, y ceremonias y cuentas de negocios, todo eso suplen los quipus tan puntualmente, que admiran. Otro comentario, ya no de Acosta: El virrey Francisco de Toledo, incorporó entre 1570 y 1581 el quipu al sistema administrativo del Virreinato. Eran frecuentemente utilizados en el culto católico para memorizar las oraciones y para recordar los pecados en la confesión. Y otro comentario: Varios autores les han considerado un sistema de codificación de información comparable a la escritura pues es posible lograr más de 8 millones de combinaciones gracias a la diversidad de colores de cuerdas, distancia entre cuerdas, posiciones y tipo de los nudos posibles. No se sabe como podría haberse codificado el contenido textual más allá de algunas simples secuencias. Hay algunos pueblos andinos alejados que mencionan tener «escritos» en los quipus de su localidad.

Inicialmente las máquinas de cómputo analógicas (los múltiples antecedentes en las Edades antigua y media, en variadas  civilizaciones, Schickard, Pascal, Liebniz ya en la Edad Moderna) aunque diseñadas por usuarios de matemáticas, fueron más bien un animal de circo, prácticamente sin utilidad. No había mercado o era muy de nicho (recaudadores de impuestos, tablas astronómicas; esta última aplicación ha dejado huella: todavía hoy a un número enorme astronómico).  Eran mecánicas y de cómputo específico. Fueron más intentos que realizaciones de uso práctico.

Máquinas calculadoras de propósito específico.

Pero hay excepciones a la regla anterior como el aritmometro y el comptometro.

La máquina de Thomas de Colmar (French inventor and entrepreneur best known for designing, patenting and manufacturing the first commercially successful mechanical calculator, theArithmometer, and for founding the insurance companies Le Soleil and L’aiglewhich, under his leadership, became the number one insurance group in France at the beginning of the Second Empire.).

Thomas de Colmar había trabajado hasta 1819 en el ejército, encargado de temas de logística,  lo cual le inspiró su máquina, que por ser de propósito específico, era más una calculadora que un ordenador tal y como lo entendemos hoy. Sin embargo, because it was the first mass-marketed and the first widely copied calculator, its design marks the starting point of the mechanical calculator industry, which eventually morphed into the electronic calculator industry and which, through the accidental design of the first microprocessor to be commercialized, the Intel 4004, for one of Busicom‘s calculator in 1971, led to the first commercially available personal computer, the Altair in 1975.

Initially Thomas spent all of his time and energy on his insurance business, therefore there is a hiatus of more than thirty years in between the first model of the Arithmometer introduced in 1820 and its true commercialization in 1852. By the time of his death in 1870, his manufacturing facility had built around 1,000 Arithmometers, making it the first mass-produced mechanical calculator in the world, and at the time, the only mechanical calculator reliable and dependable enough to be used in places like government agencies, banks, insurance companies and observatories just to name a few. The manufacturing of the Arithmometer went on for another 40 years until around 1914. This calculator could add and subtract two numbers directly and could perform long multiplications and divisions effectively by using a movable accumulator for the result. Patented in France byThomas de Colmar in 1820.  Su patente. Its production debut of 1851 launched the mechanical calculator industry[1] which ultimately built millions of machines well into the 1970s. For forty years, from 1851 to 1890,[4] the arithmometer was the only type of mechanical calculator in commercial production and it was sold all over the world. During the later part of that period two companies started manufacturing clones of the arithmometer: Burkhardt, from Germany, which started in 1878, and Layton of the UK, which started in 1883. Eventually about twenty European companies built clones of the arithmometer until the beginning of World War I.

A continuación algunos datos sobre este mercado: oferta, demanda, precio.

 Because of its reliability and accuracy, government offices, banks, observatories and businesses all over the world started using the arithmometer in their day-to-day operations. 

The fundamental design stayed the same; and after 50 years at the top, the arithmometer lost its supremacy in the mechanical calculator industry. While in 1890, the arithmometer was still the most produced mechanical calculator in the world, ten years later, by 1900, four machines, the comptometer and Burroughs’ adding machine[13] in the USA, Odhner’s Arithmometer[14] in Russia, and Brunsviga in Germany had passed it in volume of machines manufactured. 

Production of the arithmometer stopped in 1915, during World War I. Manufacturing had started in 1851 and ended around 1915. There were about 5,500 machines built during this sixty-year period; 40% of the production was sold in France and the rest was exported. 

5500 por esta compañía. Pero había bastantes otras. De cualquier manera no se puede considerar un mercado masivo…

A 12-digit arithmometer sold for 300 francs in 1853, which was 30 times the price of a table of logarithms book and 1,500 times the cost of a first-class stamp (20 French cents), but, unlike a table of logarithms book, it was simple enough to be used for hours by an operator without any special qualifications.[22]

An advertisement taken from a magazine published in 1855 shows that a 10-digit machine sold for 250 francs and a 16-digit machine sold for 500 francs

No vamos a var detalles de otra evolución tecnológica similar, el comptometro.

Máquinas programables.

Antes con Jacquard (1800, inspirado por Bouchon) nace el concepto de máquina programable, aplicado a un sector atípico, el textil. El método utilizado para la implementación de este concepto, la tarjeta perforada, dominaría la computación hasta el advenimiento  del coputador electrónico.

Jacquard inspiró a Babbage , que tenía una motivación puramente práctica: tablas astronómicas y de navegación. Comienza su primer proyecto en 1823 (máquina de diferencias para evaluación de polinomios), recibiendo apoyo de la armada Británica y el segundo en 1833 (máquina analítica, primer computador programable de propósito general).  Se apoyó para la programación de la máquina en Ada Lovelace, que ya se hacía consideraciones de complejidad computacional. No terminó ninguno de los dos proyectos.

El tercer nombre a destacar de este período es Hollerith (1860-1929).  Su motivación es también puramente práctica: automatizar en la medida de lo posible los censos de EEUU. Y la tecnología es la de la tarjeta perforada, adaptada a esta tarea censal. La empresa fundada por Hollerith sería el embrión de IBM. Empleados de Hollerith fundaron el embrión de la Rand Corporation.

Siendo todo esto así, antes del computador electrónico, durante la primera globalización,  como vemos ya existía un incipiente sector industrial de la informática, sea de máquinas calculadoras de propósito específico no programables, sea de máquinas programables.

También había un entorno institucional favorable a este tipo  de innovaciones.  Herman Goldstine comenta en su libro The computer: from Pascal to Von Neumann: es destacable la característica de nuestro sistema de que gran parte de la pujanza de la industria de computación americana sea debida a la generosidad de su gobierno, que permite a sus empleados y contratistas patentar y explotar sus invenciones, realizadas frecuentemente con fondos del propio gobierno. Como es conocido, todo esto ha cambiado: hoy el gobierno de EEUU no se lo pone fácil ni siquiera a aquellos que inventan sin haber recibido financiación de sus fondos…

¿ Que motivó el salto a la computadora electrónica ?. No vamos a profundizar excesivamente en este importante tema. En la década de los 30 las máquinas disponibles ya no eran adecuadas para la escala de los problemas que se atacaban (navegación; balística con los nuevos armamentos; logística militar).

IBM se embarca en la construcción de máquinas más potentes siguiendo una tecnología electromecánica. El resultado es la máquina de Aiken, Mark I (1939-1944).

¡¡ Un anuncio muy explícito !!.

Otros hitos en la transición del computador mecánico al puramente electrónico son: ABC; it was built by Atanasoff and Berry in the basement of the physics building at Iowa State College during 1939–42….

ABC,

–was not a Turing complete computer, which distinguishes it from more general machines, like contemporary Konrad Zuse‘sZ3 (1941), or later machines like the 1946 ENIAC, the 1949 EDVAC, the University of Manchester designs, or Alan Turing‘s post-War design of ACE at NPL and elsewhere.

–Nor did it implement the stored program architecture that made practical fully general-purpose, reprogrammable computers.

–y añadimos que tampoco era puramente electrónico, sino de tipo electromecánico.

Mark I, máquina electromecánica sólo suponía una aceleración de x3 con respecto a una máquina biológica (calculador humano más herramienta). Los límites  de la electromecánica eran evidentes. Esto es lo que propició la adopción de una tecnología puramente electrónica. La disponible en aquellos momentos era la tecnología de válvulas de vacío o triodos, la adoptada por ENIAC.

A ENIAC se le considera el primer computador puramente electrónico programable e universal (de propósito general). Su motivación fue el computo de tablas balísticas en el contexto de la IIGM. Una buena tabla balística podía determinar la eficiencia de un bombardeo y por lo tanto el resultado de una guerra. Cada tabla constaba de unas 3000 trayectorias ya cada trayectoria requería unas 2000 multiplicaciones (he visto otras cifras más bajas de este segundo parámetro). Si un humano podía hacer una multiplicación en 10 segundos (para la cantidad de dígitos implicados en las tablas balísticas), Mark I la hacía en 3 segundos y ENIAC en 3 milisegundos. En este último caso la escala de la ganancia es evidente. Sus diseñadores fueron Mauchly, Eckert y Goldstine.

Nota. No estamos a favor de la guerra. Pero existe y en ocasiones ha sido fuente de avances tecnológicos. Nos limitamos a descibirlo. Fin de nota.

DVAC añade el almacenaje del propio programa en la computadora, innovación que como es bien conocido, se debe a Von Neumann. Cada tipo de cañón necesitaba una propia tabla balística. Reprogramar a ENIAC a estos efectos era muy engorroso.  La computadora de programa almacenable permitía pasara de una tabla a otra de manera mucho más rápida. Von Neumann además de en este proyecto también estaba implicado en el proyecto Manhattan, que requería también mucho poder de cálculo (todavía hoy esta aplicación se encuentra en la vanguardia de la supercomputación). Lo que definió Von Neumann fue la arquitectura de computadores que se ha utilizado hasta ahora.

En paralelo a estos desarrollos en el otro frente estaba Zuse que empezó con una computadora mecánica programable (Z1) en 1935 (todavía al margen de la guerra: trabajaba como ingeniero y quería ahorrarse los tediosos cálculos). Z2 ya tenía procesador eléctrico, aunque la memoria era todavía mecánica (procesador eléctrico, aunque basado en relays de telefonía y no en válvulas de vacío; en el artículo sobre Z3 explican la historia). Sobre Z3: Improving on the basic Z2 machine, he built the Z3 in 1941. On 12 May 1941 Zuse presented the Z3, built in his workshop, to the public.[17][18] The Z3 was a binary 22-bit floating point calculator featuring programmability with loops but without conditional jumps, with memory and a calculation unit based on telephone relays. The telephone relays used in his machines were largely collected from discarded stock. Despite the absence of conditional jumps, the Z3 was a Turing complete computer. However, Turing-completeness was never considered by Zuse (who had practical applications in mind) and only demonstrated in 1998.   Me falta el contexto organizativo de todas estas iniciativas: ¿ pasaron de prototipos y como ENIAC se utilizaron para hacer cálculos más potentes o no ?. ¿ Eran rápidas o el uso de relays las ralentizaba ?. En el artículo de  wikipedia sobre Z3 comentan que se tardaba 3 segundos en una multiplicación  lo cual no era un gran avance con respecto al estado del arte de una máquina humana.

Se confirma que los relays eran comparativamente lentos con respecto a los tubos de vacío: relays suffered from several problems: they were large (that’s why the Harvard Mark I had to be so big); they needed quite hefty pulses of power to make them switch; and they were slow (it took time for a relay to flip from “off” to “on” or from 0 to 1)The vacuum tube, each one about as big as a person’s thumb and glowing red hot like a tiny electric light bulb, had been invented in 1906 by Lee de Forest (1873–1961), who named it the Audion. This breakthrough earned de Forest his nickname as “the father of radio” because their first major use was in radio receivers, where they amplified weak incoming signals so people could hear them more clearly. In computers such as the ABC and Colossus, vacuum tubes found an alternative use as faster and more compact switches.

Y se confirma que la Alemania nazi no vio del todo las ventajas de la automatización, al menos para acelerar cálculos: Things were very different in Germany. When Konrad Zuse offered to build his Z2 computer to help the army, they couldn’t see the need—and turned him down. 

Fuente de estas últimas citas.

Nota.

Es curioso que alguien capaz de idear por si sólo el salto al computador electrónico digital programable universal no se le ocurriese la idea cambiar de centro de trabajo: todos sus productos, Z1, Z2 y Z3  fueron bombardeados y destrozados una y otra vez.

¿ No se podía considerar una oficina en el campo ?

Fin de nota.

Todos estos desarrollos están vinculados a campos bien de la lógica (por ejemplo Censos) bien del cálculo matemático (tablas astronómicas, tablas de navegación, tablas balísticas), no del todo relacionados o no directamente relacionados con el tema que nos ocupa, que es la teoría de grafos, con la excepción de problemas logísticos. Además de la logística, el desarrollo de las telecomunicaciones vía telefonía también impulsó la automatización de la computación con una relación directa con la teoría de grafos.

Hoy el gran salto natural debería ser pasar de la computación electrónica, basada en corrientes eléctricas y por lo tanto en el movimiento controlado de masas de electrones, a la cuántica, que se basa en el movimiento controlado de “individuos cuánticos”, lo cual está generando una cantidad importante de trabajo teórico e ingenieril. Es mucho más complicado controlar o programar individuos físicos que masas de individuos, sean mecánicas o electrónicas.  Y tampoco está claro el alcance de la computación cuántica en términos de eficiencia computacional.

Cuando uno estudia el cambio tecnológico en retrospectiva, se ve que aunque inicialmente se abre una abanico amplio de opciones, al final solo unas pocas pueden ofrecer el rendimiento que se busca, subir un peldaño en la escala, atravesar el cuello de botella tecnológico. O tienes llamas y entonces te quedas con una civilización peatonal, con todas sus limitaciones), o tienes caballos / camellos y entonces cabalgas y avanzas en escala (ya hemos hablado de este  contraste en anteriores entradas). O tienes electricidad o no desarrollas una computación de mucha mayor escala. Solo la electricidad no ea suficiente.  Todo lo demás eran grandes avances, pero sin electricidad no tendríamos la computación que tenemos. La electricidad ya se usaba para aplicaciones de telegrafía desde 1833 pero el gran salto se dio más tarde durante la II Revolución Industrial. El auténtico mundo moderno tecnológicamente hablando nace en este momento.

Por otra parte, sólo con la electricidad no era suficiente: el relay no era mucho más rápido que un engranaje.

¿ Tenemos hoy las necesidades de escalar computacionalmente que existían durante la IIGM ?. ¿ Hay alguna ruta viable para escalar la cima de la computación cuántica ?. No lo sabemos.

Nota.

La historia de la ciencia e ingeniería eléctrica, de la que dependen múltiples tecnología de uso masivo hoy en los sectores de energía, telecomunicaciones, comunicaciones y computación es de gran interés. Se puede ver como la historia de como controlar un fluido y usarlo en beneficio propio. Ya hemos comentado en otras entradas sobre los impactos del  control de otros dos fluidos, el agua, cuya consecuencias fueron las primeras civilizaciones del Bronce y en especial los sistemas de registro / escritura (es decir el control del agua llevó al control del discurso y al  kit tecnológico del Bronce en general), y los rebaños, siendo el pastoreo nómada su extremo, cuya consecuencia fueron los grandes  imperio multiétnicos del Hierro (con el Imperio Multiétnico nacen las ideologías universalistas y el kit tecnológico del Hierro en general; es decir el control del rebaño llevó al control de las mentes mediante las ideologías universalistas; quien dice control de mente dice unidad: en la época de los imperios multiétnicos es cuando acomenten esfuerzos para la unidad de convenciones, como la lengua, la moneda, pesos y medidas, calendarios  etc…y para la  unidad geográfica con el desarrollo de grandes infraestructuras). La navegación interoceánica global,  que se basa en el control / uso de otro fluido, el viento, fue la tercera gran oleada de avance en la escala tecnológica. Y consideramos al control de la electricidad como el cuarto escalón, símbolo de la Segunda Revolución Industrial y el mayor representante de la tecnología actual. Quizás también haya un escalón intermedio, con el control del calor que se pone de manifiesto en las máquinas termodinámicas (motor de explosión) y símbolo de la Primera Revolución Industrial.

El orden es el siguiente: energía hidráulica, animal, eólica, termodinámica y eléctrica. ¿ otro orden es posible en el desarrollo de la civilización ?.  Es interesante ver que los primeros cuatro desarrollos estaban completamente vinculados a un determinado tipo localizaciones dónde se daban determinadas condiciones del entorno, una para cada tipo (hemos hablado mucho sobre este tema; nos queda por estudiar pq el Pacífico no se exploró desde China), además de a un estadio de desarrollo social. Sin embargo el último desarrollo, aquel sobre el que hablamos, la electricidad, parece únicamente vinculado a un estadio de desarrollo social, aquel dónde la visión naturalista / científica del  mundo predomina. Dado este estadio, no veo ninguna localización dónde no se podría haber desarrollado.

Bueno nos centramos en los principales hitos para el control de la energía eléctrica.

El estado de la cuestión en 1767 se puede ver en el libro de Priestley (1733-1844), The history and present state of electricity. Es más o menos contemporáneo de Franklin (1706-1790). En esa época y hasta el final del XVIII todavía se estudiaba la fenomenología, las diferentes manifestaciones de esta forma de energía.  No se sabía si lo eran o no. Por ejemplo todavía en 1791 Galvani (otro contemporáneo, 1737-1798) tiene que demostrar que es este fluido el responsable de la bioelectricidad. También había algunos productos tecnológicos basados en la electricidad estática (Kleist o Leyden jar).  Es lo que en tecnología eléctrica se llama capacitador.  Con precedentes en el XVII (von Guericke).

El siguiente gran hito teórico y tecnológico es Volta, de la siguiente generación (1745-1827): With this invention Volta proved that electricity could be generated chemically and debunked the prevalent theory that electricity was generated solely by living beings. Como es bien conocido inventó la batería.  Sin embargo Although early batteries were of great value for experimental purposes, in practice their voltages fluctuated and they could not provide a large current for a sustained period. The Daniell cell, invented in 1836 by British chemist John Frederic Daniell, was the first practical source of electricity, becoming an industry standard and seeing widespread adoption as a power source for electrical telegraph networks….Batteries provided the main source of electricity before the development of electric generators and electrical grids around the end of the 19th century.

El telégrafo fue el primer intento de utilizar la electricidad para comunicaciones rápidas a larga distancia. Hubo múltiples intentos, múltiples variantes. Entre otros un telégrafo óptico, Chappe, que si se implementó.

 No siempre los departamentos de defensa ven con buenos ojos los avances tecnológicos: The first working telegraph was built by the English inventor Francis Ronalds in 1816 and used static electricity…Offering his invention to the Admiralty in July 1816, it was rejected as “wholly unnecessary”. His account of the scheme and the possibilities of rapid global communication in Descriptions of an Electrical Telegraph and of some other Electrical Apparatus[12] was the first published work on electric telegraphy and even described the risk of signal retardation due to induction.[13]Elements of Ronalds’ design were utilised in the subsequent commercialisation of the telegraph over 20 years later.

En la década de los 30 del XIX había ya una carrera tecnológica con respecto al telégrafo eléctrico, en la que estaban implicados UK, Prusia, EEUU. Esta oleada estuvo precedida en los 20 del descubrimiento e invención de diversos fenómenos (se sigue investigando la fenomenología) y elementos tecnológicos de control del flujo eléctrico: Orsted y el electromagnetismo (1820, precedido al parecer por Romagnosi), Schweigger y el galvanometro (1820), Ampere y a electrodinámica (in 1827 Ampère published his magnum opus, Mémoire sur la théorie mathématique des phénomènes électrodynamiques uniquement déduite de l’experience (Memoir on the Mathematical Theory of Electrodynamic Phenomena, Uniquely Deduced from Experience), the work that coined the name of his new science, electrodynamics, and became known ever after as its founding treatise) ; Sturgeon y Henry y el electromagneto (década 20 también), Ohm y la relación potencial corriente (1827), Faraday y la inducción electromagnética y las dínamos (1831 ).

Pese a todos estos avances normalmente se asocia el telégrafo al nombre de Morse, de EEUU. Morse era pintor y es interesante ver su motivación para implicarse en el telégrafo: As noted, in 1825 New York City had commissioned Morse to paint a portrait of Lafayette in Washington, DC. While Morse was painting, a horse messenger delivered a letter from his father that read, “Your dear wife is convalescent“. The next day he received a letter from his father detailing his wife’s sudden death.[7]Morse immediately left Washington for his home at New Haven, leaving the portrait of Lafayette unfinished. By the time he arrived, his wife had already been buried.[8] Heartbroken that for days he was unaware of his wife’s failing health and her death, he decided to explore a means of rapid long distance communication.[9]  

De momento estamos haciendo un análisis en términos absolutos de esta tecnología sin relacionarla con otras tendencias tecnológicas o sociales del momento. Lo que su desarrollo pone de manifiesto es que la gente estaba empezando a moverse con mucha más frecuencia y en movimientos de mucho más alcance o distancia. Por lo tanto un medio de comunicación rápido era necesario. La Revolución Francesa disolvió la sociedad del Antiguo Régimen. Las ataduras que anclaban a la mayoría de la gente a su terruño  desaparecen.  Todo esto nos lleva a pensar que en paralelo había desarrollos importantes en la industria del transporte: built by George Stephenson and his son Robert‘s company Robert Stephenson and Company, the LocomotionNo. 1 is the first steam locomotive to carry passengers on a public rail line, theStockton and Darlington Railway in 1825. George also built the first public inter-city railway line in the world to use steam locomotives, the Liverpool and Manchester Railway which opened in 1830.

A finales de la década de los 30, la tecnología del telégrafo eléctrico ya está madura y empiezan los movimientos comerciales:  The first commercial electrical telegraph, the Cooke and Wheatstone telegraph, was co-developed by William Fothergill Cooke and Charles Wheatstone; In the United States, the Morse/Vail telegraph was quickly deployed in the two decades following the first demonstration. The overland telegraph connected the west coast of the continent to the east coast by 24 October 1861, bringing an end to the Pony Express.

Desde la década de los 40 del XIX hasta el sXXI se ha seguido utilizando, aunque cada vez con menos cuota tras la introducción de otros medios de telecomunicación.

A nuestros efectos es importante señalar que aunque el telégrafo ya estaba operativo incluso  comercialmente desde la década delos 40,  los esfuerzos contemporáneos para la automatización del cálculo se orientaron hacia su mecanización, no hacia su electrificación. La convergencia de la electricidad con la computación no se hizo hasta casi  un siglo más tarde, lo cual llama la atención.

Volvemos a la electricidad. Tras todos los avances señalado, especialmente tras Faraday, la situación ya estaba madura para una teoría general del electromagnetismo, matematizada. Como es bien conocido, de esto se encargó Maxwell (1973). Industrialmente dos nombres destacan en este fin de siècle, Siemens y Edison tendencias destacan en este momento, asociados a aplicar la electricidad a múltiples aplicaciones prácticas: iluminación, red eléctrica, etc…

During this period commercial use of electricity increased dramatically. Starting in the late 1870s cities started installing large scale electric street lighting systems based on arc lamps.[21] After the development of a practical incandescent lamp for indoor lighting, Thomas Edison switched on the world’s first public electric supply utility in 1882, using what was considered a relatively safe 110 volts direct current system to supply customers. Engineering advances in the 1880s, including the invention of the transformer, led to electric utilities starting to adopting alternating current, up till then used primarily in arc lighting systems, as a distribution standard for outdoor and indoor lighting (eventually replacing direct current for such purposes). In the US there was a rivalry, primarily between a Westinghouse AC and the Edison DC system known as the “War of Currents” .

En la década de los 80 los experimentos de Hertz confirman la teoría de Maxwell: Hertz did not devise a system for practical utilization of electromagnetic waves, nor did he describe any potential applications of the technology. Hertz was asked by his students at the University of Bonn what use there might be for these waves. He replied, “It’s of no use whatsoever. This is just an experiment that proves Maestro Maxwell was right, we just have these mysterious electromagnetic waves that we cannot see with the naked eye. But they are there”. Aunque todas ellas ya se estaban intentando desde antes de Hertz, este es el disparadero para otras tecnologías que necesitan la electricidad: radio, teléfono, televisión, etc…

La radio se asocia normalmente a Marconi, que obtiene su primera patente en 1897 y pasa a modo comercial en el mismo año constituyendo una sociedad.  El elemento que hizo posible el desarrollo comercial de todos estos sistemas fue la válvula de vacío y en particular el triodo: Invented in 1904 by John Ambrose Fleming, vacuum tubes were a basic component for electronics throughout the first half of the twentieth century, which saw the diffusion of radio, television, radar, sound reinforcement, sound recording and reproduction, large telephone networks, analog and digital computers, and industrial process control. Although some applications had counterparts using earlier technologies such as the spark gap transmitter or mechanical computers, it was the invention of the vacuum tube that made these technologies widespread and practical.

However actual amplification by a vacuum tube only became practical with Lee De Forest‘s 1907 invention of the three-terminal “audion” tube, a crude form of what was to become the triode.[11] Being essentially the first electronic amplifier,[12]such tubes were instrumental in long-distance telephony (such as the first coast-to-coast telephone line in the US) andpublic address systems, and introduced a far superior and versatile technology for use in radio transmitters and receivers. The electronics revolution of the 20th century arguably began with the invention of the triode vacuum tube.

¿ Se percibía ya el fuerte impacto de estas tecnologías durante el periodo de la Primera Globalizacion (Segunda revolución Industrial) ?. Scientific American nos informa al respecto.

Sorprendentemente ya aparece en la lista de lo que se consideraba mayores invenciones una calculating machine.   ¿ A que se referían ?.

Fin de nota.

2. El primer libro sobre teoría de grafos se publicó precisamente en 1936 por el austriaco Denes Konig. El lector puede encontrarlo aquí, en PDF en alemán.  ¿ Relaciona ya este objeto con las ciencias computacionales o el tratamiento es puramente de matematicas discretas ?.  No hablamos este idioma, no lo sabemos.

Nota. Si he visto con agrado que ya en este primer libro aparece como problema seminal el de los recorridos hamiltonianos y aparece un apartado sobre los grafos de Cayley. Fin de nota.

El segundo libro sobre teoría de grafos es del francés Claude Berge, de 1958. Ya posterior a la II GM: Théorie des graphes et ses applications, Wiley, 1958, trans. English, Russian, Spanish, Romanian, Chinese. English translation: The Theory of Graphs and its Applications, Wiley, 1964.

En 1958 a industria de los computadores digitales ya está asentada, aunque no es para nada de consumo masivo.

Un autor que se sitúa entre Konig y Berge (o contemporáneo de este último) y que publicó activamente en teoría de grafos e hizo esfuerzos para darle un barniz más de matemáticas puras fue el británico Tutte.  En este aspecto desarrolló todo su trabajo tras la II GM y ya en Canadá.

La historia anterior de la teoría de grafos, desde la publicación de lo que se supone es el primer artículo al respecto, el de Euler sobre los puentes de Koenisberg, hasta 1936 se puede leer en el siguiente magistral libro:

Graph Theory, 1736-1936. Escrito por Norman Biggs, E. Keith Lloyd, Robin J. Wilson, publicado por primera vez en 1936 con varias ediciones. Contiene algunos de los artículos clásicos de esta teoría, que nace muy vinculada a las matemáticas recreativas.

Realmente hasta que se desarrollaron plenamente las ciencias computacionales y sus potentes aplicaciones que hoy están impactando ya de manera definitiva, las matemáticas discretas siempre han sido, por decirlo de alguna manera la cenicienta de las matemáticas, al trabajar con problema finitos. Los matemáticos “auténticos” las despreciaban. Hoy esto está cambiando aunque entiendo que sigue habiendo inercias.

Con lo que hemos descrito vemos que una de las grandes diferencias entre la primera y segunda globalización, aunque no la única, es precisamente la existencia  en la segunda de máquinas computacionales universales.

Nota final. Los economistas, para consolar a los neo-luditas contrarios al imperialismo computacional sobre el que tanto hemos hablado en el blog, suelen citar a la falacia de los trabajos finitos.

Creo que aludir a esta falacia en el contexto actual, es no comprender bien el problema, la novedad de la situación actual con respecto a situaciones anteriores parecidas: ahora, o en breve, las máquinas pueden o podrán hacer cualquiera de los infinitos trabajos mejor (de manera más eficiente) que el hombre y de manera más económica.

Esto según como se mire puede ser una problema o una bendición: la Sociedad del Ocio. No sabemos si cuando llegue ésta nos dedicaremos todos a rezar, como San Isidro. Esto nos inspira unas breves reflexiones improvisadas. Una de las pre-condiciones de la Sociedad del ocio es el fin del avance científico y tecnológico (luego hablamos más sobre esto). Y en una sociedad sin posibilidad de avance científico o tecnológico, desaparece o se atenúa el ánimo de lucro, el deseo material. Por lo tanto, entendemos que la Sociedad del Ocio será más  bien espiritual, aunque no necesariamente de corte religioso tal  y como entendemos la religión hoy.

De momento todo esto está siendo al menos un aliciente para el desarrollo de la teoría de la hacienda pública: algunos proponen que los robots paguen impuestos. Como ya hemos comentado en otras entradas, nosotros no vemos tan claro este tema: ¿ pq entonces no los han pagado antes (las máquinas existen desde hace siglos) ?. ¿ Puede ser pq los pagaban sus dueños vía impuesto sobre beneficios ?. El problema real es más que de exceso de oferta de trabajo es de demanda de bienes, de consumo. Están relacionados, claro.

Como la Sociedad del Ocio no está aquí todavía, y pese a los miedos de Hawking, como que yo sepa todavía no se ha inventado el robot científico (¿ o es que éste científico tiene miedo precisamente a que se le adelante un robot en el descubrimiento de la TOE ? :-); pese a la sonrisa, esta pregunta no es una coña: o tiene este miedo realmente o su posición me parece incoherente; hala, otro :-)) a nosotros nos va a tocar trabajar muy duro en los próximos días para rematar un tema que tenemos pendiente:  hacer una síntesis digerible por abuelas de nuestro resultado.

Aunque desde hace años no pensamos  en estos temas, unas breves reflexiones que se nos ocurren sobre la marcha, sobre otros miedos actuales a los robots (al margen del miedo a que sustituyan a los trabajadores): para que sean más eficientes y económicos, entendemos que no pueden ser tan universales como el hombre. Por ejemplo, la mayoría no se moverán. Y los que se muevan será para ejecutar tareas muy especializadas. Y si no son tan universales, no tienen pq ser peligrosos. Sólo serán una herramienta más. Sofisticada, pero una herramienta al fin y al cabo. Y como con todas las herramientas, lo más peligroso va a ser el uso que hagan de ellas los hombres.

. Fin de nota final.

Anuncios

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: