REKURSIVITÄT Recursividad

REKURSIVITÄT Recursividad

(comp.) Justo Fernández López

Diccionario de lingüística español y alemán

www.hispanoteca.eu

Prozess, der sich selber aufruft und somit wiederholt anwendbar ist, um Entitäten beliebiger Größe zu erzeugen oder zu analysieren: «Wie man Wörter in alphabetischer Reihenfolge bringt: Sortieren Sie die Wörter so, dass sich ihre Anfangsbuchstaben in derselben Reihenfolge wie im Alphabet befinden; danach bilden Sie Gruppen von Wörtern mit demselben Anfangsbuchstaben, ignorieren diesen Anfangsbuchstaben und bringen den Rest in alphabetischer Reihenfolge.» «Eine Verbalphrase kann aus einem Verb bestehen, gefolgt von einer Nominalphrase, gefolgt von einer Verbalphrase.»”

[Pinker, Steven: Der Sprachinstinkt. Wie der Geist die Sprache bildet. München: Knaur, 1998, S. 534]

Aus der Mathematik übernommener Begriff, der in der Linguistik die formale Eigenschaft von Grammatiken bezeichnet, mit einem endlichen Inventar von Elementen und einer endlichen Menge von Regeln eine unendliche Menge von Sätzen zu erzeugen. Auf diese Weise ist ein solches Grammatikmodell in der Lage, die durch Kreativität gekennzeichnete sprachliche Kompetenz des Menschen zu erfassen.

Während N. Chomsky (1957) zunächst in „Syntactic Structures“ R. durch generalisierte Transformationen formalisierte, wird sie in der Standardtheorie der generativen Transformationsgrammatik von Chomsky (1965) (im sog. Aspekte-Modell) durch Phrasenstrukturregeln in der Tiefenstruktur erzeugt. Als einzige Quelle der R. wurde dabei Einbettung von S angenommen, da sich alle rekursiven Konstruktionen (attributive Adjektive, Genitiv- und Präpositionalattribute) auf Relativsätze zurückführen lassen, vgl. das interessante Buch < ® das Buch, das interessant ist. Die einzige notwendige Rekursive Regel der Tiefenstruktur, aus der sich alle oberflächenstrukturellen rekursiven Konstruktionen ableiten lassen, lautete: NP ® NP + S.

Nachdem die Generative Semantik die semantisch motivierten Ableitungen im Sinne einer restriktiven Theorie nur unbefriedigend ausformulieren konnte, wurden nach deren Überwindungen durch die „Revidierte Standardtheorie“ ausschließlich Phrasenstrukturregeln als Quelle für die Generierung rekursiver Strukturen angenommen. Somit wurde z.B. das interessante Buch direkt an der Basis mit Hilfe von NP ® Det + N und der rekursiven Regel N ® A + N erzeugt.“ [Bußmann, S. 640-641]

Nach Chomsky (1965) ein Merkmal der Basiskomponente bzw. der (rekursiven) Regeln, «die das Anfangssymbol S an bestimmten Stellen in Ketten von Kategoriensymbolen einführen»; die Möglichkeit, in einem Regelapparat Regeln wiederholt auf ihr eigenes Ergebnis anzuwenden.” [Lewandowski, Th., Bd. 2, S. 548]

Aus der Mathematik übernommener Regeltyp, der formal dadurch gekennzeichnet ist, dass dasselbe Symbol sowohl links als auch rechts vom Pfeil auftritt; z.B. NP ® N + AP + N. Hier ist N das rekursive Element, das gewährleistet, dass die Regel „auf sich selbst“ angewendet werden kann; denn immer, wenn das Symbol N erreicht ist, kann an dieser Stelle ein Ausdruck (rechts vom Pfeil) für N eingesetzt werden, der das Symbol N selbst wieder enthält.“ [Bußmann, S. 640]

Regeln oder Gruppen von Regeln, die mehr als einmal bei der Erzeugung desselben Satzes anwendbar sind (Das ist der Mann, der das Mädchen geheiratet hat, das das Buch geschrieben hat), die endlos auf ihr eigenes Ergebnis angewandt werden können.

Rekursive Regeln können eine unbegrenzte Menge von Formalobjekten hervorbringen; sie erklären «die aktuelle Fähigkeit eines Sprechers, neue Sätze hervorzubringen und zu verstehen» (Katz).” [Lewandowski, Th., Bd. 2, S. 548]

