Recursion  /  Recursividad

www.fgalindosoria.com/informatica/properties/recursion/

 

INFORMATICS PROPERTIES   /  PROPIEDADES INFORMÁTICAS

Dimension     Density  and Frecuency    Symmetry    Recursion    Form

Dimensión    Densidad y Frecuencia     Simetría     Recursividad    Forma

 

Fernando Galindo Soria

English (www.fgalindosoria.com/en/ )       Español (www.fgalindosoria.com )

fgalindo@ipn.mx

Red de Desarrollo      REDI

 

Creación de la página www    Tenayuca, Ciudad de México 16 de Abril del 2017

Últimas actualizaciones 16 de Abril del 2017

 

 

La recursividad es una propiedad fundamental de la Informática, que consiste en que algo se define o describe en términos de si mismo.

 

Fenómenos o procesos recursivos son, por ejemplo; la Invariancia Gauge (Invariancia bajo cambio de Escala), los Fractales, las Leyes de Potencia (Power Laws), el Empotramiento etc.

 

Algunos términos relacionados con la Recursividad

Iteratividad, Retroalimentación, Convolución, Sinécdoque (designar la parte por el todo o viceversa.), Auto semejanza, …

 

 

ARTÍCULOS

 

 

 

Recursividad

Fernando Galindo Soria, Tenayuca, Ciudad de México 16 de Abril del 2017

Contenido:

Conceptos Generales

Fenómenos o procesos recursivos

Invariancia Gauge (Invariancia bajo cambio de Escala), Fractales, Leyes de Potencia (Power Laws), Empotramiento.

Iteratividad, retroalimentación, convolución, autosemejanza, synecdoche

Recursividad e iteración

Recursividad y empotramiento

Empotramiento recursivo.

Página html    documento en Word   documento pdf

 

Manejo de la Recursividad mediante Paso de Control y Paso de Parámetros

Fernando Galindo Soria, Ciudad de México, 1974 – 1975

Paso de Control y Paso de Parámetros

Manejo del PC (Program Counter). (Tema de la Arquitectura de Computadoras)

Manejo de saltos (Go To). (Tema de los Compiladores)

Manejo de Interrupciones. (Tema de los Sistemas Operativos)

Manejo de Rutinas. (Tema de los Compiladores)

Manejo de la Recursividad. (Tema de las Matemáticas, programación)

Página html    documento en Word   documento pdf

 

 

 

 

LIGAS

 

Algunas Propiedades Matemáticas de los Sistemas Lingüísticos

Fernando Galindo Soria  Septiembre de 1992

Capitulo 6) Recursividad Lingüística.

http://www.fgalindosoria.com/linguisticamatematica/propiedades_matematicas_sistemas_linguisticos/prop_mate_sistemas_linguisticos.pdf

 

http://www.fgalindosoria.com/linguisticamatematica/propiedades_matematicas_sistemas_linguisticos/prop_mate_sistemas_linguisticos.htm

 

 

*************************************

Notas Acerca de los Universos Recursivos, Notas para el análisis.

Fernando Galindo Soria, 3 de Agosto del 2005

http://www.fgalindosoria.com/transfinitoydinamicadimensional/universosrecursivos/universosrecursivos.pdf

 

http://www.fgalindosoria.com/transfinitoydinamicadimensional/universosrecursivos/universosrecursivos.htm

 

 

*************************************

El viaje en el tiempo es un proceso recursivo

http://www.fgalindosoria.com/notas_de_investigacion/el_viaje_en_el_tiempo_es_un_proceso_recursivo/

 

 

***********************************************************************

De Fractales y Otros Bichos: La Matemática de la Naturaleza

