¿Cómo la indecidibilidad de la "teoría" implica que el ingenio humano es necesario en matemáticas?

Question

En Robert Stoll "la Teoría de conjuntos y la Lógica", es el siguiente pasaje de la efectividad de los teoremas (p. 375) :

Matemáticos, lógicos, han demostrado que para muchos interesantes axiomático de las teorías de la noción de teorema no es eficaz. Hacemos hincapié en que esto significa la inexistencia de efectivo procedimientos para "theoremhood" ha demostrado por algunas teorías y no sólo la nondiscovery a la fecha de procedimientos efectivos. De ello se sigue que humanos, la inventiva y el ingenio es necesario en matemáticas.

Esto parece implicar que la inventiva humana/ingenio se puede lograr algo que no puede ser realizado por una máquina, debido a la imposibilidad de un procedimiento eficaz para la decisión de "theoremhood".

Sin embargo, si por una cierta teoría, un humano podría decidir si cualquier oración es un teorema, entonces él/ella debe ser capaz de proporcionar una demostración formal de que la reclamación (de lo contrario el reclamo tendría poco valor). La demostración se puede tomar dos formas :

1. Si la sentencia es de un teorema, la demostración sería simplemente su prueba. Pero si tal prueba existe, una máquina puede realizar fácilmente la misma, simplemente por recursivamente enumerar todas las posibles pruebas de la teoría.

2. Si la sentencia es, en realidad, no es un teorema, la demostración tendría que ser expresado como una prueba de $P_M$ en algunos metalenguaje - con, supuestamente, de un conjunto de axiomas, si formalizado, que el sujeto de la teoría en la mano - lo que le permitiría mostrar que no hay prueba de $P_S$ en el tema de la teoría existe por el teorema. Pero por el mismo argumento, como en 1, si este metalenguaje y sus axiomas son formalizadas, una máquina puede encontrar $P_M$ mediante la enumeración de todos los posibles pruebas en esta cualidad de la lengua.

Así, en todos los casos una máquina logra lo que un humano es capaz de lograr. ¿Cuál es entonces la ventaja de la inventiva humana/ingenio?

Answer 1

Para ponerlo simplemente, no importa cómo muchas de las técnicas de ustedes saben, siempre habrá algún teorema que requerirá una nueva técnica para ser capaz de resolverlo. Las máquinas no puede venir con la nueva técnica, de lo contrario siguientes a la máquina en sí sería un procedimiento universal que encuentra una prueba para todos los teoremas demostrables. Pero sabemos que no hay tal procedimiento (si queremos ser capaces de demostrar los teoremas que involucran la aritmética), ya que se puede utilizar para resolver el cese Problema. Por lo tanto, sólo no-mecánicas de las entidades, posiblemente, puede ser capaz de demostrar arbitraria teoremas que involucran la aritmética. Tenga en cuenta que hay algoritmos para demostrar teoremas restringidas de los sistemas formales que son incapaces de expresar el estándar de la aritmética.

Answer 2

Pero los seres humanos viven en el mundo físico. Estamos limitados por el tiempo y los recursos que ideal máquinas de Turing no. Bueno, no exactamente, pero casi.

Incluso si usted puede enumerar recursivamente todas las pruebas, si efectivamente no puede decidir si es o no algo es un teorema, entonces usted va a tener que vivir para siempre con el fin de estar seguro de que no es un teorema. Puesto que nunca se puede decir si o no a la siguiente prueba es la prueba de que usted busca.

Por otro lado, si una teoría es decidable, entonces es verdad que no podría vivir para ver el cálculo de terminar en la búsqueda de nuestra prueba, pero no es una prueba de que definitivamente va a parar en algún momento para que nos digan si o no la pena es un teorema o no. Esto significa que si logramos mantener la máquina en funcionamiento lo suficientemente larga vamos a tener la certeza de si o no se encontró un teorema o no; mientras que en el indecidible caso tendremos que vivir para siempre antes de que nos enteramos.

El ingenio humano es un oráculo, de ordenación de todos modos, que nos permite trascender el tema de los acotados de tiempo, y encontrar una prueba de todos modos. Pero ya que no tenemos garantía de que un recursiva enumeración de encontrar esta prueba dentro de nuestra vida, el Sol del resto de miles de millones de años, o incluso el tiempo restante hasta que la decadencia de la última de protones en el universo, este método no es viable para nosotros.

Tal vez en el futuro que le toca a la Infinidad de piedras preciosas y la Energía Cósmica y esto nos va a permitir ejecutar infinito cálculos de inmediato. En ese caso, tienes razón. Si usted puede enumerar recursivamente todas las pruebas, entonces usted puede utilizar una máquina (y de estas increíbles nuevas atribuciones de la humanidad) para averiguar si es o no algo es un teorema o no un teorema.

Yo no colocar una gran cantidad de dinero en que eso ocurra, no dentro de nuestra vida, de todos modos.