sábado, 13 de junio de 2015

Vida y Obra de Chomsky: Gramaticas transformacionales


Infancia:

Avram Noam Chomsky nació el día 7 de diciembre de 1928 en Filadelfia (Pensilvania, Estados Unidos). Hijo del doctor William Chomsky (conocido gramático y estudioso de la lengua hebrea) y de Elsie Simonofsky (maestra de hebreo), de origen judío-ucraniano; residía en una población de fuerte carácter antisemita, de irlandeses y alemanes católicos. Siendo niño le tocó vivir una época de gran dureza: la gran Depresión, que se inició con el crack de la Bolsa en 1929 y persistió hasta la Segunda Guerra Mundial. Su primer escrito consistió en un artículo editorial para el periódico de la escuela sobre la caída de Barcelona. A partir de los doce años, Chomsky asistió a una escuela progresista experimental sin grados, donde no existía ninguna clase de competencia escolar. En esta época escribió una historia relacionada con la Guerra Civil Española lamentándose ante la victoria del fascismo.

Universidades:

uEstudió en la Universidad de Pensilvania desde 1945. Para poder costearse los estudios universitarios, tuvo que seguir viviendo bajo el techo de sus padres; lo cual lo obligaba a viajar varias horas por día, y a trabajar como profesor de lengua hebrea por la tarde, por la noche y los domingos. Al poco tiempo su entusiasmo por la universidad se extinguió y perdió el interés por cualquier materia, de forma que a los dos años de su inicio abandonó la facultad. Continuó participando en la política izquierdista y se comprometió de forma muy viva con el sionismo. Por sus intereses políticos, Chomsky conoció a Zellig Harris, un muy ilustre profesor de lingüística de la Universidad de Pensilvania (también inmigrante judío-ucraniano y promotor del primer departamento especializado en el ámbito de la lingüística en Norteamérica).

uPor indicación del mismo, Chomsky retomó las clases centrándose en filosofía y matemática; materias que nunca había estudiado, pero que le atrajeron en sumo grado. También por influencia de Harris, regresó a la facultad y se instruyó en la carrera de lingüística. Uno de sus mentores fue el filósofo Nelson Goodman, quien más tarde los presentaría en la Society of Fellows de Harvard. En 1953, siendo miembro de esta sociedad, Chomsky marchó a Israel y vivió algunos meses en un kibbutz. Sin embargo, se sentía molesto con los umbrales racistas y conformistas que delimitaban la institución israelí. Finalmente se situó en la Universidad de Harvard, donde finalizó su doctorado en 1955.

Tesis doctoral:

En su tesis doctoral comenzó a desplegar de sus planteamientos en el ámbito de la lingüística, desarrollándolas posteriormente en su obra Estructuras sintácticas, su labor más conocida en este campo. Estas propuestas lingüísticas han cambiado la perspectiva generalizada de muchos elementos elementales en la investigación del lenguaje humano y han sido reflejados en la teoría de la gramática transformacional y generativa.

Pensamiento:

uSe alza como profesor del Massachusetts Institute of Technology(MIT) desde 1955, donde en el año 1961 se alza con la cátedra Ferrari P. Ward de Lenguaje Moderno y Lingüística en el Departamento de Lingüística y Filosofía del MIT. Integrante de la izquierda intelectual norteamericana, que algunos han calificado como socialismo libertario, destacó por su oposición a la guerra de Vietnam, dentro de una actitud antisistema que ha mantenido a lo largo de toda su trayectoria profesional y política. Sin embargo, un pensamiento no consistió únicamente en palabra, sino que opuso resistencia activa a la guerra a pesar de saber que era muy probable que lo encarcelaran. Sus críticas a la movilización hicieron tambalear su distinguida posición académica.

Ha desarrollado su trabajo académico e intelectual a lo largo de medio siglo y abarca los campos de la lingüística moderna, comunicación, política, economía, filosofía contemporánea, psicología cognitiva y sociología generando mucha controversia. Se describe a sí mismo como socialista libertario, librepensador y simpatizante del anarcosindicalismo (entra como miembro en el sindicato IWW). Su imagen es muy acreditada en el sector de la izquierda radical estadounidense y en Europa, donde sus obras, conferencias, artículos y ensayos políticos se reimprimen y venden constantemente.