“Como primer punto se introduce el concepto de Fractal y se describen sus propiedades de autosimilaridad y de dimensión fraccionaria, a continuación se da una introducción a la Teoría del Caos y se observa que el comportamiento de un sistema caótico tiene una estructura fractal. Como siguiente punto se introduce el concepto de Agregación, que es uno de los mecanismos fundamentales para construir estructuras fractales y se observa que si un fenómeno de agregación se lleva al límite se termina con un cristal, de donde se postula que un fractal y un cristal son casos particulares de un fenómeno general.”

www.fgalindosoria.com/fractales_y_bichos/fractales_bichos/fractales_y_otros_bichos.pdf

 

www.fgalindosoria.com/fractales_y_bichos/fractales_bichos/fractales_y_otros_bichos.htm

 

 

*************************************

En esta página se presenta una serie de artículos desarrollados sobre una

Ecuación General de la Naturaleza  S-->e*S*

“Una ecuación basada en la Lingüística Matemática y los fractales, con la cual se puede representar la estructura de múltiples elementos de la naturaleza, incluyendo árboles, nubes, estrellas, montañas, caracoles y ríos y que proponemos como una de las ecuaciones fundamentales de la naturaleza.”

http://www.fgalindosoria.com/ecuaciondelanaturaleza/

 

 

Aplicación de la Lingüística Matemática a la Generación de Paisajes

Fernando Galindo Soria , UPIICSA IPN, México, Diciembre de 1992

http://www.fgalindosoria.com/ecuaciondelanaturaleza/linguistica_matematica_generacion_paisajes/paisaje1.pdf

 

http://www.fgalindosoria.com/ecuaciondelanaturaleza/linguistica_matematica_generacion_paisajes/paisaje1.htm

 

 

paisajes a1 ecuación de la naturaleza S → e*S*

https://www.youtube.com/watch?v=PqxuhoVeVL4

 

paisajes 2c1 ecuación de la naturaleza S → e*S*

https://www.youtube.com/watch?v=ssH8QKVR0Y0

 

paisajes 2c2 ecuación de la naturaleza S → e*S*

https://www.youtube.com/watch?v=jazOMZ8wrWU

 

 

Fractales de dragón en 3D  basados en la Ecuación de la Naturaleza  S->e*S*

Ciudad de México     Octubre de 1996

http://www.fgalindosoria.com/ecuaciondelanaturaleza/dragon/

 

 

Uso de la recursividad (Ecuación de la naturaleza) para modelar sistemas que se autoreproducen   fgs   abril 2000

 

AUTOREPRODUCCIÓN

Dibuja árboles y flores que se autoreproducen

Fernando Galindo Soria Tenayuca, Ciudad de México, Enero del 2002
 Generados Mediante Una Ecuación de la Naturaleza S → e*S*

https://www.youtube.com/watch?v=SKkaDInGI-A

 

 

***********************************************************************

Fractal Symmetry and Power Law Distributions,  Simetria Fractal y Leyes de Potencias

simetría interna, simetría en profundidad

Recursivity / Recursividad,     Invariant Fractal / Invariancia Fractal,

similaridad, autosimilaridad,  invarianza bajo cambios de escala, invariancia de escala, escala, conectividad

http://www.fgalindosoria.com/informatica/properties/symmetry/fractal_symmetry.htm

 

 

Fractal Space-Time  /  Espacio Tiempo Fractal

http://www.fgalindosoria.com/informatica/properties/symmetry/fractal_space_time.htm

 

 

Gauge Invariance  /  Invariancia Gauge

www.fgalindosoria.com/informatica/properties/symmetry/gauge_invariance.htm

 

“invariancia gauge, ...una traducción libre del alemán al inglés, que significa calibre, norma o escala. Sus ecuaciones debían ser invariantes frente a un cambio de escala en las distancias y los tiempos, diferente para cada punto del espacio tiempo.””

http://labellateoria.blogspot.com/2007/01/una-clave-para-la-gran-unificacin-la.html

 

 

***********************************************************************

Sistemas Evolutivos, Afectivos y Conscientes

Seminario de Investigación