„Das ist die entscheidende Tatsache, durch die sich rekursive Definitionen von zirkulären unterscheiden. Es gibt immer einen Teil der Definition, der Selbstbezüglichkeit vermeidet, so dass die Konstruktion eines Objekts, das der Definition genügt, schließlich «ausläuft».”

[Hofstadter, Douglas R.: Gödel, Escher, Bach – ein Endloses Geflochtenes Band. Stuttgart: Klett-Cotta, 1986, S. 145]

Mathematische Regeleigenschaft, die in einer Formationsregel ein Element der Eingabekette in der Ausgabekette wiederverwendet: A ® XAY, wobei X oder Y auch null sein können. So vor allem in der generativen Grammatik zur Darstellung formaler Eigenschaften einer Grammatik verwendet. Damit ist mit einem endlichen Regelinventar eine unendliche Menge von Sätzen erzeugbar (darstellbar) und bildet nach der der generativen Grammatik zugrunde liegenden rationalistischen Sprachphilosophie die wesentliche Sprachkompetenz des Menschen dar, nämlich kreativ stets neue Sätze und Bedeutungszusammenstellungen zu ersinnen, ohne solche durch bloßes Erinnern zu leisten. In der Frühphase der Entwicklung der generativen Grammatik galt als formales Mittel zur Sicherung von Rekursivität das Inventar an generalisierten Transformationen. In der Weiterentwicklung, im sog. Standardmodell (ab Chomsky 1965, dem Aspektemodell) geht diese rekursive Kraft in die Konstituentenstrukturregeln ein.

Je nachdem welches der anderen Ausgabeelemente das rekursive Element begleitet, spricht man von Linksrekursivität (sofern X = ø), Rechtsrekursivität (für Y = ø) oder Selbsteinbettung (wenn X, Y ¹ ø).

Im Allgemeinen beschränkt man die rekursive Eigenschaft auf S, da über (Relativ-)Sätze alle anderen modifizierenden Konstituenten (wie Attribut, Apposition) beschränkbar sind. Sowohl (i) wie auch (ii) unten haben rekursive Eigenschaften.

[Abraham, Werner: Terminologie zur neueren Linguistik. Tübingen: Niemeyer, 1988, Bd. 2, S. 685]

Die Anzahl komplexer Sätze ist prinzipiell unendlich. Beschränkungen ergeben sich lediglich aus den praktischen Zusammenhängen des menschlichen Handelns im Besonderen und der Endlichkeit des Daseins im Allgemeinen. Komplexe Sätze werden mit den bereits eingeführten rekursiven Regeln definiert.

Rekursion, d.h. die Wiederholung einer Struktur als Teil von sich selbst, ist aus der Computerkunst und der Mathematik recht bekannt, z.B. in der Form von fraktalen Strukturen, zu denen die Figur der Mandelbrotmenge, die oft in fraktalen Bildern zu sehen sind:

Fraktale werden manchmal als Modelle für die Beschreibung von Strukturen in der Natur genommen:

§ Ein Tannenbaum hat dieselbe Form wie einer seiner Äste. Die Äste haben die Form der von ihnen abgehenden Zweige. Die Zweige haben die Form der Nadelreihen.

§ Bei Lebewesen geht dies - sehr vereinfachend gesehen - über die Reproduktion durch die Generationen weiter:

§ Ein junger Zweig an einem Tannenbaum entspringt einer Nadelreihe und hat deren Form, usw.

Eine Struktur, die den selbstwiederholenden Charakter der Fraktale hat, ist im Baumdiagramm für den Satz This is the dog that chased the cat that killed the rat that lived in the house that Jack built. dargestellt:

In der Linguistik werden zwei Arten der Rekursion als zentral angesehen, von denen beide für die Beschreibung von komplexen Sätzen in Frage kommen:

§ Der Mann, der den Hut, der auf der linken Seite eine Feder hat, trägt, kam ins Bild.

Die ersten beiden Bedingungen definieren alle Sätze einer Sprache, die letzte Bedingung stellt klar, dass nur die Sätze der Sprache definiert werden.

2. Ein Satz verkettet mit `and', verkettet mit einem weiteren Satz ist ein Satz. Konsequenz: auch dieser Satz kann noch mal mit `and' sowie bereits definierten Sätzen verkettet werden,