uEn lo referente a los medios de comunicación de masas norteamericanos, Chomsky los define como herramientas estratégicas de poder, subordinados o dependientes de las grandes entidades económicas y de los mandos políticos que se encuentren en el poder al ser empleados como principales propulsores del incremento de la hegemonía estadounidense y su influencia internacional. En sus obras, analiza a conciencia las censuras visibles e invisibles existentes en los medios de masas norteamericanos y las debilidades de la democracia en el sector de la comunicación y de la información.

Obras importantes:

u1955 Logical Structure of Linguistic Theory (Tesis doctoral, inédita hasta 1975).
u1957 Estructuras sintácticas.
u1965 Aspectos de la teoría de la sintaxis.
u1968 El lenguaje y el entendimiento.
u1966 Lingüística cartesiana.
u1975 Reflexiones sobre el lenguaje.
u1980 Reglas y representaciones.
u1981 Lectures on Government and Binding: The Pisa Lectures.
u1986 Barreras.
u1986 El conocimiento del lenguaje, su naturaleza, origen y uso.
u1995 El programa minimalista.

Gramatica transformacional:

Gramática transformacional es una expresión que designa al tipo de gramática generativa que utiliza reglas transformacionales u otros mecanismos para representar el desplazamiento de constituyentes y otros fenómenos del lenguaje natural.
Una gramática generativa, en el sentido en que Noam Chomsky denomina el término, es un sistema de reglas formalizado con precisión matemática que genera las oraciones gramaticales de la lengua que describe o caracteriza, y asigna a cada oración una descripción estructural, o análisis gramatical. Fue perfeccionada por Chomsky, quien además le dio una base teórica diferente.

Estructura superficial y profunda:

uLa gramática generativo-transformacional de Chomsky muestra que cuando analizamos varias oraciones aparentemente distintas podemos encontrar la misma estructura, o que oraciones aparentemente iguales poseen distintas estructuras. Ello sugiere que en el lenguaje cabe distinguir dos niveles: el nivel de la estructura superficial o del enunciado tal y como lo proferimos -lo relativo al uso o ejecución-, y el nivel o estructura profunda, que se muestra al análisis lingüístico, y a partir del cual, y mediante transformaciones que siguen reglas, el sujeto genera las estructuras superficiales -nivel relativo a la competencia-.

uLa estructura profunda es la estructura subyacente de una oración que transmite el significado de la misma.
uLa estructura superficial hace referencia a la disposición superficial de los constituyentes y refleja el orden en que se pronuncian las palabras.

Reglas transformacionales:

En la gramática transformacional, la derivación completa de una oración es un proceso que se divide en dos partes:
uEn primer lugar se utilizan las reglas de la estructura sintagmática para generar la estructura subyacente que es la estructura profunda.
uEn segundo lugar se aplica una secuencia de reglas transformacionales a la estructura profunda y a las intermedias, generando así la estructura superficial de la oración.

Forma logica y fonetica:

uAunque las transformaciones continúan siendo importantes para las teorías actuales defendidas por Chomsky, él ya no defiende la idea original de las estructuras profunda y superficial. En un principio, se introdujeron dos niveles adicionales de representación: la Forma Lógica (LF) y la Forma Fonética (PF):
u Forma Lógica : Es la representación de su contenido y sintaxis usando las herramientas de la lógica, en particular el simbolismo del cálculo proposicional y el cálculo de predicados. Oraciones distintas pueden ser representaciones de la misma proposición, por ejemplo:

María ama a Juan
Juan es amado por María

  Forma fonética: La fonética se ocupa de la descripción del sonido (análisis descriptivo) Supone un nivel de abstracción que no trabaja con unidades físicas (sonidos), sino con entidades abstractas (fonemas).

Minimalismo:

