Re: RUBIK Infinito

Posted by RUBIK Transfinito on Dic 25, 2012; 3:32pm
URL: http://foro-crashoil.109.s1.nabble.com/RUBIK-Infinito-tp14p33.html

Estoy de acuerdo con ORA:CLE:

La indecidibilidad no puede tener que ver con la verdad o falsedad; de hecho, en el caso de que una proposición *fuera* FALSA, sería decidible mediante la simple exhibición de un CONTRAEJEMPLO, cosa que zanjaría la cuestión.

Visto así, para que algo sea *indecidible* tiene que ser que no podemos construir desde axiomas más simples (más simples que la "verdad" que tratamos de demostrar) una CADENA DE ARGUMENTOS que nos lleven a la conclusión a la que "apuntamos".

Como casos particulares de esto podríamos pensar en el "problema de la detención": el si un programa de ordenador en particular se detendrá alguna vez o no. En principio, si esperamos lo suficiente y se detiene, la cuestión en particular (para el "programa" estudiado) está *decidida*. Pero si no podemos deducir de la estructura del programa el hecho de si va a pararse alguna vez o no, y si además resulta que *realmente* podría funcionar indefinidamente sin detenerse, ENTONCES nos hallamos ante una pregunta indecidible: no tenemos manera de saber categóricamente cuál de las dos alternativas es la correcta.

Naturalmente, muchas cuestiones matemáticas pueden formularse en términos de si un programa funcionando en un ordenador "abstracto" se parará alguna vez o no. Creo que este enfoque fue uno de los que usaron Turing y otros (Gödel) en ocasiones para abordar algunos problemas de este tipo.


Sobre afirmaciones que sean NI-CIERTAS-NI-FALSAS no tengo ejemplos ahora. Cuando he escrito antes lo del Quinto Postulado, había pensado también en la Hipótesis del Continuo, que creo que se puede tomar a voluntad como cierta o falsa y aun así producir Teorías de Conjuntos consistentes (igual que pasa con las Geometrías No Euclídeas "pero" aun así consistentes). Claramente, en esos casos lo que pasa es que no podemos hablar de que el Quinto Postulado (o, menos intuitivamente la Hipótesis del Continuo) de "Verdad" o "Falsedad". En realidad, acabamos alejándonos tanto de la experiencia sensorial, que los axiomas empiezan a ser constructos con un cierto "algo" arbitrario en su esencia. Ya no se trata de "verdadero o falso", sino de no en contradicciones lógicas.


Un ejemplo que creo que leí una vez (de una supuesta cuestión que podría ser ni-cierta-ni-falsa y por ello escapar a la "ley de tercio excluso") fue el SI EN EL DESARROLLO DECIMAL DE PI APARECEN ALGUNA VEZ UN TRILLÓN DE 1s CONSECUTIVOS. Naturalmente, este ejemplo de pregunta se planteaba de manera puramente conjetural, junto con también -creo recordar- la Conjetura de Goldbach. En realidad, los ejemplos están bastante mal escogidos, pues probablemente (en mi *opinión*, basada en pura intuición) ambas cuestiones se pueden responder afirmativamente:


SÍ que aparecen alguna vez un trillón de 1s seguidos en el desarollo decimal de PI (asumo que PI es "normal", cosa que creo que aun no está demostrada pero que "parece" cierta)

y

SÍ que es cierta la Conjetura de Goldbach: ella misma no ha sido probada, pero sí que se han demostrado resultados muy próximos. Me parece que uno es que todo número par es descomponible como suma de un número primo y otro que es producto de a lo sumo unos pocos (¿dos?, ¿seis?, no recuerdo) números primos. Creo que un matemático chino llamado Chen Jing Run fue el autor de la prueba de esta "Conjetura de Goldbach reducida".




Interesante. ¿Tienes algún enlace a la demostración?


-> ¿A qué demostracíon ...? Entiendo que se puede referir a DOS:


PRIMERA

La de que una biyección entre espacios de dimensiones distintas no puede ser continua es inmediata:


Si la dimension es igual, basta con trucos geométricos simples:

*** Es fácil poner en correspondencia biunívoca los puntos de dos segmentos "haciéndoles el Teorema de Thales": los hacemos surgir de un origen común en el plano (sin que sean colineales, i.e. con orientaciones distintas), unimos los otros dos extremos con una línea y, trazando paralelas a ésta, biyectamos un segmento sobre el otro.

*** Es fácil biyectar un segmento sobre el semieje real usando la función 1/x o variantes.

*** Podemos biyectar una esfera (salvo el "polo norte") sobre un plano infinito mediante una línea que surja del "polo norte", atraviese la esfera en el punto que queremos proyectar, y toque al plano en un punto dado (ese es el "emparejamiento"). Esta transformación tiene un nombre técnico que no recuerdo ahora mismo.

etc.

Todo esto era continuo.


Para hacer una biyección entre puntos de espacios distintos, podemos usar directamente las coordenadas de los puntos. Por ejemplo (y SIN PÉRDIDA DE GENERALIDAD), para biyectar un segmento unitario sobre un cuadrado de lado unidad, podemos coger un punto del segmento, el PUNTO de coordenada 0.abcdefghijk... [expresión decimal]  y hacerle corresponder en el cuadrado otro punto con las coordenadas

0.acegik ... [dígitos que ocupan los sitios impares]

0.bdfhj ... [dígitos que ocupan los sitios pares]


Que esto no puede ser continuo se ve trazando dentro del cuadrado dos segmetos curvilíneos arbitrarios y que se intersecten en por lo menos un punto ... Evidentemente, cada segmento curvilíneo, si la biyección entre espacios era continua, ha de corresponder a un "microsegmento" dentro del segmento unitario que constituía el dominio original. PERO el punto de intersección de los segmentos curvilíneos ha de tener como antiimagen un punto que ha de estar en uno u otro de dos "microsegmentos" antiimagen que en principio no podían tener solapamientos. Esto nos lleva a un ABSURDO que reduce a falsa la afirmación original: la suposición de que podía ser continua una tal biyección entre espacios de dimensiones distintas. Este método se puede extender sin pérdida de generalidad.


SEGUNDA

Lo del Teorema de Shannon:

Hay una demostracíon completa en su inmortal obra:

The Mathematical Theory of Communication


Y la misma desmostración está más desglosada y explicada (consiguiendo más "intuibilidad" a costa de una ligera pérdida de rigor) en

An Introduction to Information Theory: Symbols, Signals and Noise, de John R. Pierce


No tengo un enlace a versiones online de las demostraciones.