www.fgalindosoria.com/eac/2017/

 

 

Sistemas Conscientes  SCon

Diapositiva 71 a 76, 102, 123 a 132

http://www.fgalindosoria.com/eac/2017/sconscientes17_a.pdf

 

http://www.fgalindosoria.com/eac/2017/sconscientes17_a.pptx

 

 

Automatic Music Composition with Simple Probabilistic Generative Grammars.

Horacio Alberto García Salas, Alexander Gelbukh, Hiram Calvo, and Fernando Galindo Soria, Polibits (44) 2011

http://www.scielo.org.mx/pdf/poli/n44/n44a10.pdf

http://www.scielo.org.mx/scielo.php?script=sci_arttext&pid=S1870-90442011000200010

 

Horacio Alberto García Salas, “Modelo Generativo de Composición Melódica con Expresividad”

Tesis para obtener el Grado de Doctor en Ciencias de la Computación, Laboratorio de Procesamiento de Lenguaje Natural, Centro de Investigación en Computación CIC, Instituto Politécnico Nacional IPN, México, Mayo del 2012

http://www.fgalindosoria.com/informaticos/investigadores/Itztli_(Horacio_Alberto)_Garcia_Salas/PhD/Horacio_Alberto_Garcia_Salas_PhD.pdf

 

 

 

 

ANEXOS

 

***********************************************************************

Empotramiento, Embebido

Es una propiedad informática donde un objeto se encuentra dentro de otro, por ejemplo, las estructuras de paréntesis, una caja dentro de otra, un juguete en una caja, una frase dentro de otra frase, etc.

 

Cajas

 

Contenido o espacio ocupado y frontera

Forma, tamaño, propiedades.

 

Una caja puede tener elementos y cajas

Cajas dentro de cajas

El poner cajas dentro de cajas permite construir estructuras

 

La contención (dentro de, fuera de) permite establecer una relación y un operador entre las cajas

 

Los integrantes de las cajas y su relación de contención establecen un sistema de cajas

 

Dentro de las cajas y entre las cajas se puede establecer también una relación de orden, por ejemplo, cual es el primer componente, el segundo, el tercero, etc.

 

Cortar y pegar, operaciones fundamentales en cajas y entre cajas

buscar, borrar, cortar, pegar, crear, ordenar, etiquetar, relacionar

 

Operación de conjugación o complementación

 

 

Existen cajas físicas y cajas virtuales

 

Algo puede estar dentro de varias cajas virtuales al mismo tiempo

 

Algo puede estar físicamente y tener representación mediante su información en varias cajas virtuales

 

 

Ejemplos de sistemas de cajas

 

Sistemas, fractales, sistemas de archivos, presas, ríos, lagos, entornos, contenedores, espacio, tiempo, subespacios, conjuntos, conceptos generales, patrones, normas, ontologías, reglamentos, leyes, restricciones, espacios de caos, amortiguadores

 

 

Espacio Global, Continuo, Discreto, Probabilístico

Espacio local, Continuo, Discreto, Probabilístico

 

Espacios dimensiónales.

 

Redes neuronales

Cada neurona representa una dimensión

 

 

***********************************************************************

Recursividad Lingüística

 

Tomado y editado de:

Algunas Propiedades Matemáticas de los Sistemas Lingüísticos

Fernando Galindo Soria  Septiembre de 1992

http://www.fgalindosoria.com/linguisticamatematica/propiedades_matematicas_sistemas_linguisticos/prop_mate_sistemas_linguisticos.pdf

 

http://www.fgalindosoria.com/linguisticamatematica/propiedades_matematicas_sistemas_linguisticos/prop_mate_sistemas_linguisticos.htm

 

 

6)         RECURSIVIDAD LINGÜÍSTICA.

 

6.2)      Lingüística Matemática y Recursividad.