uEn medio de la evolución histórica de la gramática generativa, en los años noventa toma una nueva linea investigativa: el Programa Minimalista.
uSe considera un programa y no una teoría debido a que pretende ser un modo de investigación mas flexible aprovechando la idea de minimalismo.
uProporciona el marco conceptual que guía el desarrollo de la teoría lingüística generativa, pero no ofrece soluciones específicas a problemas técnicos ya conocidos ni explicaciones sobre fenómenos lingüísticos observados. Interesa no solo conocer qué son exactamente las propiedades del lenguaje, sino también la de por qué son como son.
uEl concepto de minimalismo apela a la idea de que la capacidad del lenguaje en los humanos muestra indicios de estar constituida según un diseño óptimo y una exquisita organización, que parecen indicar el funcionamiento interno de unas leyes computacionales muy sencillas y generales en un determinado órgano mental.
uEste programa trabaja sobre la hipótesis de que la Gramática Universal constituye un diseño perfecto, sólo contiene lo estrictamente necesario para cubrir nuestras necesidades conceptuales, físicas y biológicas.
Representacion matematica:

En relación con el estudio matemático de la gramática, un rasgo significativo de las gramáticas transformacionales es que son más poderosas que las gramáticas libres de contexto. Esta idea fue formulada por Noam Chomsky en la Jerarquía de Chomsky: En 1959 Noam Chomsky clasifico las gramáticas en cuatro familias. Las gramáticas no restringidas, sensibles al contexto, independientes del contexto y las gramáticas regulares que se conocen como gramáticas de tipo cero, uno, dos y tres respectivamente. Los lenguajes que resultan de dichas gramáticas también se identifican con lenguajes de tipo cero, uno, dos y tres. A esta jerarquía de lenguaje se le conoce como la jerarquía de Chomsky.


u

martes, 9 de junio de 2015

El Problema del Castor Laborioso

INTRODUCCIÓN


El problema del Castor Laborioso o The Busy Beaver Game es un juego fácil de entender pero difícil de jugar. El juego fue propuesto por Tibor Radó y está pensado para máquinas de Turing.

No es un simple juego para entretenerse. Una solución general al problema implicaría un paso importante en el área de la computación.


Tibor Radó


Tibor Radó nació en Budapest y entre 1913 y 1915 asistió al Instituto Politécnico donde estudió ingeniería civil. En la primera guerra mundial él se convirtió en el primer lugarteniente de la armada húngara y fue capturado en el frente ruso. Escapó del campo de prisioneros de Siberia y, viajando miles de millas atravesando el Antártico, logró regresar a Hungaria.
Él consiguió un doctorado en la universidad Franz Joseph en 1923. Estuvo un pequeño tiempo como profesor en la universidad y apoyó en el campo de la investigación junto a la fundación Rockefeller en Alemania. 

En 1929 se trasladó a los Estados Unidos y dio una conferencia en la universidad de Harvard y en el Instituto Rice antes de obtener un puesto en el departamento de matemáticas en la universidad estatal de Ohio en 1930. 
En 1935 se le concedió la ciudadanía Americana. Durante la segunda guerra mundial fue un científico del gobierno de los Estados Unidos, interrumpiendo su carrera académica. Se convirtió en presidente del departamento de matemáticas de la universidad estatal de Ohio en 1948.

En la década de 1920 demostró que las superficies tenían una triangulación esencial única. En 1933 publicó "On the Problem of Plateau" (Sobre el problema de Plateau) y donde dio una solución al problema de Plateau, y en 1935, "Subharmonic Functions" (Funciones subarmónicas). Su trabajo se centró en la ciencia informática en la última década de su vida.

En Mayo de 1962 publicó uno de sus más famosos artículos en el periódico "Bell System Technical": "the busy beaver funciton" (el juego del castor laborioso) y la no computabilidad recogidos en su publicación "On Non-Computable Functions" (Funciones no computables).
Murió en Nueva Smyrna Beach, Florida.



Juego


Condiciones del juego:


  • Utilizar una máquina de Turing para resolverlo.
  • La cinta puede tomar 2 valores {0,1} o {B,1}.
  • La cinta debe estar llena de blancos o 0s.
  • La máquina puede desplazarse en cualquier dirección sin restricciones (es válido el desplazamiento a la izquierda desde la primera posición).

Objetivo:


  • Crear el mayor número de 1s posible.
  • La máquina debe detenerse.

La parte variable del problema es el número de estados que podemos utilizar.

Definimos la función P: N => N donde el valor de entrada es el número de estados y el de salida el número de 1s máximo que puede generar la máquina de Turing con los estados dados.

