Autor Tema: Cómo encajar la sentencia INCOMPLETABLE de Gödel en un marco realm. consisten

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

21 Julio, 2020, 04:52 pm
Respuesta #10

Elius

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
En resumen, mi problema es más "filosófico" que matemático. Lo que dudo, al margen de la corrección técnica del argumento, es que la idea general sea satisfactoria.
No creo de ninguna manera que el teorema de incompletitud sea intrascendente. Aún mirándolo como una especie de nueva y sofisticadísima paradoja, hay que pensar que las paradojas de Zenón de Elea tuvieron de la cabeza a filósofos y matemáticos durante más de 2000 años. Sólo se resolvió su misterio cuando aparecieron las teorías sobre las series infinitas en el siglo XIX.
Lo que intento mostrar es algo más amplio que lo que se ve en el artículo, y es lo siguiente: el teorema de incompletitud es el predecesor, y en cierto modo equivalente al teorema de la irresolubilidad del Halting Problem de Turing. Este último trata sobre sus máquinas virtuales, Gödel sobre las funciones recursivas. Incluso hay teoremas donde está muy clara esa similitud, ver Mendelson (4ta. ed.), pág. 325 en adelante, "Unsolvable Problems". Se trata de una anomalía del sistema formal para tratar las funciones recursivas, especialmente con respecto a los desarrollos infinitos y la circularidad. El sistema falla porque la sentencia indecidible es incompletable, como la máquina universal de Turing falla en detectar auto-referencia y circularidad. No hay una sentencia "correcta" que el sistema no puede catalogar como teorema o anti teorema, de la misma manera que en Turing no hay una máquina "correcta" que la máquina universal no catalogue. Es en las máquinas anómalas donde falla.

 

21 Julio, 2020, 07:53 pm
Respuesta #11

geómetracat

  • Moderador Global
  • Mensajes: 1,892
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sí, todos los resultados estos están bastante relacionados. Una manera general de verlo es que existen conjuntos recursivamente enumerables que no son recursivos. En efecto, el problema de la parada de Turing te dice que el conjunto de (números de) máquinas de Turing \( M_n \) para las que \( M_n(n) \) para no es recursivo (pero sí recursivamente enumerable: basta con ejecutar la máquina). De manera similar, la incompletitud de sistemas formales está relacionada con que el conjunto de números de sentencias demostrables en un sistema axiomático no es recursivo (pero sí recursivamente enumerable).

De hecho, ahora me he dado cuenta del siguiente argumento que implica que la clase de sentencias que son indecidibles en el sistema axiomático (no son ni demostrables ni refutables) no puede ser recursiva. Es decir, no puede haber ningún algoritmo que te diga si una fórmula es indecidible o no. En efecto, si existiera tal algoritmo existiría un algoritmo para saber qué sentencias son demostrables, que ya sabemos que no existe. Dada una sentencia cualquiera basta ejecutar el primer algoritmo para ver si es indecidible o no, y si sale que no es indecidible te basta con ir enumerando los teoremas del sistema axiomático hasta que salga la sentencia o su negación (una de las dos debe salir seguro porque sabes que no es indecidible).

Es un argumento interesante porque aunque no desmonta del todo lo que pretendes hacer sí muestra sus límites. Si das un criterio cualquiera comprobable algorítmicamente de fórmula "mala" que intente capturar las sentencias indecidibles, como tu noción de fórmula incompletable, o bien va a haber fórmulas indecidibles que no son "malas" o bien va a haber fórmulas "malas" que son decidibles.

Algo parecido se aplica a lo que dices al final sobre máquinas de Turing. La cuestión es que no hay un criterio operativo que te permita decidir si una máquina es "correcta" o "anómala".
La ecuación más bonita de las matemáticas: \( d^2=0 \)

21 Julio, 2020, 10:39 pm
Respuesta #12

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,051
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Qué interesante debate están armando :aplauso: :aplauso:. Vaya por delante que mezcla distintas ramas de la matemática y computación, lo cual hace que sea más que interesante.

Tengo una duda más bien básica, espero que puedan entenderla. Cuando hablan de "Puedes programar a un ordenador para que haga tal demostración", ¿se debe interpretar metafóricamente o literalmente?

Porque claro, nunca estuve en contacto con un algoritmo así pero ni de cerca (a duras penas puedo entender los algoritmos de ordenación como bubble sort, entre otros), pero claro, ¿cómo se determina el tiempo computacional? ¿Cuáles son las entradas y qué se espera por salida? ¿Se tratan de algoritmos teóricos (de ahí su "tiempo computacional exponencial/polinomial/logarítmico") o ya están puestos en marcha?

Saludos

22 Julio, 2020, 12:31 am
Respuesta #13

geómetracat

  • Moderador Global
  • Mensajes: 1,892
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Tengo una duda más bien básica, espero que puedan entenderla. Cuando hablan de "Puedes programar a un ordenador para que haga tal demostración", ¿se debe interpretar metafóricamente o literalmente?

Bueno, lo que dije es que puedes programar un ordenador para comprobar tal demostración. Hablaba metafóricamente, pero realmente puedes programarlo si quieres, no debería ser muy difícil. A lo que me refería es que si me das una demostración en el sistema formal de \( G \) puedo decirte como alargarla hasta la demostración de una contradicción.