Dentro de la Lingüística Matemática se han encontrado una gran cantidad de casos en los que la mejor representación de un lenguaje es en términos de una gramática recursiva y aun mas, en algún momento se ha postulado que el mecanismo "natural" de adquisición del lenguaje en los seres vivos es un mecanismos que genera estructuras recursivas, ya que por ejemplo, si se tiene el siguiente conjunto de oraciones:

                Estudia y triunfaras

                        a          b

                Estudia y trabaja y triunfaras

                        a          a          b

                Estudia y trabaja y ahorra y triunfaras

                        a          a             a                   b

 

Al representarlas mediante su gramática canónica

            a b

            a a b

            a a a b

 

Se observa que entramos en un ciclo de repetición en el cual se pueden poner tantos elementos como se quiera, y podemos proponer que una oración del tipo

            a a a ...a b

 

es sintácticamente válida dentro del lenguaje.

 

Cuando se tiene un conjunto de oraciones donde un tipo de elemento se puede repetir en forma indefinida es conveniente sustituir todo el conjunto de oraciones por una regla recursiva, ya que la representación es mucho más compacta y general.

 

Por ejemplo si tiene

S-->     ab

            aab

            aaab

            ....

            aaa....ab

 

Una regla recursiva asociada es:

S-->     aS| b

 

Ya que sustituyendo S por aS o por b se pueden tener cadenas como las siguientes:

S==> aS==> aaS==> aab

S==> aS==> aaS==> aaaS==> aaab

 

y en general cualquier número de a seguidos por b.

 

Entonces la gramática recursiva genera todas las cadenas originales y muchas mas.

 

 

6.3)      Gramática Recursiva y Generalización.

Por lo común la gramática recursiva es una generalización de la gramática canónica, es decir, que si tengo un conjunto de oraciones donde se detecta una estructura recursiva, ésta no solo genera todo el conjunto de oraciones, sino que además, es capaz de generar muchas otras que no estaban contempladas.

 

Esta propiedad de generalización de las gramáticas recursivas las hace extremadamente poderosas ya que permite encontrar a partir de unos cuantos ejemplos la estructura de un lenguaje.

 

Sin embargo al generalizar se puede llegar a proponer una gramática que genere estructuras oracionales que no sean válidas en el lenguaje, o sea que la gramática puede ser  tan general que produzca cosas sin sentido o contradictorias.

 

A pesar de lo anterior la fuerza de la Recursividad es tan enorme que se utiliza cotidianamente para atacar una gran cantidad de problemas de Lingüística y únicamente se debe ser consciente de sus peligros y no usarla a ciegas.

 

 

6.4)      Método de Generación de Gramáticas Recursivas.

En muchos casos la recursividad se ha introducido en forma intuitiva a los sistemas, sin embargo, ya existen métodos que permiten obtener una gramática recursiva a partir de un conjunto de oraciones del lenguaje.

 

Por ejemplo, si se tiene la gramática:

S-->     a b

            a a b

            a a a b

 

la gramática recursiva que la generaliza es:

S-->     a S | b

 

Ahora bien, si se observa el ejemplo se puede notar que la recursividad se introduce cuando se detecta que una cadena a se repite en forma monótona   a a a alrededor o tendiendo a un punto b.

 

Por ejemplo en la oración

            a b c a b c a b c a b c d

 

la cadena a b c presenta un comportamiento monótono que termina en d.

 

Dada una oración repetitiva para generar la gramática recursiva se siguen los siguientes pasos:

a) Se detecta un comportamiento monótono.

b) Se busca el elemento repetitivo.

c) Se detecta a que punto tiende

d) Se genera la gramática recursiva

 

en la oración

            a b c a b c a b c a b c d

El elemento repetitivo es a b c el sistema tiende a d  la gramática es:

            S-->     a b c S| d

 

Por ejemplo, en la cadena:

            38383838386

 

El elemento repetitivo es 38 el sistema tiende a 6  la gramática es:

            S-->     38 S| 6

 