El estado final está excluido por lo que para N = 1 la máquina de Turing tiene los estados q0 y qf pero qf no se utiliza ya que en el momento que la máquina de Turing llega a este estado se para.


Este juego no está aún resuelto, es decir, no se conoce la función descrita antes.



Existen soluciónes para un número de estados menor a 5 y cotas inferiores para un número de estados menor a 7.

También utilizaremos la función S igual a P sólo que ésta devuelve el número de pasos realizados por la máquina.

Estas son los valores exactos y las cotas inferiores:

N = 1, P = 1, S = 1
N = 2, P = 4, S = 6
N = 3, P = 6, S = 21
N = 4, P = 13, S = 107
N = 5, P = 4098, S = 47,176,870
N = 6, P = 4,6x10^1439, S = 2,5x10^2879

Como podemos observar es un crecimiento muy difícil de calcular.

Si colocásemos la cinta y por cada paso de la máquina la fuésemos clonando desplazándola hacia abajo quedarían las siguientes formas:

Para un estado:
La cinta queda con un sólo uno.

Para dos estados:


Para tres estados:


Para cuatro estados:


Aplicaciones


Sabemos que una máquina puede ser representada como una máquina de Turing de N estados donde la cinta es la memoria y la memoria sólo puede tener 1s y 0s. En máquina de Turing sería 1s y blancos.

Sabemos que una máquina de Turing con N estados no puede realizar más de S(N) pasos ya que, si los realizase, querría decir que habría entrado en un bucle infinito.

Sabiendo lo anterior podemos saber si una máquina parará o no ejecutándola ya que si la máquina en algún momento realiza más de S(N) pasos querrá decir que ha entrado en un bucle infinito.

Bibliografía



Trabajo realizado por David Domínguez Barbero.

viernes, 5 de junio de 2015

Concepto del algoritmo: La vida de Al-Khwarizmi



Introducción


Esta exposición trata sobre el origen de los algoritmos tal y como hoy los conocemos, para empezar hay que mencionar la definición actual de algoritmo. Conocemos los algoritmos como un conjunto de instrucciones simples, ordenadas y claras que mediante pasos sucesivos parten de un estado inicial y transitan por otros estados hasta llegar al estado final en el que se obtiene un resultado.

En resumen, un algoritmo es cualquier cosa que funcione paso a paso, donde cada paso se pueda describir sin ambigüedad y sin hacer referencia a una computadora en particular, y además tiene un límite fijo en cuanto a la cantidad de datos que se pueden leer/escribir en un solo paso.
 
La estructura de todo algoritmo contiene los siguientes parámetros:
  • Conjunto datos iniciales
  • Conjunto de resultados posibles
  • Conjunto de resultados intermedios
  • Regla de inicio
  • Regla del proceso directo
  • Regla de finalización
  • Regla de obtención del resultado

Vida de Al-Khwarizmi



Hacia 815 al-Mamun, séptimo califa Abásida, hijo de Harún al-Rashid, fundó en su capital, Bagdad, la Casa de la sabiduría (Bayt al-Hikma), una institución de investigación y traducción que algunos han comparado con la Biblioteca de Alejandría. En ella se tradujeron al árabe obras científicas y filosóficas griegas e indias donde además trabajo junto con otros científicos. Dos de sus obras, sus tratados de álgebra y astronomía, están dedicadas al propio califa.

Al-Khwarizmi fue bibliotecario en la corte del califa al-Mamun y astrónomo en el observatorio de Bagdad. Sus trabajos de álgebra, aritmética y tablas astronómicas adelantaron enormemente el pensamiento matemático. 

Aunque los algoritmos datan de tiempos babilónicos y los griegos diseñaron algoritmos aún famosos, fue Al-Khwarizmi el primero que diseñó algoritmos pensando en su eficiencia, en particular, para el cálculo de raíces de ecuaciones. Gracias a él, la matemática moderna usa el sistema numérico actual, proveniente de la India. Además las palabras guarismo (cifra, número) y algoritmo provienen de su nombre, que en árabe significa, "el de Khorezm" por su lugar de origen.

