31 votos

Es cierto decir que "no es lógicamente posible para demostrar que no se puede hacer algo"?

Un amigo mío me preguntó si le podía explicar esta afirmación: "no Es lógicamente posible para demostrar que no se puede hacer algo". La razón real es la comprensión de esta tira:

enter image description here

Ya que yo no soy un experto en la lógica, pero, al menos, conocer los fundamentos, yo le dije que la afirmación es falsa. Para demostrar que yo le di el contraejemplo de la imposibilidad de trisecting un ángulo utilizando sólo regla y compás, lo cual ha sido probado por Pierre Wantzel. Esto muestra claramente que es posible demostrar que algo no se puede hacer.

Cuando le dije esto, me explicó que esta es una especie de ingenuos porque Asok, el tipo que hace la declaración, es graduado del IIT y también he leído que para él siempre es un personaje genial en la franja de gaza.

Pueden ustedes decirme por favor qué piensa usted de esto? También me gustaría saber cómo habría que interpretar este cuadro de diálogo.

29voto

Mike Puntos 1113

Lo de la franja más probable era (torpemente), refiriéndose a que no es que es imposible demostrar que algo no puede hacerse, sino que es imposible demostrar en un plazo de un (suficientemente potente) sistema formal de que algo no puede ser probada en ese sistema, en otras palabras, dejar que $P(\phi)$ ser que la declaración " no existe una prueba de $\phi$', entonces es imposible probar que una declaración de la forma $\neg P(\phi)$ (es decir, la declaración $P(\neg P(\phi))$ no puede ser verdad).

La razón detrás de esto tiene que ver con la de Gödel segundo teorema de la incompletitud de que ningún sistema formal puede probar su propia consistencia - en otras palabras, el sistema no puede probar la declaración $\neg P(\bot)$ (o, equivalentemente, $P(\neg P(\bot))$ es falso). La cadena lógica de la siguiente manera a partir de la declaración de 'falsa implica cualquier cosa': $\bot\implica\phi$ para cualquier proposición $\phi$. Por las reglas de la deducción, esto da que $P(\bot)\implica P(\phi)$, y luego tomar el contrapositivo, $\neg P(\phi)\implica\neg P(\bot)$ para cualquier proposición $\phi$; el uso de la deducción una vez más, esto da $P(\neg P(\phi))\implica P(\neg P(\bot))$ — si el sistema no se puede demostrar la unprovability de cualquier declaración, a continuación, puede probar su propia consistencia, lo cual constituiría una violación de Gödel segundo teorema de la incompletitud.

Nota la palabra clave "suficientemente poderoso' aquí - y también que nos estamos refiriendo a un sistema formal de hablar acerca de las pruebas dentro de sí mismo. Esto es lo que permite que declaraciones como la imposibilidad de ángulo trisection fuera del gancho: los axiomas de regla y compás de la geometría no son lo suficientemente fuertes para que el teorema de Gödel para aplicar el sistema, así que la geometría de la misma no se puede hablar de la noción de prueba, y nuestras declaraciones de pruebas de la imposibilidad dentro de ese sistema son las pruebas de fuera de ese sistema.

27voto

Gordon Freeman Puntos 409

Scott Adams puede tener la intención de hacer algo distinto, pero en el contexto dado y con la redacción, Dan es un derecho y Asok está mal.

Imaginar Asok la escritura de una pieza de software que depende de manera crucial en la determinación de la detención de problema (o cualquier otra propiedad cubiertos por el Arroz del teorema), luego Dan es de derecho: La detención problema es que no decidable y, por tanto, el software no funcionará nunca. Y Dan, de hecho pueden demostrarlo, porque la undecidability de la detención problema es demostrable.

11voto

Vincent Puntos 5027

Es una paradoja: al decir "no es lógicamente posible hacer X", Asok es, en efecto, afirmar que debe existir una prueba que X es imposible. Lo cual es imposible, si Asok que es correcto.

Por lo tanto Asok debe estar equivocados!

6voto

Jimmyjoe Puntos 61

Básicamente, la tira se acerca el científico ser un listillo y no sobre la lógica, la posibilidad de probar algo etc. Lo que dice es "el software que está escrito no va a funcionar" (y no "el software que escribió"), así que en este punto es realmente imposible demostrar nada. No es posible demostrar que el software no va a funcionar, una vez que está escrito. Por lo que su amigo de la conclusión pierde el punto, él es más bien el revestimiento con Dan (tratando de ser más astuto que, al no entender el problema de base) que con Asok.

5voto

msw Puntos 153

"Que el software está escrito nunca funcionará" no es un reclamo dentro de un sistema formal.

Tratando de convertirlo en un proposicional declaración sólo puede arruinar la broma (y puedo demostrarlo).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X