In Phrasenstrukturregeln (konventionellerweise wird die Ausschlussbedingung nicht mitgeschrieben):

Diese Formulierung erfasst nicht die Details der einzelnen Bestandteile, aber mit ihr können doch schon unendlich viele - wenn auch langweilige - Regeln definiert werden.

Diese können am Beispiel des komplexeren Satzes illustriert werden, in dem keine Koordination, sondern Subordination als rekursiver Mechanismus vorkommt:

this is the dog that chased the cat that killed the rat that lived in the house that Jack built.

„Una definición recursiva de un concepto es una definición que procede por estratos, de la definición de casos simples a la de casos complejos, basados en los anteriores. El lenguaje formal (sintaxis) ofrece una estructura recursiva (fórmulas atómicas, último elemento de análisis, y fórmulas moleculares, compuestas a partir de las atómicas, con un grado de complejidad que puede progresar indefinidamente, pero siempre según determinados módulos fijos), que precisamente permite que se lo defina con un número finito de palabras pese a que sus posibilidades sean infinitas. El acierto de Tarski estuvo en saber apoyarse en esta estructura recursiva del lenguaje para la construcción de sus definiciones semánticas. Toda fórmula es una predicación (verdadera o falsa) o una función lógica de predicaciones, de cuya verdad o falsedad depende.“

[Garrido, Manuel: Lógica simbólica. Madrid: Editorial Tecnos, ²1977, p. 227 n. 14]

“Alonzo Church demostró en 1936 la imposibilidad de hallar un procedimiento decisorio adecuado para la lógica elemental (incluyendo, por supuesto, la lógica cuantificacional poliádica).

El resultado obtenido por Church es, como el famoso resultado de Gödel (Über formal unentscheidbare Sätze der Principia mathematica und verwandte Systeme, 1931), uno de los «teoremas de limitación», que pusieron en crisis en los años treita la ilimitada fe que hasta entonces se había venido depositando en los métodos axiomáticos y dieron lugar, al mismo tiempo, a una de las corrientes más fecundas de la investigación lógico-matemática de los últimos cuarenta años: la teoría de la computabilidad.

Desde principios de siglo David Hilbert había defendido el punto de vista (históricamente sostenido por Ramón Llull en la Edad Media y Leibniz en la Edad Moderna) de que todo problema lógico y matemático podría ser resuelto por procedimientos mecánicos. De ahí la importancia que adquirió hacia los años veinte, el llamado Entscheidungsproblem (problema de la decisión). De hecho, el problema de la decisión para el cálculo elemental de cuantores era, en el sentir de Hilbert, el problema fundamental de la lógica matemática.

Sorprendentemente, los hallazgos más interesantes en la investigación del problema de la decisión fueron hallazgos negativos que establecieron la existencia de problemas insolubles y las fatales limitaciones de sistemas axiomáticos de interés fundamental. En 1931 Kutl Gödel demostró que todo sistema axiomático que pretenda formalizar la aritmética elemental es incompleto. Y en 1936 Church probói primero la indecidibilidad de la aritmética, y luego, con ayuda de este resultado, la indecidibilidad de la lógica elemental (teorema de Church). Church propuso definir el concepto intuitivo y más bien vago de «función efectivamente calculable» mediante el concepto matemáticamente preciso y riguroso de «recursividad». Tal es el fin que persigue la llamada

Tesis de Church (1936): Toda función efectivamente calculable es una función recursiva.

Con la ayuda de su tesis probó Church que no es posible hallar una solución general para el problema de la decisión en teoría elemental de números, es decir, que el sistema formal de la aritmética es indecidible. [...]

En su contribución A note on the Entscheidungsproblem (1936) Church mostró que el sistema formal de teoría elemental de números no podía ser reducido al sistema formal de lógica elemental mediante una serie de transformaciones tendentes a eliminar los símbolos aritméticos; y a continuación hizo ver, como consecuencia de tal reducción, que si hubiera un procedimiento decisorio para toda la lógica elemental, lo habría para la teoría elemental de números. Pero teniendo en cuenta el anterior resultado de Church acerca de la indecidibilidad de la teoría elemental de números, queda establecida la indecidibilidad de la lógica elemental. [...]