La mayoría de sus diez obras son conocidas en forma indirecta o por traducciones hechas más tarde al latín (muchas de ellas en Toledo) y de algunas sólo se conoce el título. Al-Khorezmi fue un recopilador de conocimiento de los griegos y de la India, principalmente matemáticas, pero también astronomía (incluyendo el calendario Judío), astrología, geografía e historia. Su trabajo más conocido y usado fueron sus Tablas Astronómicas, basadas en la astronomía india. Incluyen algoritmos para calcular fechas y las primeras tablas conocidas de las funciones trigonométricas seno y cotangente. Lo más increíble es que no usó los números negativos (que aún no se conocían), ni el sistema decimal ni fracciones, aunque sí el concepto del cero. Su Aritmética, traducida al latín como "Algoritmi de número Indorum" introduce el sistema numérico indio (sólo conocido por los árabes unos 50 años antes) y los algoritmos para calcular con él. 

Su obra al-jebr w'al-muqabalah fue traducida al latín, por primera vez, en la Escuela de Traductores de Toledo y tuvo mucha influencia en las matemáticas de la época. La traducción del título de la obra era complicada, por lo que los traductores optaron por latinizar el título, convirtiéndolo en aljeber que acabó derivando en la actual álgebra.

Sus libros son intuitivos y prácticos y su principal contribución fue simplificar las matemáticas a un nivel entendible por no expertos. En particular muestran las ventajas de usar el sistema decimal indio, un atrevimiento para su época, dado lo tradicional de la cultura árabe. La exposición clara de cómo calcular de una manera sistemática a través de algoritmos diseñados para ser usados con algún tipo de dispositivo mecánico similar a un ábaco, más que con lápiz y papel, muestra la intuición y el poder de abstracción de Al-Khorezmi. Hasta se preocupaba de reducir el número de operaciones necesarias en cada cálculo. Por esta razón, aunque no haya sido él el inventor del primer algoritmo, merece que este concepto esté asociado a su nombre. Al-Khorezmi fue sin duda el primer pensador algorítmico.

De su aritmética, posiblemente denominada originalmente "Kitab al-Jam'a wal-Tafreeq bil Hisab al-Hindi", sólo conservamos la versión latina, Algoritmi de Numero Indorum, del siglo XII. En esta obra describe con detalle el sistema hindú de numeración posicional en base 10 y la manera de para hacer cálculos con él. Se sabe que había un método para hallar raíces cuadradas en la versión árabe, pero no aparece en la versión latina. Fue esencial para la introducción de este sistema de numeración en el mundo árabe y posteriormente en Europa. El que nos haya llegado a través de los árabes hace que le llamemos habitualmente sistema de numeración árabe, cuando deberíamos llamarlo indo-arábigo. Posiblemente fuese el primero en utilizar el cero como una cifra.

Su tratado de álgebra es una introducción compacta al cálculo, usando reglas para completar y reducir ecuaciones. Además de sistematizar la resolución de ecuaciones cuadráticas, también trata geometría, cálculos comerciales y de herencias. Quizás éste es el libro árabe más antiguo conocido y parte de su título "Kitab al-jabr wa'l-muqabala" da origen a la palabra álgebra. Los términos al-jabr y al-muqabala se utilizan para denominar lo que nosotros entendemos por transposición de términos y posterior simplificación de términos semejantes con coeficientes negativos y positivos. Una posible traducción del título sería "El libro de restaurar e igualar" o "El arte de resolver ecuaciones". La palabra algebrista se utiliza también en "El Quijote" con un significado ya en desuso, pero que hace referencia a ese significado de restauración o recomposición. En el diccionario de la Real Academia Española de la Lengua podemos leer: "Algebrista, 2. (desusado) Cirujano dedicado especialmente a la curación de dislocaciones de huesos."

Obras 

El libro de álgebra. Traducciones y ediciones.


Del libro de álgebra de Al-Khwārizmī sí que se conservan manuscritos árabes, pero eso no significa que el establecimiento de un texto lo más cercano al original posible no esté exento de problemas. Hasta hace poco tiempo la edición del álgebra de Al-Khwārizmī de que se disponía era la que hizo Frederic Rosen en 1831, acompañada de su traducción al inglés  Rosen, 1831). Esa edición estaba hecha a partir de un único manuscrito que se conserva en la Bodleyan Library de Oxford (Hunt. 212, fol. 1v-54r), que es de 1342, es decir, más de cinco siglos posterior a la fecha de redacción por parte de Al-Khwārizmī.