o sea que toda la cadena repetitiva se sustituye por el elemento repetitivo 38 seguido de un llamado recursivo S, por otro lado el núcleo del sistema 6 se pone como otra opción de la gramática.

 

Por ejemplo la cadena:

            m n o p m n o p m n o p q

 

tiene como cadena repetitiva a m n o p y tiende a q

 

Por lo que la gramática queda:

            S-->     m n o p S |q

 

 

Un caso interesante se presenta cuando el comportamiento monótono es alrededor de un punto, como por ejemplo en la oración:

            ( ( ( ( a ) ) ) )

 

donde el número de paréntesis izquierdos es el mismo que derechos y giran alrededor de a

 

La letra a funciona como Núcleo del proceso recursivo.

 

Para generar la producción recursiva se sustituye el núcleo por la variable recursiva, de donde la gramática queda:

            S -->    ( S ) | a

 

 

7)         ENFOQUE ANALÍTICO DE LOS SISTEMAS LINGÜÍSTICOS.

Como se podrá observar según este enfoque el concepto de recursividad es similar al concepto de límite en el Análisis Matemático ya que en los dos casos se tiene un conjunto de elementos que tienden a o giran alrededor de un núcleo o límite.

 

Las similaridades no se quedan en ese punto, ya que, el proceso recursivo es un proceso que se puede continuar indefinidamente y requiere de un atractor o límite o núcleo o criterio de terminación para detenerse, de donde, tal vez, el Límite del Análisis Matemático y la Recursividad son dos componentes de un fenómeno más general.

 

Aparentemente lo anterior es muy factible, ya que se tienen ejemplos de procesos recursivos que "tienden a un límite" como es el caso de algunos fractales que en el límite tienden a ocupar el espacio delimitado por otros fractales.

....

....

Finalmente no quiero perder la oportunidad de mencionar que he oído comentarios acerca de que los pueblos prehispánicos manejaban los conceptos de Límite y Recursividad dentro de un mismo campo, por lo que, tal vez, estemos en el umbral de una puerta que ha permanecido cerrada por 500 años.

 

 

***********************************************************************

Recorrido de una red

El  recorrido de una red no conmutativa sin repetir nodos es equivalente al ordenamiento de unos números o a una estructura lineal o arborescente o ecuación de la naturaleza o proceso recursivo y tiene n! opciones dónde n es el número de nodos o de dimensiones

 

El recorrido de una red con repeticiones o ciclos tiene n elevado a la n opciones dónde n es el número de nodos y en general tiene n elevado a la m opciones donde m es el número de nodos recorridos o dimensiones

 

 

Proyecciones y representaciones de objetos de n dimensiones en m dimensiones

 

 

 

 

 

LIGAS

 

Godel, Escher, Bach: An Eternal Golden Braid

 

Gödel, Escher, Bach: an Eternal Golden Braid, GEB, Douglas R. Hofstadter, Penguin Books, 1979

 

Uno de los libros mas hermosos, pero complicado de leer para los no hablantes nativos del ingles, ya que esta lleno de giros y juegos mentales difíciles de entender.

En español se han hecho dos traducciones, una en México y la otra en España:

 

Gödel, Escher, Bach, una eterna trenza dorada, Douglas R. Hofstadter, México, Consejo Nacional de Ciencia y Tecnología (Conacyt), 1982

Traducción de Mario Arnaldo Usabiaga Brandizzi

 

Gödel, Escher, Bach, un Eterno y Grácil Bucle,Douglas R. Hofstadter, Barcelona, Tusquets, 1987.

Traducción de Mario A. Usabiaga y Alejandro López Rousseau).

 

A mí me encanta la versión mexicana, pero a otros les gusta más la española.

 

 

Godel, Escher, Bach

Wikipedia 20170409

https://es.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach:_un_Eterno_y_Gr%C3%A1cil_Bucle

Campos de estudio tratados en GEB