Teorema de Church: El caso general del problema de la decisión de L es insoluble. Esto es: la lógica elemental de la cuantificación es indecidible.

El teorema de Church posee relevancia filosófica. Desde el punto de vista de la filosofía, el interés principal de este aserto está en que por él se establece, o se pretende establecer, la no mecanicidad de la lógica formal. Pues si bien es cierto que existen algoritmos que permiten revolver de modo mecánico grandes grupos de problemas de la lógica elemental, según el teorema de Church no existe ni puede existir un algoritmo que los resuelva mecánicamente todos. La operación deductiva de la razón no es totalmente mecanizable.”

[Garrido, Manuel: Lógica simbólica. Madrid: Editorial Tecnos, ²1977, pp. 349-352]

Los problemas científicos comportan a menudo la necesidad de encontrar un modo de proceder que conduzca a la solución por medio de un número finito de operaciones fáciles de ejecutar.

La teoría de las funciones recursivas es posiblemente la teoría matemática que más influencia ha tenido en el desarrollo de la gramática generativa y, en general, de la lingüística matemática.

Veamos una noción intuitiva: Una función f es recursiva general, o efectivamente calculable, o recursiva simplemente, o perteneciente a la clase de funciones recursivas cuando existe un método efectivo para calcular los valores de esta función; es decir, un método de cálculo para todo número natural x de valor y = f(x), con la ayuda de un número finito de ciertas operaciones fundamentales.

En este sentido la función y=x², por ejemplo, es recursiva, puesto que existe un método efectivo para calcular el cuadrado de un número natural arbitrario, la multiplicación por sí mismo. Asimismo, las funciones con dos argumentos, la suma y = x + z y el producto y = x × z son evidentemente recursivos porque existen unas reglas simples para operar. [...]

Queda claro que los métodos para definir funciones recursivas consisten en repetir ciertos procedimientos matemáticos muy simples un número finito de veces. [...]

Una relación R es recursiva cuando existe un método efectivo para verificar si los números naturales dados están en relación R o no.

Un conjunto E es recursivo cuando existe un método efectivo para verificar si para todo x, número natural dado, x pertenece a E o no.

En lengua, la recursividad del conjunto de frases, nos daría un criterio para verificar la gramaticalidad de cada una; es decir, que por un número finito de pasos llegaríamos a saber si una frase es gramatical o no. Nuestro problema es saber si un lenguaje es un conjunto recursivo o no.

El conjunto de los pares es recursivo (sólo es necesario ver la terminación para saber si un número es par o no). El conjunto de los múltiplos de 3 lo es, y, en general, el conjunto de todos los números divisibles por un número fijado y cualquiera es recursivo porque se puede verificar por ensayo directo si es divisible o no. La relación «x es divisible por y» será recursiva también. [...]

La importancia de la recursión para definir funciones de números naturales ya fue notada por Richard Dedekind y Giusepe Peano. Más tarde, Thoralf Skolem y Hilbert pusieron énfasis en la importancia funcional de este método de definición. Finalmente, Kurt Gödel utilizó la clase de las funciones recursivas como piedra angular de su demostración del teorema de incompletitud. [...]

Kleene ha mostrado cómo toda la aritmética clásica se puede describir mediante funciones recursivas.

El fenómeno de recursión es fundamental para la gramática generativa, ya que nos permite, con medios finitos, caracterizar conjuntos infinitos, hecho éste que se encuentra en la base del principio de creatividad de una lengua; por medio de una definición recursiva podemos caracterizar un conjunto infinito; si una lengua, por ejemplo, es un conjunto infinito, pero numerable, entonces puede ser definido recursivamente, por medio de unos esquemas de recursión, muy complicados en el caso del lenguaje natural, que pueden ser presentados como gramáticas generativas.

El conjunto C de secuencias de un vocabulario V = {a,b} que forman el llamado lenguaje reflejado o lenguaje imagen sobre un espejo, es decir,

La definición recursiva de las fórmulas nos permite una decisión mecánica (algorítmica) ante la cuestión de si una expresión dada es o no una fórmula, sin necesidad de apelar al sentido de dicha expresión. [...] La definición recursiva permite, a partir de un número finito dado de proposiciones, en general de frases, un número infinito de proposiciones, frases, derivables por aplicación repetida de un conjunto de reglas. Evidentemente, esta definición nos permite reencontrar el método llamado axiomático-formal; las proposiciones, frases iniciales son los axiomas y el conjunto de frases derivadas de los axiomas por aplicación repetida de las reglas, los teoremas.