Aunque el manuscrito está en muy buen estado y el copista hizo un trabajo cuidadoso, con el texto nítido en tinta negra y los títulos y las figuras en tinta roja, y con la escritura vocalizada a menudo, e incluso indicó el día exacto en que acabó la copia (19 Muharram del 743 de la Hégira, es decir, 24 de junio de 1342), no cupo nunca duda de que el tiempo transcurrido desde el original tenía que haber producido cambios, pérdidas o incorporaciones por su paso por múltiples manos de copistas. El libro fue editado de nuevo en Egipto en 1939 por Alī Mustafā Masharrafa y Muhammad Mursī Ahmad en árabe a partir del mismo manuscrito, en una edición ligeramente más cuidadosa que la realizada por Rosen (Masharrafa y Ahmad, que apenas modificaba la situación).

A falta de manuscritos árabes más antiguos, los historiadores recurrieron al estudio de las traducciones latinas medievales, una de las cuales resultó ser especialmente buena. En efecto, se conservan tres traducciones latinas diferentes del álgebra de Al-Khwārizmī.  


Texto de una edición árabe de su álgebra (El Cairo, 1968) donde se explica como resolver la ecuación x^2 + 10x = 39

Otras obras

 


Kitāb al-Mukhtasar fī hisāb al-jabr wa’l-muqābala (Libro conciso de cálculo de restauración y oposición).
El libro de álgebra. Según el prólogo debió escribirlo entre 813 y 833, ya que se lo dedica al califa Al-Ma’mūn, y ésos son los años en que fue califa.

Kitāb al-hisāb al-cadad al-hindī (Libro del cálculo con los números hindúes).
Escrito también después de 813. El libro en que explica el sistema de numeración hindú y el cálculo aritmético con él. No se conserva ningún manuscrito árabe de este libro.

Kitāb al-jamc wa’t-tafrīq (Libro de la reunión y de la separación).
Perdido. La opinión de Djebbar (2005) y de Rashed (2007) es que debía contener un cálculo aritmético anterior a la introducción del cálculo hindú.

Kitāb sūrat al-ard (Libro de la configuración de la tierra).
Escrito alrededor de 817. Se conserva una copia árabe en la Biblioteca de la Universidad de Estrasburgo, y una traducción latina en la Biblioteca Nacional de Madrid. En esta geografía, Al-Khwārizmī sigue la teoría de los siete climas, y usa datos de Ptolomeo, pero otros que no están en el Almagesto. Es probable que haya participado en la expedición organizada por Al-Ma’mūn para comprobar los datos del libro de Ptolomeo. En ninguna de las copias hay mapas, y se especula sobre si Al-Khwārizmī incluiría un mapa del mundo. 

Istikhrāj ta’rīkh al-Yahūd (Determinación del calendario judío).
En este libro, escrito alrededor de 824 y descubierto alrededor de 1940, Al-Khwārizmī muestra conocer también el mundo hebreo, ya que describe las reglas de cálculo de las longitudes medias del Sol y de la Luna a  partir del calendario judío.

Zīj as-Sindhind (Tablas hindúes)
Escrito después de 813. El libro más importante de astronomía de Al-Khwārizmī. Además escribió otros menos conocidos, perdidos o redescubiertos recientemente. 

Kitāb cAmal al-asturlāb (Libro sobre la realización del astrolabio).
No se conserva ninguna copia. Mencionado por Al-Nadīm, en su Kitāb al-Fihrist. En este libro, publicado en 938, al-Nadīm pretendió recoger en un índice todos los libros escritos en árabe hasta ese momento.

Kitāb al-cAmal bi’l-asturlāb (Libro sobre la utilización del astrolabio).
Identificado por unos fragmentos reproducidos por el astrónomo del siglo IX Al-Farghānī

Kitāb al-Tārīkh.
Mencionado también por Al-Nadīm, se trata de un libro de historia, escrito después de 826.



Bibliografia