Autor Tema: Comentarios a "La Aritmética Recursiva Primitiva"

0 Usuarios y 1 Visitante están viendo este tema.

08 Junio, 2023, 05:49 pm
Respuesta #20

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
Me has deformado la frase  >:(, y así ciertamente suena fatal. Yo decía: "Estamos suponiendo que hemos razonado".

Me disculpo por haber deformado la frase, pero total mi perplejidad era la misma.


08 Junio, 2023, 06:10 pm
Respuesta #21

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
No puedo aceptar que introduzcas la "propiedad" Q(n), porque así te encuentras de repente con infinitas propiedades, y (en contra de lo que acabas planteando en los spoilers) la inducción no tiene que ver con infinitas propiedades.

Pero es que la inducción tiene una conclusión,
y la conclusión es que:

Citar
Principio de inducción [...] podemos concluir que todos los números naturales tienen dicha propiedad.

Eso está cuantificando sobre los naturales, y se habla de infinitas afirmaciones:
el 1 cumple la propiedad, el 2 cumple la propiedad, etc.

Lo "finitista" es el procedimiento de inducción,
que involucra P(1), y la relación entre dos proposiciones P(n) y P(n+1).
Aún así, si esto es iterativo, entonces se hace infinitas veces.

Son infinitas afirmaciones de implicación, e infinitas conjunciones, si uno quiere verlo así, en la conclusión.

____________________

Ahora, puede ser que le quisiste decir es otra cosa.
Tal vez que estamos contando propiedades de manera diferente.
¿Acaso la propiedad a la que te referís en tu presentación de la inducción "es una sola"?
No veo por qué mis \(Q(n)\) son infinitas propiedades.
Yo podría decir que estoy probando una propiedad \(Q\)
que para cada natural \(n\) adopta una forma que depende de  \(n\).

Estoy seguro que la inducción que enunciaste es un esquema del mismo estilo.
Para cada \(n\), el contenido de la "propiedad" en cuestión depende de ese valor de \(n\).
¿Por qué no se puede tomar de la misma manera a lo que llamé \(Q(n)\)?

¿Por qué \(P(n) \equiv [n+3=3+n]\) es "una" propiedad, mientras que \(Q(n)\equiv[(n+3=3+n)\to ((n+1)+3=3+(n+1))]\) serían "infinitas propiedades?

____________________

Lo que digo es que mi construcción geométrica (enredosa o no),
le da sentido a cuantificar sobre los naturales y trabajar incluso con infinitas propiedades.
Al final será lo mismo, porque esas infinitas sentencias que indiqué requieren que,
en la práctica, se compruebe que realmente son sentencias.

Creo haber usado construcciones basadas en la intuición (me cuesta todavía entender qué hago cuando hago eso, pero digamos que he procurado seguir las reglas del juego),
y definiciones claras, sin caer en nada de formalismo alguno.

En tal caso, sería un principio lógico más.

Estoy influenciado por la forma de trabajar formalista, claramente,
pero eso no quiere decir que esa forma general de inducción que pretendí hacer esté mal.
Y que no quiera decir, pues no signfica que de todos modos no esté mal a fin de cuentas,
lo cual es otra historia...  :'( :'( :'(


08 Junio, 2023, 09:44 pm
Respuesta #22

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Me disculpo por haber deformado la frase, pero total mi perplejidad era la misma.

¿Pero te disculpas en serio? ¿Qué importancia tiene eso?

Citar
No puedo aceptar que introduzcas la "propiedad" Q(n), porque así te encuentras de repente con infinitas propiedades, y (en contra de lo que acabas planteando en los spoilers) la inducción no tiene que ver con infinitas propiedades.

Pero es que la inducción tiene una conclusión,
y la conclusión es que:

Citar
Principio de inducción [...] podemos concluir que todos los números naturales tienen dicha propiedad.

Eso está cuantificando sobre los naturales, y se habla de infinitas afirmaciones:
el 1 cumple la propiedad, el 2 cumple la propiedad, etc.

Lo "finitista" es el procedimiento de inducción,
que involucra P(1), y la relación entre dos proposiciones P(n) y P(n+1).
Aún así, si esto es iterativo, entonces se hace infinitas veces.

No me expresé bien al hablar de infinitas propiedades. En realidad tenía que haber dicho "infinitas afirmaciones", pero, aun diciéndolo mal, era justo lo que acabas de decir ahora lo que quería negar. Nadie puede hacer nada infinitas veces. A eso me refería, a que una inducción no consiste en demostrar infinitas afirmaciones, consiste en demostrar dos. Y la conclusión es una: la conclusión es que "todos los números naturales \( n \) cumplen \( P(n) \).

Es verdad que yo siempre digo que afirmar que todos los números naturales cumplen \( P(n) \) no significa, ni más ni menos, que "se cumple P(0)" y "se cumple P(1)" y "se cumple P(2)", etc. y eso son infinitas afirmaciones, pero yo no diría que cuando probamos que todos los números naturales cumplen P(n) estamos demostrando infinitas afirmaciones. Estamos demostrando una afirmación que tiene infinitas consecuencias, pero eso es típico. Cualquier afirmación tiene infinitas consecuencias.

Por eso te decía que desglosar el principio de inducción en una prueba de infinitas afirmaciones no me parece un avance a la hora de entenderlo, sino más bien un retroceso.

Son infinitas afirmaciones de implicación, e infinitas conjunciones, si uno quiere verlo así, en la conclusión.

Sí, yo digo que el significado que "todo número natural n cumple P(n)" no es ni más ni menos que infinitas conjunciones, en el sentido de que nada expresa el significado de esa afirmación salvo el "se cumple P(0) y P(1) y P(2)... ", pero no creo que sea orientativo afirmar que cuando razonamos por inducción demostramos infinitas cosas. Lo que demostramos es \( \forall n (P(n)\rightarrow P(n+1)) \) y la gracia del asunto está en que esto se demuestra de una sola vez, no como una conjunción de infinitas afirmaciones, aunque su significado sea ése. Por ejemplo, si yo recurro a un libro de geografía para justificar que "todos los españoles son europeos", puedo decir que he demostrado una única afirmación, aunque sea equivalente a 47 millones y pico de afirmaciones (una para cada español). El hecho de que "Todos los españoles sean europeos" equivalga a una conjunción de 47 millones y pico de afirmaciones no significa que sea razonable considerar una prueba de este hecho como una prueba de 47 millones y pico de afirmaciones.

Ahora, puede ser que le quisiste decir es otra cosa.
Tal vez que estamos contando propiedades de manera diferente.
¿Acaso la propiedad a la que te referís en tu presentación de la inducción "es una sola"?
No veo por qué mis \(Q(n)\) son infinitas propiedades.
Yo podría decir que estoy probando una propiedad \(Q\)
que para cada natural \(n\) adopta una forma que depende de  \(n\).

En efecto, no debía haber dicho "infinitas propiedades", me refería a que no me parece clarificador que plantees que la inducción consiste en demostrar \( Q(0) \) y \( Q(1) \) y \( Q(2)\ldots \)  Es cierto que lo que estás demostrando significa justo eso, pero precisamente la inducción sirve para reducir la prueba de una conjunción infinita, que no sabemos demostrar directamente, de una vez, tomando un n y probando P(n), a la prueba de dos afirmaciones, P(0) y otra que sí que podemos demostrar de una vez (tomando un n y probando \( P(n) \rightarrow P(n+1) \)).

Lo que digo es que entender eso no consiste en desglosar eso en infinitas afirmaciones y ver cómo podemos convencernos de que las infinitas implicaciones son ciertas, sino más bien en entender que vale P(0) y una única implicación nos asegura que las infinitas afirmaciones P(n) tienen que ser ciertas.

Estoy seguro que la inducción que enunciaste es un esquema del mismo estilo.
Para cada \(n\), el contenido de la "propiedad" en cuestión depende de ese valor de \(n\).
¿Por qué no se puede tomar de la misma manera a lo que llamé \(Q(n)\)?

¿Por qué \(P(n) \equiv [n+3=3+n]\) es "una" propiedad, mientras que \(Q(n)\equiv[(n+3=3+n)\to ((n+1)+3=3+(n+1))]\) serían "infinitas propiedades?

En efecto, no era correcto que dijera ahí "infinitas propiedades", sino que debía haber dicho que estás planteando la inducción como demostrar las infinitas afirmaciones Q(0), Q(1), Q(2)...  pero eso es como plantear una prueba de que todo español es europeo como una prueba de 47 millones de afirmaciones.

La inducción consiste en demostrar infinitas afirmaciones P(0), P(1), P(2)...  que no podemos demostrar una a una, demostrando dos afirmaciones que sí que podemos demostrar de una vez cada una.

De todos modos, no me parece que esa observación marginal sobre cómo concebir la inducción esté entre lo fundamental que he tratado de expresar en los mensajes anteriores. Sólo iba en la línea de que, en mi opinión, todos los análisis que haces y que había puesto en spoiler, no tienen más razón de ser que la vaguedad inherente a los enunciados en términos de propiedades genéricas, pero que no tendrán razón de ser a la hora de justificar cualquier inducción concreta respecto de una propiedad concreta cuyo significado y objetividad no pueda ser cuestionada.

Lo que digo es que mi construcción geométrica (enredosa o no),
le da sentido a cuantificar sobre los naturales y trabajar incluso con infinitas propiedades.
Al final será lo mismo, porque esas infinitas sentencias que indiqué requieren que,
en la práctica, se compruebe que realmente son sentencias.

No digo que no, pero mi problema es: ¿realmente necesitas ninguna construcción para cuantificar sobre los naturales? ¿Qué problema hay en entender lo que significa que todo número natural cumple P(n) (más allá del requisito de que P(n) esté bien definido)? Por ejemplo, si \( P(n) \) es \( 3+n = n+3 \), ¿qué problema hay en entender el significado de que, si te dan un número \( n \), dará lo mismo que calcules \( 3+n \) o que calcules \( n+3 \)? Eso significa que pasará así si \( n = 0 \), y si \( n = 1 \), y si \( n = 2 \), etc. ¿Realmente hace falta aclarar algo ahí?

Hay formas directas de probar eso, según cómo definas la suma, pero si la definimos por recurrencia y entonces hace falta probarlo por inducción, ¿cuál es el problema? Probamos \( 3+0 = 0+3 \) como bien sabes hacerlo, y probamos que si se cumple \( 3+n = n+3 \) entonces \( 3+(n+1) = (n+1)+3 \), como bien sabes hacerlo. ¿Realmente necesitas algo más para concluir que eso vale para todo n que la mera observación de que, de no ser así, podríamos ir recorriendo los números naturales hasta encontrar el primer contraejemplo, y eso es imposible porque no podría ser el 0 y, si fuera un \( n+1 \), el hecho de que \( n \) no sea un contraejemplo implica que \( n+1 \) tampoco lo es?

Nada te impide reestructurar la demostración así:

Supongamos que hay un número natural que no conmuta con \( 3 \), y consideramos el menor de todos. No puede ser \( 0 \), pues sabemos que \( 3+0 = 3 = 0+3 \), luego tendría que ser de la forma \( n+1 \), pero aquí pegamos el razonamiento del paso inductivo y llegamos a una contradicción. ¿Crees que esto, sin más precisión (al margen del razonamiento inductivo que no he detallado porque es de sobra conocido), deja algún resquicio que te pueda hacer dudar de que todos los números naturales conmutan con 3?

Si el problema está en tomar el mínimo, el argumento es: podemos ir recorriendo los números naturales en busca del primero que no conmute con 3. Como suponemos que existe alguno, tarde o temprano encontraremos el primero, y será de la forma \( n+1 \), con \( 3+n = n+3 \), pero \( 3+(n+1) \neq (n+1)+3 \), y eso nos lleva a una contradicción. ¿Qué falta?

Creo haber usado construcciones basadas en la intuición (me cuesta todavía entender qué hago cuando hago eso, pero digamos que he procurado seguir las reglas del juego),
y definiciones claras, sin caer en nada de formalismo alguno.

En tal caso, sería un principio lógico más.

Estoy influenciado por la forma de trabajar formalista, claramente,
pero eso no quiere decir que esa forma general de inducción que pretendí hacer esté mal.
Y que no quiera decir, pues no signfica que de todos modos no esté mal a fin de cuentas,
lo cual es otra historia...  :'( :'( :'(

En ningún momento he dicho que nada de lo que argumentes esté mal, en el sentido de no sea convincente, aunque sospecho que si te aplicara el mismo criterio que aplicas tú, llegaríamos a que tus objeciones fundamentales siguen escondidas en puntos críticos de tus argumentos, de modo que no las has eliminado realmente, sino que las has vuelto más discretas. Por ejemplo, tú mismo admites que la objeción de que no está bien definido que es una propiedad sigue presente en tus planteamientos (aunque yo te digo que eso no tiene importancia). Lo único que digo es que me parece que es matar moscas a cañonazos, que es desarrollar un aparato lógico relativamente sofisticado para acabar justificando algo que es inmediato e irrebatible, al menos si no tratas de rebartirlo en general (donde puedes atacar la vaguedad de los conceptos de "propiedad", "sucesión", etc.) sino que valoras si los procedimientos de razonamiento son convincentes o no en cada caso concreto en el que se aplican.

De todos modos, igual que te he dicho que en varios momentos hemos tocado puntos esenciales, ahora te digo que todo el contenido de este mensaje me parece irrelevante. Mi sensación es que discutir sobre si concebimos el paso inductivo como una afirmación o como infinitas afirmaciones no tiene ninguna trascendencia. No veo mucha diferencia entre "he mostrado cómo trabajar con infinitas afirmaciones" y "es mejor pensar que trabajamos con una única afirmación".

09 Junio, 2023, 01:34 am
Respuesta #23

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Me disculpo por haber deformado la frase, pero total mi perplejidad era la misma.

¿Pero te disculpas en serio? ¿Qué importancia tiene eso?
 

Bueno, es una forma de decir que reconocía ese error,
y de paso aclarar que mantenía la duda de todos modos.




09 Junio, 2023, 01:40 am
Respuesta #24

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
En ningún momento he dicho que nada de lo que argumentes esté mal, en el sentido de no sea convincente, aunque sospecho que si te aplicara el mismo criterio que aplicas tú, llegaríamos a que tus objeciones fundamentales siguen escondidas en puntos críticos de tus argumentos, de modo que no las has eliminado realmente, sino que las has vuelto más discretas.

Que me contradigo es seguro, porque por un lado no me termina de cerrar la forma de trabajar Metamatemáticamente, y por otra parte, cuando parece que entiendo más o menos para dónde va algo, ya me veo haciendo uso y abuso de los recursos disponibles, pero sin haber resuelto mis dudas acerca de los recursos mismos utilizados.

Una ensalada, bah.

09 Junio, 2023, 02:02 am
Respuesta #25

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino

En este mensaje entenderemos que una función \( n \)-ádica \( F \) (donde \( n \) es un número natural no nulo) es cualquier criterio que a \( n \) números naturales \( a_1,\ldots, a_n \), dados en un cierto orden con posibles repeticiones, les asigna un número natural que representaremos por \( F(a_1,\ldots, a_n) \).


Parece que has tenido precaución en no hablar directamente de \(n\)-uplas,
o de que \(F\) asigna valores a elementos del producto cartesiano \(\mathbb N^n\).

Si \(\mathbb N\) se asume/entiende/acepta/visualiza como un conjunto claramente existente en forma objetiva, y lo mismo para cada natural \(n\),
¿no está en el mismo grado de existencia el conjunto \(\mathbb N^n\)?

Podría interpretar que estás preparando las cosas para decir que la función \(F\)
tendrá sentido calcularla sólo cuando sea necesario, y aaparezcan unos números \(a_1,\ldots,a_n\), etc.

Pero aún así la asignación de valores de \(F\) está hecha de antemano para los infinitos naturales, aún cuando pareciera que ese tipo de tareas de infinitos pasos estuvieran tratando de evitarse.

_________

O bien acá la palabra "función" la estás usando en un sentido que no entiendo.

¿Acaso acá las funciones son pensadas como recetas para calcular algo mecánicamente?

Muchas veces hacés mención de cosas que puede calcular una computadora (de esas que no caben en el Universo, pero bueno, si no hay más remedio...).

Esas primeras funciones que se exponen ahí se me ocurre enseguida cómo programarlas
en cualquier lenguaje de programación.
Pero bueno, los lenguajes de programación tienen menos limitaciones que las computadoras, pero aún así hay problemas subyacentes al acecho.







09 Junio, 2023, 02:59 am
Respuesta #26

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • La función monádica \( S \) (o función sucesor) que a cada número natural \( n \) le hace corresponder \( S(n) = n+1 \).

    En estos términos, si representamos por \( 0 \) el número natural cero, los números naturales son

    \( 0, \quad  S(0),  \quad    S(S(0)),  \quad    S(S(S(0))),   \quad   S(S(S(S(0)))),    \quad  \ldots \)

  • La función monádica \( c_0 \) (función cero) que a cada número natural \( n \) le hace corresponder \( c_0(n) = 0 \).

  • Para cada par de números naturales \( 1\leq i\leq n \), la función \( n \)-ádica \( p^n_i \) (la \( i \)-ésima proyección \( n \)-ádica) dada por  \( p^n_i(a_1,\ldots, a_n) = a_i \).

El lector deberá reconocer que no hay ninguna ambigüedad posible en la definición de estas funciones, y que es posible programar a un ordenador para que nos calcule cualquiera de ellas para unos argumentos dados cualesquiera (haciendo abstracción de las posibles limitaciones de memoria del ordenador o del universo).

Que no hay ambigüedad... Pues la función sucesor parece que no tiene ambigüedad alguna, aún si no supiéramos que la sucesión de "siguientes" diera siempre valores distintos.
Basta conque se sepa qué significa el "siguiente de" algo.

Así que más vale tener bien establecido previamente el conjunto \(\mathbb N\) de naturales.

Para programar eso en C:

int S(int n) {
  return n+1;
}


El primer problema que hay acá es que el tipo de datos int tiene un rango predeterminado de valores enteros, de acuerdo a una cantidad fija de bits,
que puede determinarse directamente desde el lenguaje mismo, así:


#include <limits.h>
#define BITS_OF_INT  sizeof(int)*CHAR_BIT


El tipo de datos más grande que permite representar números naturales es uintmax_t.
Pero el problema de la cantidad fija de bits permanece.

Uno puede intentar cambiar de lenguaje, por ejemplo yéndose a Python.
Allí, escribimos simplemente:


def S(n):
  return n+1


La especificación del lenguaje promete que uno puede trabajar con números enteros de cualquier cantidad de dígitos.

Y uno dice, bueno: si la computadora tiene una memoria limitada, el intérprete de Python no podrá trabajar con números arbitrariamente grandes, y se le echa la culpa a esa limitación práctica.

Pero yo digo que muy posiblemente haya problemas en el diseño mismo del intérprete.
No me he metido a ver cómo está diseñada la ingeniería de los números enteros en Python,
pero en principio tengo razones para dudar de que el intérprete trabaje bien,
incluso si le dieran memoria infinita.
El problema que veo es que el intérprete de Python está escrito en lenguaje C.
Para representar un entero grande en Python, se necesita un array de enteros en C, o alguna estructura similar: un array de caracteres, o lo que fuere.
Dicho array puede ser que se cree dinámicamente, es decir, podría crecer su tamaño durante la ejecución del intérprete, según se necesite, y requerir tanta memoria como haga falta.
Pero esto tiene el problema de que las instrucciones en C para reajustar el tamaño de la memoria de un array (la función realloc) admite un parámetro de tamaño, que a su vez es de un tipo de datos entero no negativo (size_t), el cual, de nuevo, tiene un tamaño fijo de bits.

Por lo tanto, el número de bytes de un array, estático o dinámico, estará limitado por el máximo valor entero representable en el tipo de datos size_t.

Entonces uno podría ensayar una solución diferente: no usar arrays,
sino otra estructura de datos, digamos una lista enlazada, tal que cada dígito del entero grande "apunte" al dígito siguiente.

typedef struct numero_grande_type {
      char digito;
      struct numero_grande_type * puntero_al_siguiente_digito;
} numero_grande_type;

Parece que esto ha solucionado el problema, porque ahora cada nuevo nodo de la lista tiene un tamaño pequeño, de unos pocos bytes, o incluso 1 solo byte (para representar un decimal, por ejemplo), y los nuevos dígitos se van requiriendo de a uno, en una larga lista de punteros, que no requieren estar contiguos en memoria (como ocurre con los arrays).
No se necesita asignar de un solo golpe un bloque grande de bytes, y entonces size_t ya no nos molesta con sus limitaciones.

Pero la verdad es que size_t sigue molestando.
Resulta que la especificación del lenguaje C dice que el número de bytes de un tipo de datos se calcula con sizeof(tipo_de_datos), y el resultado es un valor de tipo size_t.
En realidad todo tipo de datos tendrá un número fijo de bytes, pero aquí basta darse cuenta que todo tipo de datos tiene una cantidad de bits acotada por el máximo valor representable en size_t.  [Dicho valor depende de la época, pero en nuestros días podría rondar en \(2^{32}-1\) o \(2^{64}-1\).

¿Cómo limita esto a una lista enlazada, o cualquier otra estructura de datos flexible?
Bueno, pues resulta que una lista enlazada es una estructura recursiva,
que contiene un campo de datos (que usaríamos para almacenar uno de los dígitos de nuestro entero gigantesco), y otro campo de datos tipo puntero, que apunta al siguiente elemento de la lista.

Ese puntero  tiene un tipo de datos, digamos puntero a un nodo de la lista,
que entonces tiene también un tamaño fijo de bits.
Si bien no hay reglas concretas que digan cómo se codifica la información de las posiciones de memoria en un puntero,
hay algo cierto de todos modos, y es que el número de direcciones de memoria distintas representables por un tipo de datos puntero será finito.

Así que, yo me pregunto. Los intérpretes de Python, ¿han tenido en cuenta esa limitación a la hora de representar direcciones de memoria en C?
Imagino que lidiar con eso debe ser algo engorroso.
Usar un lenguaje distinto al C para esquivar este problema no sé si sea una solución,
o si en el fondo será sólo postergar el mismo problema.
De hecho, no parece que tenga sentido práctico tener que lidiar con mas de \(2^{32}\) decimales en nuestros días, así que dudo mucho que los desarrolladores se hayan puesto a tener que lidiar con eso.
Y menos ganas le habrán de echar al ver que no hay máquina que disponga de tanta memoria que valga la pena el esfuerzo de semejante generalidad.

La cuestión es que tendrían que poder manejar direcciones de memoria que puedan ellas mismas poder representar información (esto es: una posición de memoria específica) de tamaño variable.
Parece ser que el problema se empieza a morder su propia cola.

No es que no tenga solución.
Lo que digo es que sospecho que posiblemente nadie se ha tomado el trabajo de hacerlo del todo bien.
Pero tengo que reconocer que no estoy 100% seguro de esto, pues tendría que analizar el código fuente de aquellos intérpretes de lenguajes que aseguran manejar números enteros de tamaño arbitrario.

Ahora bien. Que un intérprete tenga un diseño defectuoso, no significa que el lenguaje de programación que intenta interpretar lo sea,
y en ese caso la especificación del lenguaje se podría aceptar al menos como un ideal, en forma abstracta.
Pero lo que sospecho es que las limitaciones prácticas de implementar un intérprete en la vida real sean acaso un indicio, un síntoma, de que no es posible aterrizar ese lenguaje en un intérprete real, aún si le prometerian memoria infinita.
No lo afirmo categóricamente, porque también sospecho lo contrario.  8^)

09 Junio, 2023, 11:59 am
Respuesta #27

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Que me contradigo es seguro, porque por un lado no me termina de cerrar la forma de trabajar Metamatemáticamente, y por otra parte, cuando parece que entiendo más o menos para dónde va algo, ya me veo haciendo uso y abuso de los recursos disponibles, pero sin haber resuelto mis dudas acerca de los recursos mismos utilizados.

Yo insisto en que no se trata de "justificar recursos en general" para luego usarlos sin pensar con la tranquilidad de que ya están justificados, porque todo intento de justificarlos en general tropezará con el problema de que tendrías que hablar de "propiedades genéricas", de "funciones genéricas", de "conjuntos genéricos" y no podemos desarrollar una teoría coherente sobre estas cosas genéricas.

La forma de trabajar es describir estrategias que pueden dar lugar a razonamientos concluyentes (sin tratar de justificar en general que realmente serán concluyentes) y comprobar en cada caso, cuando no hay duda de que estás tratando con propiedades bien definidas, con funciones bien definidas, con conjuntos bien definidos, etc., que el razonamiento que obtienes es realmente concluyente.

Otra cosa es que, cuando ya has comprobado dos o tres veces que, por ejemplo, el razonamiento por inducción es concluyente en dos o tres casos en los que tenías propiedades claramente objetivas y bien definidas, al final apliques mecánicamente la inducción porque no te cabe duda de que, si te paras a pensar si está bien aplicada (es decir, que te da un argumento concluyente), vas a concluir que sí.

Parece que has tenido precaución en no hablar directamente de \(n\)-uplas,
o de que \(F\) asigna valores a elementos del producto cartesiano \(\mathbb N^n\).

Si \(\mathbb N\) se asume/entiende/acepta/visualiza como un conjunto claramente existente en forma objetiva, y lo mismo para cada natural \(n\),
¿no está en el mismo grado de existencia el conjunto \(\mathbb N^n\)?

En efecto, he evitado el uso de \( \mathbb N^n \) o de n-tuplas, pero no por razones técnicas, ya que, como tú muy bien dices, no hay ningún problema en hablar de \( \mathbb N^n \) o de n-tuplas igual que hablamos de \( \mathbb N \).

Lo he evitado por razones "estéticas" o, mejor, psicológicas. Entiendo que esto:

Una función \( n \)-ádica \( F \) (donde \( n \) es un número natural no nulo) es cualquier criterio que a \( n \) números naturales \( a_1,\ldots, a_n \), dados en un cierto orden con posibles repeticiones, les asigna un número natural que representaremos por \( F(a_1,\ldots, a_n) \).

y esto:

Citar
Una función \( n \)-ádica \( F \) (donde \( n \) es un número natural no nulo) es cualquier criterio que a cada \( n \)-tupla \( (a_1,\ldots, a_n)\in \mathbb N^n \) le asigna un número natural que representaremos por \( F(a_1,\ldots, a_n) \).

son dos párrafos que contienen exactamente la misma información, son igualmente precisos y rigurosos, con la única ventaja a favor del primero de que es autocontenido, que explicita la importancia del orden de los argumentos, mientras que el segundo requiere referirse a una definición previa de n-tupla en la que figure dicho requisito.

La razón (psicológica, o didáctica) por la que prefiero la primera redacción a la segunda, aunque son equivalentes, es porque la segunda suena pseudoformal, la segunda imita inútilmente el lenguaje de la teoría de conjuntos formal, y eso puede inducir a equívocos, esencialmente a pensar que algo es más riguroso cuando está expresado en términos más parecidos a los que emplea la teoría de conjuntos formal.

La teoría de conjuntos formal, además de dar rigor a los razonamientos que usan conceptos abstractos de los que la intuición no puede dar cuenta, exige una serie de requisitos puramente "burocráticos", "técnicos", que no contribuyen en nada al rigor de la exposición, sino que sirven meramente para que todo se reduzca a unos axiomas lo más simples posibles, lo que requiere, en particular, que todo sean conjuntos y, más aún, conjuntos concretos.

Por ejemplo, las funciones tienen que ser conjuntos de n-tuplas (lo cual es artificial: cualquier niño sabe sumar y no piensa en conjuntos de ternas \( (a, b, a+b) \), sin que eso pueda interpretarse como que no sabe lo que hace), y las n-tuplas han de ser ciertos conjuntos, lo que hace conveniente hablar del conjunto \( \mathbb N^n \), pero todo eso son puros tecnicismos que no tienen más finalidad que poder decir que en la teoría de conjuntos todo es un conjunto.

Otros ejemplos de tales tecnicismos son definir \( 3 = \{0,1,2\} \). Eso es una "mentira inocua", en el sentido de que no es cierto que el número natural 3 sea ningún conjunto, puesto que alguien puede dominar los números naturales y su aritmética sin pensar en ningún momento en el 3 como un conjunto, y si a alguien así le dices que, aunque no lo sepa, \( 3 = \{0,1,2\} \), te responderá —con razón— "porque tú lo digas". No obstante, es una mentira inocua porque uno puede adoptar ese convenio y coincidir con alguien que no lo adopte en todos los hechos significativos sobre los números naturales, como que \( 3+2=5 \). Si dos personas coinciden en eso, no importa nada que uno considere que eso es una igualdad entre conjuntos y otro considere que eso sólo indica que si ponemos dos palitos al lado de tres palitos habrá cinco palitos.

Así, prefiero decir que una función n-ádica es un criterio que a cada n números naturales (repetidos o no y en un orden fijado) les asigna una imagen, porque eso es exactamente lo que es una función, sin ningún aditivo burocrático de los que impone la teoría de conjuntos, no para dar rigor al concepto, sino para reducirlo a los meros conceptos de conjunto y pertenencia.

Usar jerga conjuntista cuando no hace ninguna falta me parece como ir con traje de chaqueta y corbata a una excursión a la montaña. Es seguir unas normas de etiqueta en un contexto en el que no hay ninguna razón para seguirlas, y el mero hecho de seguirlas se puede interpretar como una excentricidad (en el caso del traje de chaqueta) o simplemente como una concepción errónea de lo que exige el rigor matemático.

Por ejemplo, eso se aplica también al requisito burocrático conjuntista de que los números enteros sean clases de equivalencia de pares de números naturales, o que los números reales sean clases de sucesiones de Cauchy o cortaduras, etc. Todo eso son mentiras inocuas que la teoría de conjuntos incorpora, no por rigor, sino por simplicidad técnica (para reducir al mínimo los axiomas necesarios).

Y eso tiene que ver con tus intentos de identificar los números naturales con algo en concreto (como puntos en un segmento). Es una mentira inocua que puedes adoptar si te lo propones, pero decir que el 3 es un punto de un segmento es tan falso como decir que \( 3 = \{0,1,2\} \) o decir que una función es un conjunto de pares ordenados. En realidad, los números naturales son un concepto abstracto que puedes representar de muchas formas, igual que un "juego de ajedrez" es un concepto abstracto que puedes materializar en muchos tableros físicos, o diagramas en un papel, sin que puedas decir que ningún juego de fichas son "las fichas de verdad" y todas las demás son copias isomorfas.

Los números naturales los puedes visualizar como puntos, como palitos, como campanadas, o como ovejitas saltando al redil, pero no tiene sentido decir que ninguna de esas representaciones te proporciona "los números de verdad". Si quieres ceñirte a lo que realmente hay en el concepto de "número natural", no puedes identificarlos con nada en concreto, sino que tienes que admitir que el cero no es nada en particular y que el siguiente de un número no es nada en particular, sino un concepto abstracto como "perro", que puede aplicarse a una gran variedad de perros. Igual que si ves un cierto bicho puedes decir "esto puede describirse como un perro", si ves ciertas sucesiones puedes decir "esta sucesión puede describirse como una representación de los números naturales", sin que tenga sentido buscar "los verdaderos números naturales" igual que no tiene sentido buscar "el perro verdadero". Insisto, no obstante, en que si prefieres decir "para mí los números naturales son estos puntitos", no hay ningún inconveniente, más allá de que no puedes pretender que otros coincidan contigo en eso, pero mientras eso te lleve a afirmar sin dudarlo que hay un primer número "cero", que todo número tiene un siguiente y que no hay números no invitados a la fiesta, a nadie le importará que prefieras verlos como puntitos o como campanadas o como nada (que es lo que realmente son).

Bueno, me he ido un poco por las ramas, pero era algo que me había quedado en el tintero en mis respuestas anteriores  ;D

Pero sí que me parece interesante destacar mi opinión de que imitar el lenguaje conjuntista no aporta nada en teoría y me chirría en la práctica, porque induce a pensar que algo irrelevante es importante.

Podría interpretar que estás preparando las cosas para decir que la función \(F\)
tendrá sentido calcularla sólo cuando sea necesario, y aaparezcan unos números \(a_1,\ldots,a_n\), etc.

Pero aún así la asignación de valores de \(F\) está hecha de antemano para los infinitos naturales, aún cuando pareciera que ese tipo de tareas de infinitos pasos estuvieran tratando de evitarse.

No, no estaba pensando nada de eso, pero, puestos a opinar, no creo que la definición de función diga nada sobre si las funciones "están ya calculadas" o si "son cosas que se pueden calcular cuando haga falta". Eso dependerá de la filosofía de la matemática de cada cual, y no creo que afecte a nada en la práctica, en el sentido de que dos personas pueden tener filosofías distintas y coincidir en todos los hechos relevantes.

Por ejemplo, no veo en qué influye que uno piense que todas las sumas "están ya calculadas" o que las sumas "se pueden calcular siempre que haga falta". Ambos tendrán que coincidir en que \( x+y = y+x \), ya sea pensando en que eso se cumple en las infinitas sumas "ya calculadas" o que eso se cumplirá siempre que calculemos dos sumas que difieran sólo en el orden de los sumandos. Pensarlo de una forma o de otra queda para la intimidad de cada cual. Lo importante es que no haya discrepancia en que la suma es conmutativa.

O bien acá la palabra "función" la estás usando en un sentido que no entiendo.

¿Acaso acá las funciones son pensadas como recetas para calcular algo mecánicamente?

Pues... no sé en qué podríamos diferir sobre lo que es una función. Si a cada n números en un cierto orden, con posibles repeticiones les podemos asignar otro de forma objetiva, eso es una función.

No obstante, para lo que necesitamos en el hilo, y en particular en la respuesta #2, sólo vamos a tratar con funciones recursivas primitivas, todas las cuales se pueden calcular mecánicamente, luego no pasa nada si restringimos el concepto de función exigiendo que el criterio sea explícito y corresponda con un cálculo que se pueda hacer siempre en la práctica.

Muchas veces hacés mención de cosas que puede calcular una computadora (de esas que no caben en el Universo, pero bueno, si no hay más remedio...).

Es una forma de que no haya duda de que estamos hablando de algo concreto y sin ambigüedades.

Esas primeras funciones que se exponen ahí se me ocurre enseguida cómo programarlas
en cualquier lenguaje de programación.
Pero bueno, los lenguajes de programación tienen menos limitaciones que las computadoras, pero aún así hay problemas subyacentes al acecho.

No copio todo lo que pones en el mensaje siguiente sobre cómo programar la función sucesor, pero, digo yo, en lugar de pelearte con los intestinos de Python o C, ¿no te vale con que una máquina de Turing puede calcular trivialmente la función S?

Esto esta mal
Es muy fácil programarla para que si le das como argumento un número, por ejemplo \( a = 5 \), así:

\( 111111\underline1 \),

donde el subrayado indica la casilla de la cinta que leerá la máquina cuando empiece, la máquina se detenga así:

\( 1111111\underline1 \).

El programa consiste únicamente en que se mueva una casilla a la derecha e imprima un 1. Fin.

Ese programa está calculando la función sucesor.
[cerrar]

Lo anterior (que he puesto en spoiler) está mal. Véase la Respuesta #38

La cuestión sobre tu lectura de la respuesta #2 es si admites que el concepto de "función recursiva primitiva" está bien definido, que está bien claro lo que significa que una función es recursiva primitiva y, en particular, que toda función recursiva primitiva puede calcularse mediante un ordenador para cualesquiera argumentos dados, haciendo abstracción de limitaciones de memoria.

10 Junio, 2023, 02:29 am
Respuesta #28

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
No copio todo lo que pones en el mensaje siguiente sobre cómo programar la función sucesor, pero, digo yo, en lugar de pelearte con los intestinos de Python o C, ¿no te vale con que una máquina de Turing puede calcular trivialmente la función S?

Es muy fácil programarla para que si le das como argumento un número, por ejemplo \( a = 5 \), así:

\( 111111\underline1 \),

donde el subrayado indica la casilla de la cinta que leerá la máquina cuando empiece, la máquina se detenga así:

\( 1111111\underline1 \).

El programa consiste únicamente en que se mueva una casilla a la derecha e imprima un 1. Fin.

Ese programa está calculando la función sucesor.


Y bueno, con la computadora imaginaria siempre es todo más fácil.  :P

Sí, tras postear mi mensaje me dí cuenta que podía haber nombrado la máquina de Turing,
pero no agregué ninguna aclaración, y además no es una máquina real.
Es un mecanismo imaginario, más complicado que lo que se está queriendo representar con eso.

Discusión aparte, para mí, la estructura de la cinta de la máquina de Turing es la que mejor refleja la estructura mental subyacente de los números naturales.
Esa estructura "espacial" (que mantiene "pegado", "conectado", cada casillero con su siguiente y también con el anterior) me da una imagen más nítida del pensamiento secuencial necesario para concebir los naturales.
Salvo los duendes del cuento del Argentinator feliz, lo demás me funciona mejor que cualquier otra "sucesión" que pretenda ser la de naturales.

No sé si logro explicarme. Sospecho que sin esa intuición espacial, sería inconcebible pensar en los números naturales, o mejor dicho, que todo recorrido secuencial tiene soporte geométrico en algo como dicha cinta.

Para mí es clave que sea posible "imprimir" una cierta información y dejarla "memorizada" en cierto casillero de esa cinta. De lo contrario, el intento de volver atrás, por ejemplo, buscando encontrar elementos anteriores de una sucesión, se volvería una acción confusa o borrosa.

____________________________________________

El inconveniente que ví en esto es que cuando invitás al lector a hacer un programa en la computadora para comprobar que todo funciona de forma concreta,
lo que digo es que eso no es así.
Algo tan sencillo como sumar un 1 a un número natural es algo que puede tener problemas de implementación complejos, aún cuando se lleve a cabo el programa bajo la hipótesis de que durante la ejecución no habrá limitaciones de memoria.

Si en vez de usar dígitos, como hice yo, uno simplemente usa "concatenación de caracteres con forma de palitos": |||||||||,
y sumar 1 lo implemente como agregar un palito a la cadena,
hacer operaciones aritméticas con eso será más ineficiente a la larga,
aunque implementar la operación "siguiente de" es tan sencillo como agregar un palito.

________________

Pero bueno, creo que es interesante tratar de aprender algo nuevo, no sólo pelearse con la vida.

Así que aquí va mi intento de programa con la máquina de Turing.

Me molestan las máquinas de Turing que no tienen un casillero inicial.
Así que de izquierda a derecha dispondré las casillas, a partir de un casillero inicial.

Asumo el alfabeto: { 1 } (el caracter "uno").
También denotaré con 0 a la casilal en blanco (para hacerla un poco más visible).
Considero el estado Q1 como activo y Q0 como el estado terminal y pasivo.

Al iniciar, el cabezal de impresión está parado sobre un casillero de la cinta.
Tiene permitido imprimir un caracter del alfabeto, o borrar lo que esté impreso.
Luego, tiene permitido mover el cabezal a Izquierda (I), Derecha (D), o Centro (C, quedarse quieto).
El estado puede cambiar a otro estado activo o a un estado pasivo.

El algoritmo A sería éste:

__ Si la máquina está en el estado activo Q1 (el único posible en este caso), entonces
________ Si el casillero actual está en blanco (0):
________________ Mover hacia C (quietud), imprimir 1, y cambiar el estado a Q0.
________ Si el casillero actual tiene un (1):
________________ Mover hacia D, imprimir 1, cambiar el estado a Q0.


Espero haberlo hecho bien.

Y si no, pues estoy abierto a recibir los castigos correspnodientes.

En tal caso sería mi primer programa de Turing.

Y si ese es el programa de la función "siguiente", pues tengo algunas moscas que me dan vueltas en la mente...


10 Junio, 2023, 11:36 am
Respuesta #29

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos. Paso por aquí principalmente a saludar y a decir que, aunque últimamente estoy participando poco en el foro (mucho trabajo), seguí con interés el hilo de la inducción hasta \( \epsilon_0 \), y estoy siguiendo este nuevo hilo de la aritmética primitiva recursiva.

Me ha llamado bastante la atención esto:
De hecho, existe una teoría más débil que ARP, conocida como la Aritmética de las Funciones Elementales  que es como ARP, pero con funtores únicamente para la suma, el producto y la exponenciación, y la "Gran Conjetura de Friedman" afirma, más o menos, que cualquier teorema con enunciado puramente aritmético, y no diseñado con mala idea para que no sea así, es demostrable en AFE. En particular, la conjetura afirma que el Último Teorema de Fermat tiene que ser demostrable en AFE, luego, en particular, en ARP, aunque nadie ha probado que sea así.
No estoy familiarizado con AFE pero parece una teoría extremadamente débil. Entiendo que la idea de Friedman debe ser que, de todos los usos de argumentos generales sofisticados en la demostración del UTF (p.ej. la maquinaria de geometría algebraica) y que claramente no son formalizables en AFE, se pueden extraer y formalizar los argumentos concretos que se necesitan en la demostración y probarlos en AFE. Si es así me parece una idea interesante, pero soy un tanto escéptico al respecto. Sí lo veo bastante más plausible en PA.

Ahora un poco de "off-topic" sobre las cuestiones de implementación real de la función sucesor.
Y bueno, con la computadora imaginaria siempre es todo más fácil.  :P

Sí, tras postear mi mensaje me dí cuenta que podía haber nombrado la máquina de Turing,
pero no agregué ninguna aclaración, y además no es una máquina real.
Es un mecanismo imaginario, más complicado que lo que se está queriendo representar con eso.
No es tan imaginaria, hay gente que se ha dedicado a construir alguna real (a efectos demostrativos). Mira por ejemplo: https://spectrum.ieee.org/032610-diy-turing-machine

De todas maneras, para calcular la función sucesor en la realidad, una máquina de Turing sigue siendo matar moscas a cañonazos. Si sabes algo de electrónica digital es bastante sencillo diseñar e implementar en la realidad un autómata finito que te calcule la función sucesor de un número. Y ahí sí que realmente solo estás limitado por la "memoria" (y las limitaciones físicas inherentes a la electrónica y los semiconductores, que es una cosa que se suele obviar).

La implementación de Python de los enteros de longitud arbitraria es un tema muy interesante. Hay sitios en internet donde lo explica muy bien. Básicamente por lo que entendí la idea es expresar un número entero en base \( 2^{30} \), \( n=\sum_{k=0}^N a_k(2^{30})^k \), y almacenar los dígitos \( a_k \) en un array. Como cada palabra del computador tiene \( 32 \) o \( 64 \) bits, puedes almacenar ahí cada dígito, y puedes tener un array de hasta el máximo del tipo size_t. En efecto, ese máximo será \( 2^{64}-1 \), en un procesador de \( 64 \) bits. Pero esto es consecuencia de la arquitectura de Von Neumann de los ordenadores actuales, no de ningún problema fundamental a la hora de diseñar un sistema electrónico que calculé el sucesor (que como digo te puedes hacer uno en casa con electrónica digital sin demasiados problemas).

Lo que sucede es que en un programa los datos de las variables se guardan en memoria RAM, y el máximo de posiciones direccionables en memoria usando palabras de \( 64 \) bits es \( 2^{64} \) (en realidad son menos, pero es una cota superior). Entonces, si quieres usar la implementación de Python, conforme aumentas la memoria RAM tendrías que ir cambiando también la arquitectura del procesador para que use palabras con longitud mayor (por ejemplo, \( 128 \) bits) y por tanto pueda direccionar más RAM.

Pero hay otras formas de hacer esto. Por ejemplo, podrías ir guardando el número en un disco duro en lugar de en memoria RAM, con lo que tienes muchísima más capacidad de almacenamiento. O podrías usar varios ordenadores en red, de manera que "añadir" más memoria significaría "añadir más ordenadores" que fueran capaces de acceder a más memoria (que es el camino que se emplea para tratar con datos masivos).

En resumen, que las complicaciones son más de carácter técnico que filosófico. No hay ningún problema real en guardar números grandes y calcular el siguiente, más allá de que la arquitectura de los ordenadores es como es, por motivos de versatilidad y de eficiencia. Pero aún con los ordenadores actuales hay muchas soluciones que realmente solo requieren añadir "más memoria".

La ecuación más bonita de las matemáticas: \( d^2=0 \)