Una definición recursiva es como un sistema axiomático (formal) en que la base son los axiomas y la recursión está constituida por las reglas de derivación (deducción); los elementos del conjunto especificado por la definición recursiva coinciden con el conjunto de teoremas del sistema.

Definiremos un tal sistema de la siguiente forma: Un sistema axiomático (formal) es una estructura matemática definida por el siguiente cuadruplete: <V, F, A, R> donde

De los sistemas axiomáticos formales podríamos pasar a un tipo particular de ellos, los llamados sistemas combinatorios, entre los que se incluyen los sistemas semitueanos que incluyen, en a su vez, las gramáticas generativas.“

[Serrano, Sebastián: Lógica, lingüística y metemáticas. Madrid: Editorial Anagrama, 1977, p. 176 ss.]

“Para la comprensión de la demostración que Gödel (1931) hace de su teorema resulta necesaria la noción de «función recursiva», cuya configuración precisa se consigue en el quinquenio siguiente. [...] En 1936, A. Church define la noción de «función efectivamente calculable», basándose en la noción más precisa de «función λ-definible». [...] Por su parte Kleene estableció la equivalencia entre función recursiva general y función λ-definible. Y basándose en estos resultados, propone Church identificar «efectivamente calculable» con «λ-definible» o con su equivalente: «recursivdad general». Esta propuesta es conocida como la Tesis de Church:

Como tesis que es (ya que le equivalencia enunciada mediante «es» se establece entre la noción precisa de «función recursiva general» y la noción antropológica e intuitiva de «función efectivamente calculable») no puede ser probada, pero todas las funciones efectivamente calculables hasta ahora conocidas son recursivas.

Posteriormente, Markov estableció de manera precisa el concepto de «algoritmo», y D’etlovs probó que las funciones calculables mediante tales algoritmos coinciden también con las funciones recursivas generales. Finalmente, en 1980, Gandy siguiendo las directrices marcadas por Turing, aduce una serie de principios que apoyan la justificación de la Tesis de Church.

Dando por supuesta esta Tesis, Church demostró, primero, que el problema de la decisión es insoluble en la teoría elemental de números, esto es, que no es posible encontrar un procedimiento efectivo que permita decidir, para toda proposición de la teoría, si es derivable o no.

Luego, suponiendo también la tesis, mostró que el sistema de la Lógica Elemental (la lógica de predicados de primer orden de Hilbert y Ackermann) es indecidible. Este resultado es conocido como Teorema de Church. [...] Según este teorema, el conjunto de las fórmulas de la Lógica Elemental lógicamente válidas no es recursivo (en el sentido, propuesto por Church, de que no es efectivamente computable).

El teorema de Church constituye otra de las limitaciones del formalismo; mas las limitaciones de los sistemas formales no lo son de la capacidad de la razón humana; es lo que Gödel quiere dejar bien sentado al criticar la idea de Turing de que la mente humana es equivalente a una máquina:

«Turing ofrece una argumentación que se supone muestra que los procedimientos mentales no pueden llegar más lejos que los procedimientos mecánicos. Sin embargo, esta argumentación es inconcluyente, pues depende de la suposición de que una mente finita sólo es susceptible de tener un número finito de estados distinguibles. De lo que Turing no se da cuenta es del hecho de que la mente, en su uso, no es estática, sino que está en constante desarrollo». (K. Gödel, Obras completas. Madrid: Alianza Editorial, 1981, p. 171, nota).”

[Velarde Lombraña, Julián: Historia de la lógica. Oviedo: Servicio de Pub. de la Universidad. O. J., pp. 405 y 406‑4]

Naturaleza y cultura no son alternativos ni excluyentes. El aprendizaje debe realizarse a través de un esquema de circuitos innatos y lo que es innato no es una serie de rígidas instrucciones para un determinado comportamiento, sino más bien programas que absorben informaciones de los sentidos y dan vida a nuevos pensamientos y nuevas acciones. El lenguaje es un caso paradigmático. Una vez adquirida, una lengua no es un elenco rígido de frases, sino un algoritmo combinatorio que hace posible expresar un número infinito de nuevos pensamientos.