autorreferencia, recursión, bucles extraños

....

 

 

Gödel, Escher, Bach, Una eterna trenza dorada

http://avata.utadeo.edu.co/Lecturas/Hofstadter_Douglas_Un_Eterno_y_Gracil_Bucle.pdf

 

Godel, Escher, Bach: An Eternal Golden Braid

https://ia600308.us.archive.org/29/items/GEBen_201404/GEBen.pdf

 

 

***********************************************************************

Language identification in the limit

 

Gold, E. Mark. "Language identification in the limit." Information and control 10.5 (1967): 447-474.

http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf

 

Wikipedia

https://en.wikipedia.org/wiki/Language_identification_in_the_limit

 

 

***********************************************************************

The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge (1984) William Poundstone,

KIRKUS REVIEW

https://www.kirkusreviews.com/book-reviews/william-poundstone-3/the-recursive-universe-cosmic-complexity-and-th/

 

Traduccion mediante Google (20170415)

"El Universo Recursivo: La Complejidad Cósmica y los Límites de Conocimiento Científico ", William Poundstone

REVISIÓN DE KIRKUS

“El título debe ser una advertencia: si usted entiende que "" recursivo "" se refiere a un proceso iterativo utilizado, por ejemplo, en una fórmula matemática en la que el siguiente término de una serie se define en términos del término anterior, usted tiene una pista A las ideas expresadas en este intrigante libro. Poundstone, un físico entrenado por el MIT, lanza su red ampliamente al discurso sobre cosmología, biología, física de partículas, robots auto-reproductores y teoría de juegos. Sus eslabones de conexión, y de hecho su propio tipo de recursiones de orden superior, son capítulos en los que introduce y desarrolla variaciones en un juego de ordenador llamado "Vida", inventado por un matemático llamado John Conway mientras estaba en Cambridge. "" Life "es un juego completamente programable que produce patrones cambiantes en una pantalla visual después de que el jugador establezca un conjunto de condiciones iniciales. Poundstone acredita a Stanislaw Ulam con la génesis de tales pantallas: Parece que cuando el fallecido matemático estaba en Los Alamos jugando con computadoras tempranas, fue capaz de programar patrones visuales inesperados y agradables usando fórmulas de recursión simple. La "Vida" de Conway fue popularizada por Martin Gardner y condujo a una secta de culto entre los piratas informáticos desafiados a ver qué tipo de reglas podrían generar patrones complejos que se reproducirían, generando sucesivas generaciones de copias del patrón. Parecía una manera de conseguir algo para nada - y por lo tanto una posible violación de la segunda ley de la termodinámica. Así, Poundstone introduce la historia del Demonio de Maxwell y algunos de los astutos esquemas que los científicos han construido para convertir al demonio en una máquina de movimiento perpetuo. Al final, por supuesto, no se puede negar la segunda ley. Lo que Poundstone conjetura es que el universo y la vida misma pueden representar el aumento de complejidad y patrón de los últimos días que ha caído de un conjunto de fórmulas de recursión lleno de información que inició el mundo, por así decirlo. Apelando, las ideas provocativas para una audiencia con algo de física, matemáticas, teoría de la información, y conocimiento de la computadora (detalles de la programación son suministrados e ilustrados).”

 

 

***********************************************************************

The Embedding

by Ian Watson 1973

http://www.lycaeum.org/mv/BX/Ian_Watson__The_Embedding.pdf

 

Empotrados

Ian Watson

http://gye.ecomundo.edu.ec/Biblio/Libros_Digitales/Bonus-CienciaFiccion/W/Watson%20Ian/Empotrados.pdf

 

 

 

 

 

INFORMATICS PROPERTIES   /  PROPIEDADES INFORMÁTICAS

Dimension     Density  and Frecuency    Symmetry    Recursion    Form

Dimensión    Densidad y Frecuencia     Simetría     Recursividad    Forma