Citar
Porque claro, nunca estuve en contacto con un algoritmo así pero ni de cerca (a duras penas puedo entender los algoritmos de ordenación como bubble sort, entre otros), pero claro, ¿cómo se determina el tiempo computacional? ¿Cuáles son las entradas y qué se espera por salida? ¿Se tratan de algoritmos teóricos (de ahí su "tiempo computacional exponencial/polinomial/logarítmico") o ya están puestos en marcha?
Todos los algoritmos de los que he hablado en el último mensaje son teóricos. Es decir, lo único que me interesa es si existe o no un algoritmo para resolver un problema determinado, no me importa su complejidad, podría tardar más tiempo que la edad del universo.

Hay varios niveles de análisis de algoritmos. El más general es el que corresponde a la teoría de la recursión (o teoría de la computabilidad). Esta teoría se preocupa (al menos en primer instancia) de determinar los problemas que son resolubles algorítmicamente y los que no, sin preocuparse por el tiempo de ejecución, limitaciones de memoria o detalles de implementación. Es lo que es teóricamente posible, disponiendo de tiempo y memoria infinitos.
Un segundo nivel corresponde a la teoría de la complejidad. Esta estudia clases de complejidad computacional de algoritmos atendiendo al tiempo necesario de ejecución o al espacio necesario, pero siempre a "gran escala". Por ejemplo, estudia las clases P, NP, etc. Pero no se preocupa de encontrar cotas precisas, da igual que un algoritmo sea \( O(n^2) \) o \( O(n^3) \), basta con que sea computable en tiempo polinomial.
Por último está la algorítmia o el análisis de algoritmos, que se dedica a encontrar los mejores algoritmos posibles para resolver un problema y a encontrar cotas (si puede ser óptimas) sobre el tiempo de ejecución. Aquí es donde entran los algoritmos de ordenación y sus cotas que mencionas.

Pero como ya he dicho, a efectos lógicos solamente importa el primer nivel (si algo es resoluble algorítmicamente o no).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

23 Julio, 2020, 01:42 am
Respuesta #14

Elius

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
Tengo una duda más bien básica, espero que puedan entenderla. Cuando hablan de "Puedes programar a un ordenador para que haga tal demostración", ¿se debe interpretar metafóricamente o literalmente?
Hola, manooooh.
Hay muchos algoritmos, de dos tipos: verificadores de demostraciones, y los que intentan encontrar una demostración. Por supuesto, el "demostrador" siempre tiene que estar complementado por un verificador.
Los verificadores son muy buenos. Pero los "demostradores" no son muy eficaces, porque usan búsquedas sofisticadas, pero no matemáticamente probadas para encontrar deducciones.
Los algoritmos pueden ser impresionantes, como para ganarle al ex campeón mundial de ajedrez Garry Kasparov, o al campeón de Go, pero no encontrando demostraciones. Ni qué hablar de proponer y probar un teorema.
Es que para eso tiene que haber previamente un procedimiento de decisión creado matemáticamente: Hilbert planteó esto, y es lo que se conoce como el Entscheidungsproblem, problema de la decisión: https://plato.stanford.edu/entries/computability/.
Church y Turing demostraron que no era posible un procedimiento así para la lógica de primer orden, y Gödel para la aritmética de Peano. Pero lo que resulta un poco exagerado es que luego de esto, pocos matemáticos quisieron dedicarse a buscar procedimientos de decisión en campos más acotados. Si se restringe la lógica a predicados de dos variables, por ejemplo (la aritmética usa sólo el predicado de igualdad, dos variables), o la aritmética sin todas las operaciones que agrega Gödel, podría haberlo.

23 Julio, 2020, 11:25 am
Respuesta #15

geómetracat

  • Moderador Global
  • Mensajes: 1,892
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Pero lo que resulta un poco exagerado es que luego de esto, pocos matemáticos quisieron dedicarse a buscar procedimientos de decisión en campos más acotados. Si se restringe la lógica a predicados de dos variables, por ejemplo (la aritmética usa sólo el predicado de igualdad, dos variables), o la aritmética sin todas las operaciones que agrega Gödel, podría haberlo.

Sobre la decidibilidad de fragmentos de la lógica de primer orden, recordaba que había resultados clásicos (de antes del resultado de Church y Turing, creo) de decidibilidad de algunos fragmentos (sólo con predicados monádicos, o sentencias que en su forma prenexa solamente pueden aparecer cuantificadores \( \exists^* \forall^* \)).

Me he dedicado a buscar un poco por internet cómo está la cosa hoy en día y parece que se ha hecho mucho desde tiempos de Gödel y ahora se entiende bastante bien qué fragmentos son decidibles y cuáles no. He encontrado un libro de 1997, "The classical decision problem" de Börger, Grädel y Gurevich, que está dedicado a explicar todos estos resultados.
Incluso he encontrado una tesis doctoral de 2019 que trata de estos temas:
http://people.mpi-inf.mpg.de/~mvoigt/files/Dissertation_with_hyperref.pdf
Es decir, que parece que es un tema en lo que se sigue haciendo investigación.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

23 Julio, 2020, 10:17 pm
Respuesta #16

Elius

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
Muy buena información, geómetracat.
Sí, sabía de algunas investigaciones, pero el libro que mencionas es muy valioso. La tesis también es interesante.
En la universidad Humboldt de Berlín el Dr. Timm Lampert está desarrollando un FOL-Decider, procedimiento de decisión para la lógica de orden 1, desafiando a Church y Turing:
http://www2.cms.hu-berlin.de/newlogic/webMathematica/Logic/decide.jsp
Me pasó algunos papers por si quería colaborar, pero la notación que emplea me resulta ilegible.