La
propiedad de la recursión en el "Tractatus
Logico-Philosophicus"
de Wittgenstein y su relación con la Teoría
de la Computabilidad y la Lógica Matemática*El concepto de recursión ha sido empleado de forma ambigua dentro de diferentes disciplinas, como son la lógica matemática, y más concretamente dentro de una rama especializada de ésta, la teoría de la computabilidad, y la ciencia cognitiva. En el primer caso, el término ‘recursión’ ha significado tanto ‘definición por recursión’ (o ‘por inducción’) como ‘computabilidad’ (Soare, 2009). El primer uso del término ‘recursión’ se aplica cuando se quiere predicar recursividad de una función. Así, se dice que una función es recursiva, esto es, está definida por recursión en un sentido técnico, cuando para definir un argumento y hacemos uso de sus propios valores previamente computados para argumentos menores que y; pudiendo emplearse también funciones previamente definidas (Soare, 1996, 1999, 2009; véase también Gödel, 1931; Kleene, 1952, 2002; Cutland, 1980). Este es el significado original y primario del término ‘recursión’, empleado tanto por Dedekind como por Peano en el siglo XIX.
En este sentido, Epstein y Carnielli (1989) indican que en su forma más simple, la definición recursiva de una función f sería como sigue (siendo g una función previamente definida): f(0) = m; f(n+1) = g(f(n)). Este sistema de ecuaciones recursivas puede instanciarse fácilmente y de una manera perspicua en la función suma (Kleene, 1952, 2002; Boolos y Jeffrey, 1974). Así, el caso base sería: 2+0 = 2, mientras que el paso recursivo sería 2+2 = (2+1)+1; siendo g en el esquema de arriba la función sucesor (S(a) = a+1).
Sin embargo, tal y como señala Soare (1996, 1999, 2009), el concepto de recursión se comenzó a aplicar para significar ‘computabilidad’. El término ‘computabilidad’ (o ‘computable’) se refiere a una función para la que existe un procedimiento mecánico finito (esto es, un procedimiento generativo o algoritmo) por medio del cual es computada o calculada. Desde 1996, Soare ha propuesto volver a emplear el concepto de recursión en su sentido original, distinguiéndolo del de computabilidad, un concepto relacionado pero no coextensivo, dado que hay formalismos que no proceden recursivamente, como la máquina de Turing.1
Por otro lado, la propiedad de la recursividad ha suscitado mucho interés en el campo de la ciencia cognitiva. Es muy conocido el ya clásico trabajo de Hauser, Chomsky y Fitch (2002) en el que proponen que la recursión es una propiedad central de la facultad del lenguaje. Estos autores toman como referencia el Programa Minimista previamente formulado por Chomsky (1995). Para Chomsky (1959, 1995, 2005, 2007, 2008, 2010, 2011, 2012), el lenguaje, esto es, el I-language como él lo define, puede ser entendido como un procedimiento generativo o sistema de cómputo capaz de generar una cantidad potencialmente infinita de expresiones jerárquicas internas. De este modo, la teoría de la gramática, que comprende el estudio del lenguaje así entendido, es el estudio de una clase especial de funciones recursivas dentro de la teoría de la computación (Chomsky, 1959, 2012).
Dentro de este planteamiento, Chomsky (2007, 2008) distingue claramente entre dos niveles de análisis. Podemos denominar a dichos niveles como el nivel del ‘qué’ y el nivel del ‘cómo’. El concepto de recursión es aplicado a estos dos niveles en el mismo sentido técnico derivado de la teoría de la computabilidad. Así, con respecto al nivel de análisis que formula qué hace un procedimiento generativo, podemos decir que lo que hace es generar recursivamente valores (objetos sintácticos, proposiciones de la lógica, términos de una serie de formas, números naturales, etc.). Esto quiere decir que cada nuevo valor se genera usando valores previamente computados, tal y como he señalado en relación con las funciones recursivas en el campo de la teoría de computabilidad.
Con respecto al segundo nivel de análisis, aquel que formula cómo genera esos valores un procedimiento generativo, esto es, cómo procede, tanto de manera abstracta como en tiempo real, encontramos que o bien puede proceder recursivamente o iterativamente. En el primer caso, el procedimiento se llama a sí mismo exactamente en el modo indicado por la definición recursiva. Así, si se quiere computar 2+2, el procedimiento invoca un valor previamente computado para un argumento menor, esto es, se computaría (2+1)+1. En el segundo caso, el procedimiento no se llama a sí mismo y sencillamente se aplica la misma operación sobre el último valor generado. Esto es, se obtiene el sucesor de 1 (1+1) y al resultado (2) se le añade 1, y al resultado (3) se le suma 1, hasta que se alcanza el valor ‘4’. Mediante tal implementación iterativa, una operación genera sucesivamente valores desde un argumento a otro sin usar valores previamente calculados para argumentos menores.
Conviene señalar que aunque un procedimiento se defina recursivamente, éste no tiene que implementarse de manera recursiva necesariamente (Abelson et al., 1996). Un ejemplo de esto acaba de ofrecerse en relación con la implementación recursiva e iterativa. En esta distinción repara también Chomsky (2007, 2008) cuando establece que el procedimiento generativo que subyace a la facultad del lenguaje genera recursivamente objetos sintácticos, pero su operación fundamental, Merge, procede iterativamente.2
Sin embargo, en la ciencia cognitiva el concepto de recursión también se aplica a la organización interna de las estructuras que estudia. Así, una estructura recursiva se define como aquella en la cual un constituye (o una estructura Xn) contiene a otro constituyente (o estructura Xn+1) del mismo tipo (Pinker y Jackendoff, 2005; Moro, 2008; Karlsson, 2010; Kinsella, 2010). Ejemplos de tales estructuras son tanto “[la casa de [la sierra]SN]SN es de piedra”, como “[el ratón [que el gato [que el perro perseguía]O mordió]O corría]O”.
Este uso del término ‘recursión’ añade un significado adicional que nada tiene que ver con su sentido original, a saber, el de auto-inclusión (self-embedding en inglés). Así, de acuerdo con Chomsky (1965), una estructura con auto-inclusión es aquella en la que el sintagma (o estructura) A esta auto-incluido en B si A está anidado en B y, además, A es un sintagma (o una estructura) del mismo tipo que B (es importante hacer ver que el concepto de recursión no es empleado en la definición de estructuras con auto-inclusión).
Por su parte, Moro (2008), muestra que todos los sintagmas, como por ejemplo, muchas casas viejas, presentan el esquema asimétrico universal siguiente: [Especificador-[Núcleo-Complemento]]. Así, el especificador es muchas, el núcleo es casas y el complemento es viejas. Tal y como señala Moro, tanto el especificador como el complemento (que añaden diferente información sobre el núcleo) pueden presentar el mismo esquema asimétrico (op. cit., p. 71), que aplicado al ejemplo anterior sería […Núcleo…-[…Núcleo…-[…Núcleo…]]]. Esto lleva a aplicar la noción de recursión tales estructuras, sin embargo, tal empleo sigue significando lo mismo que en el caso de los constituyentes, a saber: auto-inclusión: esquemas dentro de esquemas del mismo tipo.
Esto refleja con claridad la falta de precisión conceptual y la consecuente confusión en ciencia cognitiva, empleando de manera superficial el concepto de recursión y usándolo cuando en realidad se quiere significar la auto-inclusión de estructuras dentro de otras del mismo tipo.3 Por otro lado, el concepto de auto-inclusión no es empleado en la definición original de ‘recursión’, la cual he mostrado unas líneas más arriba. Es claro, por tanto, que ambas nociones hacen referencia a propiedades independientes entre sí, y conviene recordar que usar una palabra con significados distintos sólo da lugar a equívocos.
Así, el significado de recursión empleado en este trabajo es el que originalmente se empleó en la teoría de la computabilidad, el cual, por cierto, siempre empleó Wittgenstein, al igual que Chomsky, y que nada tiene que ver con el que se predica en relación con la organización jerárquica interna de las estructuras.
Veamos a continuación donde se localiza la propiedad de la recursión en el Tractatus de Wittgenstein, una cuestión que no ha recibido suficiente atención, a mi juicio, en grandes obras centradas en la figura de Wittgenstein, como las de Baker y Hacker (1980, 1985) Hacker (1990) o Potter (2009), por poner unos ejemplos. Más bien, este trabajo está en la línea de aquellos realizados por autores como Marion (1995, 1998), Frascolla (1994) u Odifreddi (2001), los cuales destacan la importancia del trabajo de Wittgenstein en el dominio la filosofía y los fundamentos de la matemática, complementando a los anteriormente citados.
Antes de entrar de lleno en el objetivo fundamental de este apartado, conviene indicar dos cosas de cierta relevancia. La primera es que con la formulación del programa finitista de Hilbert, uno de los objetivos prioritarios de la lógica matemática y de la teoría de la computabilidad fue el de dar una definición formal de un procedimiento mecánico finito (esto es, un procedimiento generativo). Wittgenstein contribuyó a este propositico y definió unos procedimientos capaces de generar todas las proposiciones de la lógica de enunciados así como la serie de los números naturales sobre la que la aritmética se define, postulando la recursión como propiedad central de tales series de formas. En segundo lugar, y al igual que Chomsky, Wittgenstein también distingue entre los niveles de análisis en torno a qué hace un procedimiento generativo y cómo lo hace, algo que se aprecia con claridad en el Tractatus (1922).
Dicho esto, es necesario ver con claridad qué entiende Wittgenstein por ‘operación’ para así comprender mejor tanto la definición formal como la aplicación de tales procedimientos.
Para Wittgenstein, una operación “muestra cómo se puede pasar de una forma de proposición a otra” (5.24). Dado que una serie de formas “es una serie que está ordenada por relaciones internas” (4.1252)4 y “[l]as estructuras de las proposiciones están en relaciones internas entre sí” (5.2), se puede concluir que una serie de proposiciones es una serie de formas. La serie de los números naturales también es una serie de formas, tal y como señala Wittgenstein en 4.1252. En este sentido, “[l]a relación interna que ordena una serie equivale a la operación mediante la que un término resulta a partir de otro” (5.232), siendo posible sólo de esta manera “la progresión de un término a otro en una serie de formas” (5.252).
Veamos a continuación cuál es el procedimiento generativo que propone Wittgenstein para generar una serie de formas. Este procedimiento queda expresado en la denominada forma general (o término general) de una serie de formas: [a, x, O’x]. En 5.2522, Wittgenstein explica en qué consiste esta notación. Así, “[e]l primer término…es el comienzo de la serie de formas, el segundo es la forma de un término x cualquiera de la serie y el tercero la forma de aquel término de la serie que sigue inmediatamente a x”.
Este procedimiento genera series como la siguiente: a, O’(a), O’(O’(a)), y así sucesivamente. Esta operación se aplica iterativamente, esto es, de manera sucesiva, sobre su último resultado producido (5.2521).
Dicho esto, podemos aplicar ahora los dos niveles anteriormente definidos sobre la generación de una serie de formas. Así, podemos decir que lo que hace este procedimiento es generar recursivamente términos de la serie en el que cada término está definido por recursión; esto es, cada nuevo término de la serie (por ejemplo, O’(O’(a))) está definido por términos de la serie previamente computados (esto es, a y O’(a)). Por su parte, cómo hace el procedimiento para generar tales términos queda explicado mediante la aplicación sucesiva (iterativa) de la operación O’ sobre el último elemento generado en cada paso. Formalmente, este procedimiento puede definirse como sigue: O’(0)(a) = a; [el caso base] O’(n)(a) = O’(O’(n-1)(a)) [el paso recursivo]. Este análisis se aplica exactamente igual al procedimiento generativo que queda expresado mediante la forma general de una proposición que Wittgenstein presenta en 6: [p̃, ξ̃, N(ξ̃)]. El primer término de la expresión se refiere al conjunto de las proposiciones base o elementales, el segundo término se refiere a una variable proposicional (véase 5.501) y el tercer término es aquel que se obtiene al aplicar la operación N ( ) a ξ̃ (véase 5.22, 5.23, 5.502 y 5.51).
Es necesario, antes de continuar, apuntar brevemente algunas cuestiones sobre la operación N(ξ̃). Como el propio Wittgenstein señala en 5.502, “N(ξ̃) es la negación de todos los valores de la variable proposicional ξ”. Por tanto, como indica en 5.51, si ξ = p, entonces N(ξ̃) = (FVFV) (p). Por otra parte, si ξ = p,q, entonces N(ξ̃) = (FFFV) (p,q). Así, la operación N(ξ̃) es equivalente a la operación de la negación conjunta, la cual se representa por medio de la barra de Sheffer (Mounce, 1981). Como Mounce (op. cit., p, 50) señala, cuando Wittgenstein escribió el Tractatus ya se había demostrado con claridad que todas las constantes lógicas podías reemplazarse por una sola, la mencionada barra de Sheffer. Tal descubrimiento, permite ver de manera más perspicua las relaciones internas entre las formas de las proposiciones, tal y como indica Wittgenstein en 5.13, 5.131 y 5.1311. De este modo, por medio de la negación conjunta, podemos hacer surgir una nueva proposición N(ξ̃) a partir de ξ, previamente generada. Veamos esto con un poco más de detalle: En 5.22, Wittgenstein establece que “[l]a operación es la expresión de una relación entre las estructuras de su resultado y las de sus bases”. Así, “[l]a operación es lo le ha de suceder a una proposición para hacer surgir otra distinta a partir de ella” (5.23). Como el propio Wittgenstein se encarga de establecer, “[e]sto no dice sino que toda proposición es un resultado de aplicaciones sucesivas de la operación N(ξ̃) a proposiciones elementales” (6.001; véase también 6.002).
Aplicando de nuevo los dos niveles de análisis, vemos que, como en el caso anterior, lo que hace este procedimiento es generar recursivamente las proposiciones de la lógica proposicional. Un ejemplo de dicha generación recursiva sería esta: p,q, N(p,q), N(N(p,q)), y así sucesivamente. Así, cada nueva proposición (por ejemplo, N(N(p,q))) es generada haciendo uso de preposiciones previamente computadas (por ejemplo, N(p,q)). Dado que dicha serie recursiva es una serie de formas, su definición formal sería: N(0)(p,q) = p,q; [el caso base] N(n)(p,q) = N(N(n-1)(p,q)) [el paso recursivo] (nótese que esta definición se aplica igual para ξ = p). Por otro lado, el nivel de análisis del cómo caracteriza la aplicación iterativa de la operación N(ξ̃) sobre el último resultado generado.
Por último, Wittgenstein también proporciona un procedimiento generativo que permite generar la serie de los números naturales; serie sobre la que se sustenta toda la aritmética. Así, la forma general de un número natural (o entero positivo) es ‘[0, ξ, ξ + 1]’ tal y como Wittgenstein establece en 6.03.5 Así, el primer término de la expresión hace referencia al primer término de la serie, el segundo es una variable numérica que puede adoptar cualquier valor de la misma y el tercero hace referencia al número que sigue inmediatamente al anterior.
Análogamente a lo señalada con referencia a los dos procedimientos anteriores, lo que hace el presente procedimiento es generar recursivamente la serie de los números naturales: (I)+I, ((I)+I)+I, (((I)+I)+I)+I, y así sucesivamente (Wittgenstein, 1978). Por otra parte, procede de manera iterativa aplicando al último resultado la operación ‘+1’.6
Teniendo en consideración todo lo dicho hasta aquí, es posible generalizar la formulación de la forma general de una serie de formas a la forma general de un procedimiento generativo. Muy brevemente, la definición formal de un procedimiento mecánico finito ocupó gran parte de la teoría de la computabilidad. Mediante dicha definición, se pretendía capturar la clase de las funciones computables; esto es, las funciones para las que existía un algoritmo o una serie de pasos que permitían calcularla.
Las formulaciones más relevantes fueron hechas por Skolem (1923) quien formuló varias funciones recursivas primitivas como Gödel (1931), quien amplió la clase de las funciones recursivas primitivas a la clase de las funciones recursivas generales (Gödel, 1934). La diferencia fundamental entre una clase y otra es que mientras que en las funciones recursivas primitivas el paso recursivo se aplica a una sola variable (el otro argumento es un parámetro fijo) en las funcione recursivas generales el paso recursivo se aplica, al menos, a dos variables simultáneamente (Soare, 1996, p. 286).
Por su parte, Church (1932) formuló el cálculo-λ y posteriormente demostró que dicho formalismo era equivalente a las funciones recursivas generales, lo que le llevó a formular la famosa Tesis de Church, que establece que toda función efectivamente computable es recursiva general (Church, 1936). Turing también formalizó la noción de computación mediante el formalismo conocido como la máquina de Turing (1937; véase la nota al pie 1). En su caso, la Tesis de Turing, asevera que una función es computable si y sólo si es computable por una máquina de Turing (Soare, 2009, p. 373).
Otro autor de gran importancia es Post (1921, 1941, 1943, 1946), cuyo formalismo consiste en un sistema capaz de generar todas las proposiciones de la lógica de enunciados. Así, sea g un enunciado de la lógica proposicional y P una variable operacional aplicada a dicho enunciado, el sistema produce un enunciado g’ que sustituye a g. Esto se expresa en su sistema de producción normal como sigue: gP→Pg’ (Post, 1943, p. 199). Su tesis, conocida como la Tesis de Post, establece que un conjunto no vacío (como el de las proposiciones de las lógica de enunciados) es efectivamente numerable si y sólo si es derivado de un sistema de producción (normal) [derivado de su sistema canónico (normal)] (Davis, 1982; Soare, 2009).
También es importante destacar el formalismo de Kleene (1938, 1943, 1952), quien definió la clase de las funciones recursivas parciales (la cual identifica correctamente la clase de las funciones computables [Kleene, 1952, pp. 323-348]), una clase que recibe su nombre por el hecho de que una función no necesita estar definida para todas las n-tuplas de números naturales que toma como argumentos, y que incluyen las funciones recursivas primitivas y las funciones recursivas generales, estas últimas como aquellas funciones parciales para las cuales está definido todo el conjunto de sus argumentos. Así, es posible definir la Tesis de Kleene, una tesis no formulada explícitamente, que establece que una función es computable si y sólo si es una función recursiva parcial (o está definida por el formalismo de Kleene). Asimismo, y dado que el formalismo de Kleene es extensionalmente equivalente a la máquina de Turing (Epstein y Carnielli, 1989), es posible establecer otra tesis no formulada explícitamente, a saber, la Tesis de Turing-Kleene, que establece que una función es computable si y sólo si es computable por una función recursiva parcial o, de forma equivalente, por una máquina de Turing.
Presentado este marco general, voy a mostrar a continuación que Wittgenstein presentó lo que es común a todos ellos como objetos matemáticos formales, mediante su formulación de una serie de formas. Así, todos estos procedimientos mecánicos finitos constan de: un conjunto de inputs base (σ̃), una variable que puede adoptar el valor de un subconjunto de dichos inputs (ε̃) y una variable operacional (Õ( )) que genera nuevos valores (Õ(ε̃)) haciendo uso de valores previamente computados (ε̃) mediante la aplicación en sucesión de la variable operacional Õ( ). Además, tal expresión muestra claramente como la recursión sería una propiedad esencial referente a lo que hacen tales procedimientos. Esta formulación puede resumirse en al siguiente expresión: [σ̃, ε̃, Õ(ε̃)].
Así, sean los inputs base números naturales o enunciados de la lógica proposicional, y adopte la variable operacional Õ( ) el valor que adopte (por ejemplo, la operación de sumar, como en el caso de las funciones recursivas; los operadores de la lógica proposicional, como en el caso de los formalismos de Wittgenstein o Post; o las operaciones que lleva a cabo una máquina de Turing) se pueden definir para todos ellos la siguiente serie recursiva: ε̃, Õ(ε̃), Õ(Õ(ε̃))… y así sucesivamente. Cada miembro se genera mediante la aplicación iterativa de la variable operacional en cada paso, pero cada miembro (y por tanto, la serie completa) son definidos por recursión: Def. Õ(0)(ε̃) = ε̃ [el caso base]; Õ(n)(ε̃) = Õ(Õ(n-1)(ε̃)). Y es que, tal y como señaló Wittgenstein (1975b, § 154), un sistema formal, como lo son todos y cada uno de los sistemas arriba mencionados, es una serie de formas, esto es, cada uno de sus miembros ordenados en la serie se encuentran relacionados internamente entre sí, tal y como acabo de explicar.
Veamos esto con un ejemplo. En el caso de las funciones recursivas, podemos ilustrar lo dicho mediante la función suma. σ̃ sería un miembro inicial de la serie del conjunto de los número naturales 1, 2, 3,…n; ε̃ sería una variable que adoptaría los valores de dos números de la serie; y Õ(ε̃) hace referencia al valor que se genera haciendo uso de valores previamente computados para argumentos menores aplicando Õ( ). Un ejemplo concreto de la serie formal ε̃, Õ(ε̃), Õ(Õ(ε̃)) puede ser (2+2), (2+2)+1, ((2+2)+1)+1. Tal serie puede generarse recursivamente mediante el sistema de ecuaciones recursivas arriba presentado como sigue:
Así la serie de la suma consiste en el sucesor de φ(a,b) [= (a+b)]. Recuérdese que la función suma y la función sucesor son dos funciones diferentes y que lo que convierte en recursivo tal expresión no es la presencia de la función sucesor, si no el hecho de que para definir un nuevo valor se hace uso de valores previamente computados para argumentos menores.7
Tal sistema puede expresarse en el formalismo de Wittgenstein, aquí reproducido como [Ω0’x, Ωv-1’x, Ωv’x]. Así pues, sea la serie Ω2+2x, Ω(2+2)+1x, Ω(2+2)+1)+1x vemos que:
Como muestra Wittgenstein en 6.241, esto sería válido también para la multiplicación y, presumiblemente, para todas las operaciones de la teoría de números, las cuales subyacen a diferentes procedimientos mecánicos finitos, así como para las otras clases de funciones recursivas mencionadas aquí, recogidos todos ellos bajo esta forma general de una serie de formas. Si esto se puede generalizar a otros procedimientos mecánicos finitos, como parece que así es8, se puede definir la forma general de un procedimiento mecánico finito, equivalente a la forma general de una serie de formas, o dicho de otra manera, sería una instancia de una serie de formas, que recoge lo esencial y común a todos ellos desde un punto de vista formal, esto es, expresa lo común a todos ellos como objetos matemáticos formales, especificando que lo que hacen es generar recursivamente distintos valores relacionados internamente entre sí y constituyendo, por tanto, series de formas.
Sin embargo, hay algunos aspectos que no son esenciales a la definición formal de un procedimiento generativo arriba señalada. Uno de estos aspectos es cómo implementamos dicho procedimiento. Esto no quiere decir que no sea importante buscar la mejor manera de implementar un algoritmo, sencillamente quiere decir que la forma general de un procedimiento generativo (esto es, su definición formal) es independiente del modo (o modos) en que se implementa un procedimiento (o algoritmo).
Por otro lado, las distintas formulaciones de los diferentes procedimientos generativos no son sino instancias del concepto de procedimiento generativo mecánico finito definido formalmente en el Tractatus Logico-Philosophicus por Wittgenstein. Así, cómo operan o proceden los distintos sistemas generativos o procedimientos mecánicos finitos no es esencial a dicho concepto. De este modo, las diferencias intensionales, aunque válidas para identificar cuáles pueden ser las formulaciones de un procedimiento más claras y perspicuas, no son esenciales para definir formalmente el concepto de procedimiento mecánico finito, puesto que todas ellas caen bajo dicha forma general. La razón fundamental es porque lo esencial a todo procedimiento es lo que todos ellos tienen en común entre sí. Lo esencial es, así, lo recogido en la forma general.
Los diferentes procedimientos generativos propuestos por Wittgenstein en el Tractatus están, en un sentido técnico, definidos por recursión. De hecho, gracias a las formulaciones presentadas por Wittgenstein en su Tractatus, es posible establecer la forma general de un procedimiento generativo (mecánico finito) de manera análoga a la formulación de la forma general de una serie de formas. En dicha formulación se muestra claramente cómo la recursión es una propiedad que puede definir todo procedimiento, al menos en el dominio de lo que cada uno hace, a saber, generar recursivamente una serie de términos o miembros (esto es, una serie de formas). Dicho forma general expresa lo que todos ellos tienen en común, lo que es esencial a todos ellos; del mismo modo que, tal y como Wittgenstein indica, “la forma general de la proposición es la esencia de la proposición” (5.471).
El Tractatus de Wittgenstein puede entenderse, desde este punto de vista, como una aproximación a las funciones efectivamente computables o calculables.
Fecha de recepción: 12 de octubre de 2013
Fecha de Aprobación: 6 de diciembre de 2013
