El último teorema de Gödel. Confesión de un gran lógico

Uno de los teoremas más famosos de la lógica matemática es afortunado y desafortunado al mismo tiempo. En esto es similar a la teoría especial de la relatividad de Einstein. Por un lado, casi todo el mundo ha oído algo sobre ellos. Por otra parte, en interpretación popular La teoría de Einstein, como se sabe, “dice que todo en el mundo es relativo”. Y el teorema de la incompletitud de Gödel (en adelante simplemente TGN), aproximadamente en la misma formulación popular libre, "demuestra que hay cosas incomprensibles para la mente humana". Por eso algunos intentan adaptarlo como argumento contra el materialismo, mientras que otros, por el contrario, prueban con su ayuda que Dios no existe. Lo curioso no es sólo que ambos lados no pueden tener razón al mismo tiempo, sino que ni uno ni el otro se molestan en descubrir qué dice realmente este teorema.

¿Así que lo que? A continuación intentaré contártelo “con los dedos”. Mi presentación, por supuesto, no será rigurosa e intuitiva, pero pediré a los matemáticos que no me juzguen estrictamente. Es posible que para los no matemáticos (de los cuales, de hecho, soy uno), haya algo nuevo y útil en lo que se describe a continuación.

De hecho, la lógica matemática es una ciencia bastante compleja y, lo más importante, no muy familiar. Requiere maniobras cuidadosas y estrictas, en las que es importante no confundir lo que realmente ha sido probado con lo que “ya está claro”. Sin embargo, espero que para comprender el siguiente “esquema de una prueba de TGN”, el lector sólo necesite conocimientos de matemáticas/informática de la escuela secundaria, habilidades de pensamiento lógico y de 15 a 20 minutos de tiempo.

Simplificando un poco, TGN afirma que en cantidad suficiente idiomas dificiles Hay declaraciones indemostrables. Pero en esta frase casi cada palabra necesita explicación.

Comencemos por intentar descubrir qué es una prueba. Tomemos un problema de aritmética escolar. Por ejemplo, supongamos que necesita demostrar la exactitud de la siguiente fórmula simple: " " (permítame recordarle que el símbolo dice "para cualquiera" y se llama "cuantificador universal"). Puedes probarlo transformándolo de manera idéntica, digamos, así:

La transición de una fórmula a otra se produce según ciertas reglas conocidas. La transición de la cuarta fórmula a la quinta se produjo, digamos, porque cada número es igual a sí mismo; este es un axioma de la aritmética. Y, por lo tanto, todo el procedimiento de prueba traduce la fórmula al valor booleano VERDADERO. El resultado también podría ser una MENTIRA, si refutamos alguna fórmula. En este caso probaríamos su desmentida. Uno puede imaginar un programa (y tales programas realmente se han escrito) que demostraría declaraciones similares (y más complejas) sin intervención humana.

Digamos lo mismo de manera un poco más formal. Supongamos que tenemos un conjunto que consta de cadenas de caracteres de algún alfabeto, y existen reglas mediante las cuales a partir de estas cadenas podemos seleccionar un subconjunto del llamado declaraciones- es decir, frases gramaticalmente significativas, cada una de las cuales es verdadera o falsa. Podemos decir que existe una función que relaciona declaraciones con uno de dos valores: VERDADERO o FALSO (es decir, mapeándolas en un conjunto booleano de dos elementos).

Llamemos a ese par: un conjunto de declaraciones y una función de a - "lenguaje de declaraciones". Tenga en cuenta que en el sentido cotidiano el concepto de lenguaje es algo más amplio. Por ejemplo, la frase rusa "¡Ven aquí!" ni verdadero ni falso, es decir, desde el punto de vista de la lógica matemática, no es un enunciado.

Para seguir adelante necesitaremos el concepto de algoritmo. No daré aquí una definición formal; eso nos llevaría muy por mal camino. Me limitaré a lo informal: "algoritmo" es una secuencia de instrucciones inequívocas (“programa”) que en un número finito de pasos convierte los datos de origen en resultados. Lo que está en cursiva es fundamentalmente importante: si el programa recorre algunos datos iniciales, entonces no describe el algoritmo. Por simplicidad y en aplicación a nuestro caso, el lector puede considerar que un algoritmo es un programa escrito en cualquier lenguaje de programación conocido por él, que, para cualquier dato de entrada de una clase determinada, tiene la garantía de completar su trabajo produciendo un resultado booleano.

Preguntémonos: para cada función existe un “algoritmo de prueba” (o, en resumen, "deductivo"), equivalente a esta función, es decir, ¿transformar cada declaración en exactamente el mismo valor booleano? La misma pregunta se puede formular de manera más sucinta de la siguiente manera: ¿toda función sobre un conjunto de declaraciones calculable? Como ya habrás adivinado, de la validez de TGN se deduce que no, no todas las funciones, existen funciones incalculables de este tipo. En otras palabras, no todas las afirmaciones verdaderas pueden probarse.

Es muy posible que esta afirmación provoque en ti una protesta interna. Esto se debe a varias circunstancias. En primer lugar, cuando nos enseñan matematicas escolares, entonces a veces hay una impresión falsa de una identidad casi completa entre las frases “el teorema es verdadero” y “el teorema puede probarse o verificarse”. Pero, si lo piensas bien, esto no es nada obvio. Algunos teoremas se demuestran de forma bastante sencilla (por ejemplo, probando un pequeño número de opciones), mientras que otros son muy difíciles. Consideremos, por ejemplo, el famoso último teorema de Fermat:

cuya prueba se encontró sólo tres siglos y medio después de la primera formulación (y está lejos de ser elemental). Es necesario distinguir entre la verdad de un enunciado y su demostrabilidad. De ninguna parte se sigue que no existan afirmaciones verdaderas pero no demostrables (y no totalmente verificables).

El segundo argumento intuitivo contra TGN es más sutil. Digamos que tenemos alguna afirmación no demostrable (dentro del marco de esta deductiva). ¿Qué nos impide aceptarlo como un nuevo axioma? Por lo tanto, complicaremos un poco nuestro sistema de evidencia, pero esto no da miedo. Este argumento sería completamente correcto si hubiera un número finito de afirmaciones no demostrables. En la práctica, puede suceder lo siguiente: después de postular un nuevo axioma, te topas con una nueva afirmación que no se puede demostrar. Si lo aceptas como un axioma más, tropezarás con el tercero. Y así hasta el infinito. Dicen que la deducción se mantendrá incompleto. También podemos forzar que el algoritmo de prueba finalice en un número finito de pasos con algún resultado para cualquier expresión del idioma. Pero al mismo tiempo, comenzará a mentir, lo que conducirá a la verdad en caso de declaraciones incorrectas o a mentiras, para los fieles. En tales casos dicen que la deducción contradictorio. Por lo tanto, otra formulación del TGN suena así: "Hay lenguajes proposicionales para los cuales es imposible una deductividad completamente consistente", de ahí el nombre del teorema.

A veces llamado "teorema de Gödel", la afirmación es que cualquier teoría contiene problemas que no pueden resolverse dentro de la teoría misma y requieren su generalización. En cierto sentido esto es cierto, aunque esta formulación tiende a oscurecer la cuestión en lugar de aclararla.

También señalaré que si estuviéramos hablando de las funciones habituales que muestran un conjunto numeros reales en él, entonces la "no computabilidad" de la función no sorprendería a nadie (simplemente no confunda "funciones computables" y "números computables"; son cosas diferentes). Cualquier escolar sabe que, digamos, en el caso de una función, hay que tener mucha suerte con el argumento para que el proceso de calcular la representación decimal exacta del valor de esta función se complete en un número finito de pasos. Pero lo más probable es que lo calcules utilizando una serie infinita, y este cálculo nunca conducirá a un resultado exacto, aunque puede acercarse tanto como quieras, simplemente porque el valor del seno de la mayoría de los argumentos es irracional. TGN simplemente nos dice que incluso entre funciones cuyos argumentos son cadenas y cuyos valores son cero o uno, también hay funciones no computables, aunque estén estructuradas de una manera completamente diferente.

Para propósitos posteriores, describiremos el “lenguaje de la aritmética formal”. Considere una clase de cadenas de texto de longitud finita, que consta de números arábigos, variables (letras del alfabeto latino) que toman valores naturales, espacios, signos aritméticos, igualdad y desigualdad, cuantificadores (“existe”) y (“para cualquiera”) y , quizás , algunos otros símbolos (su número exacto y composición no son importantes para nosotros). Está claro que no todas estas líneas tienen significado (por ejemplo, " " no tiene sentido). El subconjunto de expresiones significativas de esta clase (es decir, cadenas que son verdaderas o falsas desde el punto de vista de la aritmética ordinaria) será nuestro conjunto de declaraciones.

Ejemplos de enunciados aritméticos formales:

etc. Ahora llamemos “fórmula con un parámetro libre” (FSP) a una cadena que se convierte en una declaración si se sustituye un número natural como este parámetro. Ejemplos de FSP (con parámetro):

etc. En otras palabras, los FSP son equivalentes a funciones de argumentos naturales con valores booleanos.

Denotemos el conjunto de todos los FSP con la letra . Está claro que se puede ordenar (por ejemplo, primero escribimos fórmulas de una letra ordenadas alfabéticamente, seguidas de las de dos letras, etc.; no nos importa en qué alfabeto se realizará el orden). Así, cualquier FSP corresponde a su número en la lista ordenada, y lo denotaremos.

Pasemos ahora a un bosquejo de la prueba de TGN en la siguiente formulación:

• Para el lenguaje proposicional de la aritmética formal no existe un sistema deductivo completo y consistente.

Lo demostraremos por contradicción.

Entonces, supongamos que existe tal sistema deductivo. Describamos el siguiente algoritmo auxiliar, que asigna un valor booleano a un número natural de la siguiente manera:

En pocas palabras, el algoritmo da como resultado el valor VERDADERO si y solo si el resultado de sustituir su propio número en el FSP de nuestra lista da una afirmación falsa.

Aquí llegamos al único lugar donde le pediré al lector que confíe en mi palabra.

Es obvio que, bajo el supuesto anterior, cualquier FSP puede compararse con un algoritmo que contiene un número natural en la entrada y un valor booleano en la salida. Lo contrario es menos obvio:

La prueba de este lema requeriría, como mínimo, una definición formal, más que intuitiva, del concepto de algoritmo. Sin embargo, si lo piensas un poco, es bastante plausible. De hecho, los algoritmos están escritos en lenguajes algorítmicos, entre los que se encuentran otros tan exóticos como, por ejemplo, Brainfuck, que consta de ocho palabras de un solo carácter, en los que, sin embargo, se puede implementar cualquier algoritmo. Sería extraño que el lenguaje más rico de fórmulas de aritmética formal que describimos resultara ser más pobre, aunque, sin duda, no es muy adecuado para la programación ordinaria.

Pasado este lugar resbaladizo, llegamos rápidamente al final.

Entonces, arriba describimos el algoritmo. Según el lema que les pedí que creyeran, existe un FSP equivalente. Tiene algún número en la lista, digamos. Preguntémonos ¿a qué es igual? Que esta sea la VERDAD. Entonces, según la construcción del algoritmo (y por tanto de la función equivalente a él), esto significa que el resultado de sustituir un número en la función es FALSO. Lo contrario se comprueba de la misma forma: de FALSO sigue VERDADERO. Hemos llegado a una contradicción, lo que significa que la suposición original es incorrecta. Por tanto, no existe un sistema deductivo completo y consistente para la aritmética formal. Q.E.D.

Conviene recordar aquí a Epiménides (véase el retrato del título), quien, como se sabe, declaró que todos los cretenses son mentirosos, siendo él mismo cretense. En una formulación más sucinta, su afirmación (conocida como la “paradoja del mentiroso”) puede expresarse de la siguiente manera: “Estoy mintiendo”. Es precisamente este tipo de afirmación, que proclama su falsedad, la que utilizamos como prueba.

En conclusión, quiero señalar que TGN no afirma nada particularmente sorprendente. Después de todo, todo el mundo está acostumbrado desde hace mucho tiempo al hecho de que no todos los números se pueden representar como una proporción de dos números enteros (¿recuerde, esta afirmación tiene una prueba muy elegante que tiene más de dos mil años?). Y tampoco todos los números son raíces de polinomios con coeficientes racionales. Y ahora resulta que no todas las funciones de un argumento natural son computables.

El esbozo de la prueba dada fue para aritmética formal, pero es fácil ver que TGN es aplicable a muchos otros lenguajes proposicionales. Eso sí, no todos los idiomas son así. Por ejemplo, definamos un idioma de la siguiente manera:

• "Cualquier frase idioma chino es declaración verdadera, si está contenida en el libro de citas del camarada Mao Zedong, y es incorrecta si no está contenida”.

Entonces, el correspondiente algoritmo de demostración completo y consistente (podríamos llamarlo “deductivo dogmático”) se parece a esto:

• “Hojee el libro de citas del camarada Mao Zedong hasta que encuentre el dicho que busca. Si se encuentra, entonces es correcto, pero si el libro de citas terminó y no se encuentra la declaración, entonces es incorrecto”.

Lo que nos salva aquí es que cualquier libro de citas es obviamente finito, por lo que el proceso de “demostración” inevitablemente terminará. Así, el TGN no es aplicable al lenguaje de los enunciados dogmáticos. Pero estábamos hablando de lenguajes complejos, ¿verdad?

Etiquetas: Agregar etiquetas

Ecología de la vida. Ciencia y descubrimiento: el teorema de incompletitud de Gödel, uno de los teoremas más famosos de la lógica matemática, es a la vez afortunado y desafortunado. En esto es similar a la teoría especial de la relatividad de Einstein. Por un lado, casi todo el mundo ha oído hablar de ellos. Según otra interpretación, la teoría de Einstein “dice que todo en el mundo es relativo”.

Teorema Gödel sobre lo incompleto, uno de los teoremas más famosos de la lógica matemática, es afortunado y desafortunado al mismo tiempo. En esto es similar a la teoría especial de la relatividad de Einstein.

Por un lado, casi todo el mundo ha oído algo sobre ellos. Por otra parte, en la interpretación popular La teoría de Einstein, como es sabido, " dice que todo en el mundo es relativo" A Teorema de incompletitud de Gödel(en adelante simplemente TGN), aproximadamente en la misma formulación popular libre, “ demuestra que hay cosas incomprensibles para la mente humana».

Y por eso algunos intentan adaptarlo como argumento contra las malas palabras. serialismo , mientras que otros, por el contrario, demuestran con su ayuda, que no hay dios . Lo curioso no es sólo que ambos lados no pueden tener razón al mismo tiempo, sino que ni uno ni el otro se molestan en descubrir qué dice realmente este teorema.

¿Así que lo que? A continuación intentaré contárselo “con los dedos”. Mi presentación, por supuesto, no será rigurosa e intuitiva, pero pediré a los matemáticos que no me juzguen estrictamente. Es posible que para los no matemáticos (de los cuales, de hecho, soy uno), haya algo nuevo y útil en lo que se describe a continuación.

De hecho, la lógica matemática es una ciencia bastante compleja y, lo más importante, no muy familiar. Requiere maniobras cuidadosas y estrictas, en las que es importante no confundir lo que realmente ha sido probado con lo que “ya está claro”. Sin embargo, espero que para comprender el siguiente “esquema de una prueba de TGN”, el lector sólo necesite conocimientos de matemáticas/informática de la escuela secundaria, habilidades de pensamiento lógico y de 15 a 20 minutos de tiempo.

Para simplificar un poco, TGN sostiene que en lenguajes suficientemente complejos existen enunciados indemostrables. Pero en esta frase casi todas las palabras necesitan explicación.

Comencemos tratando de descubrir qué es una prueba. Tomemos un problema de aritmética escolar. Por ejemplo, supongamos que necesita demostrar la exactitud de la siguiente fórmula simple: “∀x(x−1)(x−2)−2=x(x−3)” (permítame recordarle que el símbolo ∀ se lee “para cualquiera” y se llama “cuantificador universal”). Puedes probarlo transformándolo de manera idéntica, digamos, así:

∀x(x−1)(x−2)−2=x(x−3)

∀xx2−3x+2−2=x2−3x

∀xx2−3x–x2+3x=0

∀x0=0

VERDADERO

La transición de una fórmula a otra se produce según ciertas reglas bien conocidas. La transición de la cuarta fórmula a la quinta se produjo, digamos, porque cada número es igual a sí mismo; este es un axioma de la aritmética. Y, por lo tanto, todo el procedimiento de prueba traduce la fórmula al valor booleano VERDADERO. El resultado también podría ser una MENTIRA, si refutamos alguna fórmula. En este caso probaríamos su desmentida. Uno puede imaginar un programa (y tales programas realmente se han escrito) que demostraría declaraciones similares (y más complejas) sin intervención humana.

Digamos lo mismo de manera un poco más formal. Tengamos un conjunto que consta de cadenas de caracteres de algún alfabeto, y existen reglas mediante las cuales a partir de estas cadenas podemos seleccionar un subconjunto S las llamadas declaraciones, es decir, frases gramaticalmente significativas, cada una de las cuales es verdadera o falsa. Podemos decir que existe una función P que asigna declaraciones de S uno de dos valores: VERDADERO o FALSO (es decir, las asigna a un conjunto booleano B de dos elementos).

Llamemos a este par- conjunto de declaraciones S y función P de >S a B - "lenguaje de declaraciones". Tenga en cuenta que en el sentido cotidiano el concepto de lenguaje es algo más amplio. Por ejemplo, la frase rusa " ¡Ven aquí!"No es ni verdadero ni falso, es decir, desde el punto de vista de la lógica matemática, no es un enunciado.

Para seguir adelante necesitaremos el concepto de algoritmo. No daré aquí una definición formal; eso nos llevaría muy por mal camino. Me limitaré a lo informal: un “algoritmo” es una secuencia de instrucciones inequívocas (“programa”) que, en un número finito de pasos, transforma los datos iniciales en el resultado.

Lo que está en cursiva es fundamentalmente importante: si el programa recorre algunos datos iniciales, entonces no describe el algoritmo. Por simplicidad y en aplicación a nuestro caso, el lector puede considerar que un algoritmo es un programa escrito en cualquier lenguaje de programación conocido por él, que, para cualquier dato de entrada de una clase determinada, tiene la garantía de completar su trabajo produciendo un resultado booleano.

Preguntémonos: para cada función P existe un “algoritmo de demostración” (o, en resumen, “ deductivo"), equivalente a esta función, es decir, ¿transformar cada declaración en exactamente el mismo valor booleano? La misma pregunta se puede formular de manera más sucinta: ¿Es computable cada función sobre un conjunto de declaraciones?

Como ya habrás adivinado, de la validez de TGN se deduce que no, no todas las funciones, existen funciones incalculables de este tipo. En otras palabras, No todas las afirmaciones verdaderas pueden probarse.

Es muy posible que esta afirmación provoque en ti una protesta interna. Esto se debe a varias circunstancias. En primer lugar, cuando nos enseñan matemáticas en la escuela, a veces tenemos la falsa impresión de que las frases “El teorema X es verdadero” y “El teorema X puede demostrarse o verificarse” son casi completamente idénticas.

Pero, si lo piensas bien, esto no es nada obvio. Algunos teoremas se demuestran de forma bastante sencilla (por ejemplo, probando un pequeño número de opciones), mientras que otros son muy difíciles. Recordemos, por ejemplo, el famoso Gran teorema de fermat:

no existen tales naturales x,y,z y n>2, que xn+yn=zn,

cuya prueba se encontró sólo tres siglos y medio después de la primera formulación (y está lejos de ser elemental). CON Hay que distinguir entre la verdad de una afirmación y su demostrabilidad. De ninguna parte se sigue que no existan afirmaciones verdaderas pero no demostrables (y no totalmente verificables).

El segundo argumento intuitivo contra TGN es más sutil. Digamos que tenemos alguna afirmación no demostrable (dentro del marco de esta deductiva). ¿Qué nos impide aceptarlo como un nuevo axioma? Por lo tanto, complicaremos un poco nuestro sistema de evidencia, pero esto no da miedo.

Este argumento sería completamente correcto si hubiera un número finito de afirmaciones no demostrables. En la práctica, puede suceder lo siguiente: Después de postular un nuevo axioma, te topas con una nueva afirmación que no se puede demostrar.. Si lo aceptas como un axioma más, tropezarás con el tercero. Y así hasta el infinito.

Ellos dijeron eso la deducción quedará incompleta. También podemos forzar que el algoritmo de prueba finalice en un número finito de pasos con algún resultado para cualquier expresión del idioma. Pero al mismo tiempo, comenzará a mentir, lo que conducirá a la verdad en caso de declaraciones incorrectas o a mentiras, para los fieles.

En tales casos dicen que la deducción es contradictoria. Así, otra formulación del TGN suena así: “ Hay lenguajes proposicionales para los cuales es imposible un proceso deductivo completo y consistente." - de ahí el nombre del teorema.

A veces llamado "teorema de Gödel", la afirmación es que cualquier teoría contiene problemas que no pueden resolverse dentro de la teoría misma y requieren su generalización. En cierto sentido esto es cierto, aunque esta formulación tiende a oscurecer la cuestión en lugar de aclararla.

También señalaré que si estuviéramos hablando de funciones familiares que asignan un conjunto de números reales a ella, entonces la "no computabilidad" de la función no sorprendería a nadie (simplemente no confunda "funciones computables" y "números computables"). ” - estas son cosas diferentes).

Kurt Godel

Cualquier escolar sabe que, digamos, en el caso de la función sen⁡x, hay que tener mucha suerte con el argumento para que el proceso de calcular la representación decimal exacta del valor de esta función se complete en un número finito. de pasos.

Pero lo más probable es que lo calcules utilizando una serie infinita, y este cálculo nunca conducirá a un resultado exacto, aunque puede acercarse tanto como quieras. simplemente porque el valor seno de la mayoría de los argumentos es irracional. TGN simplemente nos dice que incluso entre funciones cuyos argumentos son cadenas y cuyos valores son cero o uno, también hay funciones no computables, aunque tengan una estructura completamente diferente.

Para propósitos posteriores, describiremos el “lenguaje de la aritmética formal”. Considere una clase de cadenas de texto de longitud finita que consta de números arábigos, variables (letras del alfabeto latino) que toman valores naturales, espacios, signos aritméticos, igualdad y desigualdad, cuantificadores ∃ (“existe”) y ∀ (“para cualquiera”) y quizás algunos otros símbolos (su número exacto y composición no son importantes para nosotros).

Está claro que no todas estas líneas tienen significado (por ejemplo, “12=+∀x>” no tiene sentido). El subconjunto de expresiones significativas de esta clase (es decir, cadenas que son verdaderas o falsas desde el punto de vista de la aritmética ordinaria) será nuestro conjunto de declaraciones.

Ejemplos de enunciados aritméticos formales:

1=1

2×2=5

∃xx>3

∀y∀zy×z>y+ z

etc. Ahora llamemos “fórmula con un parámetro libre” (FSP) a una cadena que se convierte en una declaración si se sustituye un número natural como este parámetro. Ejemplos de FSP (con parámetro x):

x=0

2×2=x

∃yx+y>x

etc. En otras palabras, los FSP son equivalentes a funciones de argumentos naturales con valores booleanos.

Denotemos el conjunto de todos los FSP con la letra F. Está claro que se puede ordenar (por ejemplo, primero escribimos fórmulas de una letra ordenadas alfabéticamente, seguidas de fórmulas de dos letras, etc.; no es importante indicarnos en qué alfabeto se realizará el pedido). Así, cualquier FSP corresponde a su número k en la lista ordenada, y lo denotaremos Fk.

Pasemos ahora a un bosquejo de la prueba de TGN en la siguiente formulación:

Para el lenguaje proposicional de la aritmética formal no existe un sistema deductivo completo y consistente.

Lo demostraremos por contradicción.

Entonces, supongamos que existe tal sistema deductivo. Describamos el siguiente algoritmo auxiliar A, que asigna un valor booleano a un número natural k de la siguiente manera:

1. Encuentra késima fórmula en la lista F.

2. Sustituya el número k como argumento.

3. Aplicamos nuestro algoritmo de demostración a la afirmación resultante (según nuestra suposición, existe), que la traduce a VERDADERO o FALSO.

4. Aplicar la negación lógica al resultado obtenido.

En pocas palabras, el algoritmo da como resultado el valor VERDADERO si y solo si el resultado de sustituir su propio número en el FSP de nuestra lista da una afirmación falsa.

Aquí llegamos al único lugar donde le pediré al lector que confíe en mi palabra.

Es obvio que, bajo el supuesto anterior, cualquier FSP de F puede asociarse con un algoritmo que contenga un número natural en la entrada y un valor booleano en la salida.

Lo contrario es menos obvio:

Lema: Cualquier algoritmo que convierte un número natural en un valor booleano corresponde a algún FSP del conjunto F.

La prueba de este lema requeriría, como mínimo, una definición formal, más que intuitiva, del concepto de algoritmo. Sin embargo, si lo piensas un poco, es bastante plausible.

De hecho, los algoritmos están escritos en lenguajes algorítmicos, entre los que se encuentran otros tan exóticos como, por ejemplo, Brainfuck, que consta de ocho palabras de un solo carácter, en los que, sin embargo, se puede implementar cualquier algoritmo. Sería extraño que el lenguaje más rico de fórmulas de aritmética formal que describimos resultara ser más pobre, aunque, sin duda, no es muy adecuado para la programación ordinaria.

Pasado este lugar resbaladizo, llegamos rápidamente al final.

Entonces, arriba describimos el Algoritmo A. Según el lema que les pedí que creyeran, existe un FSP equivalente. Tiene algún número en la lista F, digamos, n. Preguntémonos ¿qué es Fn(n)? Que esta sea la VERDAD. Entonces, de acuerdo con la construcción del algoritmo A (y por lo tanto la función equivalente Fn), esto significa que el resultado de sustituir el número n en la función Fn es FALSO.

Lo contrario se comprueba de la misma manera: de Fn(n)=FALSE se deduce que Fn(n)=TRUE. Hemos llegado a una contradicción, lo que significa que la suposición original es incorrecta. Por tanto, no existe un sistema deductivo completo y consistente para la aritmética formal. Q.E.D.

Conviene recordar aquí a Epiménides, quien, como se sabe, declaró que todos los cretenses son mentirosos, siendo él mismo cretense. En una formulación más sucinta de su afirmación (conocida como la “paradoja del mentiroso”) puede formularse de la siguiente manera: “ yo miento" Es precisamente este tipo de afirmación, que proclama su falsedad, la que utilizamos como prueba.

En conclusión, quiero señalar que TGN no afirma nada particularmente sorprendente. Después de todo, todo el mundo está acostumbrado desde hace mucho tiempo al hecho de que no todos los números se pueden representar como una proporción de dos números enteros (¿recuerde, esta afirmación tiene una prueba muy elegante que tiene más de dos mil años?).Y las raíces de polinomios con coeficientes racionales. tampoco todos los números lo son . Y ahora resulta que no todas las funciones de un argumento natural son computables.

El esbozo de la prueba dada fue para aritmética formal, pero es fácil ver que TGN es aplicable a muchos otros lenguajes proposicionales. Eso sí, no todos los idiomas son así. Por ejemplo, definamos un idioma de la siguiente manera:

“Cualquier frase en idioma chino es verdadera si está contenida en el libro de citas del camarada Mao Zedong, e incorrecta si no está contenida”.

Entonces, el correspondiente algoritmo de demostración completo y consistente (podríamos llamarlo “deductivo dogmático”) se parece a esto:

“Hojee el libro de citas del camarada Mao Zedong hasta que encuentre el dicho que busca. Si se encuentra, entonces es correcto, pero si el libro de citas terminó y no se encuentra la declaración, entonces es incorrecto”.

Lo que nos salva aquí es que cualquier libro de citas es obviamente finito, por lo que el proceso de “demostración” inevitablemente terminará. Así, el TGN no es aplicable al lenguaje de los enunciados dogmáticos. Pero estábamos hablando de lenguajes complejos, ¿verdad? publicado

Uspensky V.A.

Teorema de incompletitud de Gödel.1994.

Informática teórica 130, 1994, páginas 273-238.

Quizás el teorema de incompletitud de Gödel sea verdaderamente único. Es único porque se hace referencia a él cuando quieren probar "todo en el mundo", desde la presencia de dioses hasta la ausencia de inteligencia. Siempre me ha interesado una "pregunta más importante": ¿cuál de las que se refieren al teorema de incompletitud podría no sólo formularlo, sino también demostrarlo? Publico este artículo porque establece una formulación completamente accesible del teorema de Gödel. Te recomiendo que leas primero el artículo de Tullio Regge Kurt Gödel y su famoso teorema

La conclusión sobre la imposibilidad de un criterio universal de verdad es

una consecuencia directa del resultado obtenido por Tarski al combinar

El teorema de indecidibilidad de Gödel con su propia teoría de la verdad, según

para lo cual no puede haber un criterio universal de verdad, ni siquiera para casos relativamente

campo estrecho de la teoría de números y, por lo tanto, para cualquier ciencia que utilice

aritmética. Naturalmente, este resultado se aplica a fortiori al concepto de verdad.

en cualquier campo del conocimiento no matemático en el que sea ampliamente

Se utiliza la aritmética.

karl popper

Uspensky Vladimir Andreevich nació el 27 de noviembre de 1930 en Moscú. Graduado por la Facultad de Mecánica y Matemáticas de la Universidad Estatal de Moscú (1952). Doctor en Ciencias Físicas y Matemáticas (1964). Profesor, Jefe del Departamento de Lógica Matemática y Teoría de Algoritmos, Facultad de Mecánica y Matemáticas (1966). Imparte cursos de conferencias "Introducción a la lógica matemática", "Funciones computables", "Teorema de completitud de Gödel". Preparó 25 candidatos y 2 doctores en ciencias.

1. Planteamiento del problema

El teorema de la incompletitud, cuya formulación exacta daremos al final de este capítulo, y quizás más adelante (si el lector está interesado en esto) y la demostración, establece aproximadamente lo siguiente: bajo ciertas condiciones, en cualquier idioma, hay cosas verdaderas pero declaraciones indemostrables.

Cuando formulamos el teorema de esta manera, casi todas las palabras requieren alguna explicación. Por tanto, comenzaremos explicando el significado de las palabras que utilizamos en esta formulación.

No daremos la definición más general posible de lenguaje, prefiriendo limitarnos a aquellos conceptos lingüísticos que necesitaremos más adelante. Hay dos conceptos de este tipo: "el alfabeto de una lengua" y "el conjunto de enunciados verdaderos de una lengua".

1.1.1. Alfabeto

Por alfabeto nos referimos a un conjunto finito de signos elementales (es decir, cosas que no pueden descomponerse en sus partes componentes). Estos signos se llaman letras del alfabeto. Por palabra del alfabeto nos referimos a una secuencia finita de letras. Por ejemplo, las palabras comunes en inglés (incluidos los nombres propios) son palabras del alfabeto de 54 letras (26 letras minúsculas, 26 letras mayúsculas, un guión y un apóstrofo). Otro ejemplo - números enteros en notación decimal son palabras de un alfabeto de 10 letras, cuyas letras son signos: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Para designar alfabetos usaremos ordinarios. letras mayúsculas. Si L es un alfabeto, ¿entonces L? denotará el conjunto de todas las palabras del alfabeto L, palabras formadas a partir de sus letras. Supondremos que cualquier idioma tiene su propio alfabeto, de modo que todas las expresiones de este idioma (es decir, nombres de varios objetos, declaraciones sobre estos objetos, etc.) son palabras de este alfabeto. Por ejemplo, cualquier oferta en Inglés, así como cualquier texto escrito en inglés, puede considerarse como una palabra de un alfabeto ampliado de 54 letras, que también incluye signos de puntuación, espacios entre palabras, un signo de línea roja y, posiblemente, algunos otros signos útiles. Suponiendo que las expresiones del idioma son palabras de algún alfabeto, excluimos de la consideración expresiones “multicapa” como ???f(x)dx. Sin embargo, esta limitación no es demasiado significativa, ya que cualquier expresión de este tipo, utilizando convenciones adecuadas, puede "estirarse" hasta adoptar una forma lineal. ¿Algún conjunto M contenido en L? se llama conjunto de palabras del alfabeto L. Si simplemente decimos que M es un conjunto de palabras, entonces queremos decir que es una palabra de algún alfabeto. Ahora bien, el supuesto anterior sobre el lenguaje se puede reformular de la siguiente manera: en cualquier idioma, cualquier conjunto de expresiones es un conjunto de palabras.

1.1.2. Muchas declaraciones verdaderas

¿Suponemos que tenemos un subconjunto T del conjunto L? (donde L es el alfabeto de algún idioma que estamos considerando), que se denomina conjunto de “afirmaciones verdaderas” (o simplemente “verdades”). Pasando directamente al subconjunto T, omitimos los siguientes pasos intermedios de razonamiento: primero, qué palabras del alfabeto L son expresiones del idioma correctamente formadas, es decir, que tienen un cierto significado en nuestra interpretación de este idioma (por ejemplo, 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 son expresiones bien formadas, mientras que expresiones como +=x no lo son); en segundo lugar, qué expresiones son fórmulas, es decir puede depender del parámetro (por ejemplo, x=3, x=y, 2=3, 2=2); en tercer lugar, cuáles de las fórmulas son fórmulas cerradas, es decir, declaraciones que no dependen de parámetros (por ejemplo, 2=3, 2=2); y finalmente, qué fórmulas cerradas son afirmaciones verdaderas (por ejemplo, 2=2).

1.1.3. Par de lenguas fundamentales

1.2. "Indemostrable"

"Indemostrable" significa sin evidencia.

1.3. Prueba

Aunque el término "demostración" es quizás uno de los más importantes en matemáticas (los Bourbaki comienzan su libro "Fundamentos de las matemáticas" con las palabras: "Desde la época de los antiguos griegos, decir 'matemáticas' ha significado lo mismo que decir diga 'prueba'"), no tiene su propia definición exacta. En general, el concepto de prueba con todas sus ramas semánticas pertenece más al campo de la psicología que a las matemáticas. Pero sea como fuere, la prueba es simplemente un argumento que nosotros mismos consideramos bastante convincente para convencer a todos los demás.

Una vez escrita, la prueba se convierte en una palabra de algún alfabeto P, como cualquier texto en inglés es una palabra del alfabeto L, cuyo ejemplo se dio anteriormente. El conjunto de todas las pruebas forma un subconjunto (y un subconjunto bastante extenso) del conjunto P?. No intentaremos dar definición precisa este concepto de prueba simultáneamente “ingenuo” y “absoluto”, o - lo que es equivalente - definir el subconjunto correspondiente de P?. En su lugar, consideraremos un análogo formal de este vago concepto, para el cual en el futuro seguiremos usando el término "prueba". Este análogo tiene dos muy características importantes, que lo distinguen del concepto intuitivo (aunque la idea intuitiva de prueba todavía refleja estas características hasta cierto punto). En primer lugar, admitiremos que existen diferentes conceptos de prueba, es decir, diferentes subconjuntos de pruebas en P son admisibles, e incluso más que eso: de hecho, admitiremos que el alfabeto de las pruebas P puede cambiar. . A continuación exigiremos que para cada concepto de prueba exista método efectivo, en otras palabras, un algoritmo que necesariamente determinaría si una palabra dada del alfabeto P es una prueba o no. También asumiremos que existe un algoritmo que siempre puede determinar qué afirmación prueba una prueba determinada. (En muchas situaciones, el enunciado que se demuestra es simplemente el último enunciado de la secuencia de pasos que constituye la prueba).

Así, nuestra definición final es la siguiente:

(1) Tenemos el alfabeto L (alfabeto del idioma) y el alfabeto P (alfabeto de prueba).

(2) Se nos da un conjunto P, que es un subconjunto de P?, y cuyos elementos se denominan “pruebas”. En el futuro, asumiremos que también tenemos un algoritmo que nos permite determinar si una palabra arbitraria del alfabeto P es un elemento del conjunto P, es decir, una prueba, o no.

(3) ¿También tenemos una función? (para encontrar qué se ha demostrado exactamente), ¿de quién es el alcance? satisface la condición P???P?, y cuyo rango de valores se encuentra en P?. Suponemos que tenemos un algoritmo que calcula esta función ( valor exacto Las palabras "un algoritmo calcula una función" son las siguientes: los valores de la función se obtienen utilizando este algoritmo (un conjunto de reglas de transformación especiales). Diremos que el elemento p? P es una prueba de la palabra?(p) del alfabeto L.

Un triple que satisface las condiciones (1)-(3) se llama sistema deductivo sobre el alfabeto L.

Para el lector familiarizado con la forma habitual de definir "demostración" en términos de "axioma" y "regla de inferencia", ahora explicaremos cómo este método puede considerarse como un caso especial de la definición dada en la sección 1.3.2. Es decir, una prueba generalmente se define como una secuencia de tales expresiones lingüísticas, cada una de las cuales es un axioma o se obtiene previamente a partir de enunciados ya existentes utilizando una de las reglas de inferencia. Si agregamos una nueva palabra * al alfabeto de nuestro idioma, entonces podemos escribir dicha prueba en forma de una palabra compuesta usando la modificación del alfabeto resultante: la secuencia de expresiones se convierte en la palabra C1*C2*...*Cn . En este caso, la función que determina qué se ha probado exactamente tiene su significado en la parte de esta palabra que sigue inmediatamente a la última letra * de la secuencia. Un algoritmo cuya existencia se requiere en la parte 1.3.2. Las definiciones pueden construirse fácilmente una vez que hayamos definido con precisión cualquiera de valores aceptados las palabras "axioma" y "reglas de inferencia".

1.4. Intenta formular con precisión el teorema de la incompletitud

1.4.1. Primer intento

"Bajo ciertas condiciones para un par fundamental de un lenguaje alfabético L y un sistema deductivo sobre L, siempre existe una palabra en T que no tiene prueba". Esta opción todavía parece vaga. En particular, podríamos idear fácilmente tantos sistemas deductivos como queramos que tengan muy pocas palabras demostrables. Por ejemplo, en un sistema deductivo vacío (donde P = ?) no hay ninguna palabra que tenga evidencia.

1.4.2. Segundo intento

Hay otro enfoque más natural. Supongamos que se nos da un idioma, en el sentido de que se nos da un par fundamental de este idioma. Ahora buscaremos un sistema deductivo sobre L (intuitivamente, buscamos una técnica de demostración) con la ayuda del cual podamos demostrar todo lo posible. mas palabras de T, en el límite todas las palabras de T. El teorema de Gödel describe una situación en la que tal sistema deductivo (mediante el cual cada palabra en T sería demostrable) no existe. Por lo tanto, nos gustaría formular la siguiente declaración:

"Bajo ciertas condiciones relativas al par fundamental, no existe un sistema deductivo en el que cada palabra de T tenga una prueba".

Sin embargo, tal afirmación es obviamente falsa, ya que sólo es necesario tomar un sistema deductivo en el que P = L, P = P? u?(p) = p para todo p de P?; entonces cada palabra de L? es trivialmente demostrable. Por lo tanto, debemos aceptar alguna restricción sobre qué sistemas deductivos utilizamos.

1.5. Consistencia

Sería bastante natural exigir que sólo puedan probarse "enunciados verdaderos", es decir, sólo palabras de T. Diremos que un sistema deductivo es consistente respecto del par fundamental si?(P)?T. En todas las discusiones posteriores sólo nos interesaremos en sistemas deductivos tan consistentes. Si nos dieran un lenguaje, entonces sería extremadamente tentador encontrar un sistema deductivo consistente en el que cada afirmación verdadera tuviera una prueba. La versión del teorema de Gödel que nos interesa afirma precisamente que bajo ciertas condiciones relativas al par fundamental, es imposible encontrar tal sistema deductivo.

1.6. Lo completo

Se dice que el sistema deductivo es completo respecto del par fundamental, siempre que ?(P)?T. Entonces nuestra formulación del teorema de incompletitud toma la siguiente forma:

Bajo ciertas condiciones con respecto al par fundamental, no existe ningún sistema deductivo sobre L que sea completo y relativamente consistente.

Cualquier sistema de axiomas matemáticos, a partir de un cierto nivel de complejidad, es internamente contradictorio o incompleto.

En 1900 se celebró en París la Conferencia Mundial de Matemáticos, en la que David Hilbert (1862-1943) presentó en forma de tesis los 23 problemas más importantes, en su opinión, que los teóricos del próximo siglo XX debían resolver. El número dos en su lista era uno de esos tareas simples, cuya respuesta parece obvia hasta que se profundiza un poco más. Discurso idioma moderno, era una pregunta: ¿son las matemáticas autosuficientes? La segunda tarea de Hilbert se redujo a la necesidad de demostrar estrictamente que el sistema axiomas- afirmaciones básicas tomadas como base en matemáticas sin prueba - es perfecta y completa, es decir, permite describir matemáticamente todo lo que existe. Era necesario demostrar que era posible definir tal sistema de axiomas que, en primer lugar, serían mutuamente consistentes y, en segundo lugar, de ellos se podría sacar una conclusión sobre la verdad o falsedad de cualquier afirmación.

Tomemos un ejemplo de la geometría escolar. Estándar Planimetría euclidiana(geometría plana) se puede demostrar incondicionalmente que la afirmación “la suma de los ángulos de un triángulo es 180°” es verdadera, y la afirmación “la suma de los ángulos de un triángulo es 137°” es falsa. En esencia, en la geometría euclidiana cualquier afirmación es falsa o verdadera y no existe una tercera opción. Y a principios del siglo XX, los matemáticos creían ingenuamente que debería observarse la misma situación en cualquier sistema lógicamente consistente.

Y luego, en 1931, un matemático vienés con gafas, Kurt Gödel, lo tomó y publicó artículo corto, que simplemente trastornó el mundo entero de la llamada "lógica matemática". Después de largos y complejos preámbulos matemáticos y teóricos, estableció literalmente lo siguiente. Tomemos cualquier afirmación como: “El supuesto número 247 en este sistema de axiomas es lógicamente indemostrable” y llamémosla “afirmación A”. Entonces, Gödel simplemente demostró lo siguiente propiedad increíble cualquier sistemas de axiomas:

"Si puedes probar la afirmación A, entonces puedes probar la afirmación que no es A".

En otras palabras, si es posible probar la validez de la afirmación “supuesto 247 No demostrable", entonces es posible probar la validez de la afirmación "supuesto 247 demostrable" Es decir, volviendo a la formulación del segundo problema de Hilbert, si un sistema de axiomas es completo (es decir, cualquier enunciado que contenga puede ser probado), entonces es contradictorio.

La única salida a esta situación es aceptar sistema incompleto axioma. Es decir, hay que aguantar el hecho de que en el contexto de cualquier sistema lógico nos quedarán declaraciones "tipo A", que se sabe que son verdaderas o falsas, y sólo podemos juzgar su verdad afuera el marco de la axiomática que hemos adoptado. Si no existen tales afirmaciones, entonces nuestra axiomática es contradictoria y, dentro de su marco, inevitablemente habrá formulaciones que puedan ser probadas y refutadas.

Entonces la redacción primero,o débil Teoremas de incompletitud de Gödel: "Cualquier sistema formal de axiomas contiene suposiciones no resueltas". Pero Gödel no se detuvo ahí, formulando y demostrando segundo, o fuerte Teorema de incompletitud de Gödel: “La integridad lógica (o incompletitud) de cualquier sistema de axiomas no puede probarse dentro del marco de este sistema. Para probarlo o refutarlo se requieren axiomas adicionales (fortalecer el sistema)”.

Sería más seguro pensar que los teoremas de Gödel son de naturaleza abstracta y no nos conciernen, sino sólo áreas de la lógica matemática sublime, pero de hecho resultó que están directamente relacionados con la estructura del cerebro humano. El matemático y físico inglés Roger Penrose (n. 1931) demostró que los teoremas de Gödel pueden utilizarse para demostrar la existencia de diferencias fundamentales entre el cerebro humano y una computadora. El significado de su razonamiento es simple. La computadora actúa de manera estrictamente lógica y no es capaz de determinar si el enunciado A es verdadero o falso si va más allá de la axiomática, y tales enunciados, según el teorema de Gödel, existen inevitablemente. Una persona, ante una afirmación A tan lógicamente indemostrable e irrefutable, siempre es capaz de determinar su verdad o falsedad, basándose en la experiencia cotidiana. Al menos en este sentido, el cerebro humano es superior a una computadora limitada por circuitos lógicos puros. El cerebro humano es capaz de comprender toda la verdad contenida en los teoremas de Gödel, pero el cerebro de la computadora nunca podrá hacerlo. Por tanto, el cerebro humano es cualquier cosa menos una computadora. el es capaz decisiones, y la prueba de Turing pasará.

Me pregunto si Hilbert tenía alguna idea de hasta dónde nos llevarían sus preguntas.

Kurt Gödel, 1906-78

Matemático austriaco y luego estadounidense. Nacido en Brünn (actual Brno, República Checa). Se graduó en la Universidad de Viena, donde permaneció como profesor en el departamento de matemáticas (desde 1930 - profesor). En 1931 publicó un teorema que más tarde recibió su nombre. Siendo una persona puramente apolítica, lo pasó muy mal con el asesinato de su amigo y colega de departamento por un estudiante nazi y cayó en una profunda depresión, cuyas recaídas lo persiguieron por el resto de su vida. En los años 30 emigró a Estados Unidos, pero regresó a su Austria natal y se casó. En 1940, en plena guerra, se vio obligado a huir a América en tránsito por la URSS y Japón. Trabajó durante algún tiempo en el Instituto de Estudios Avanzados de Princeton. Desafortunadamente, la psique del científico no pudo soportarlo y murió en clínica psiquiátrica de hambre, negándose a comer, porque estaba convencido de que pretendían envenenarlo.

Cualquier sistema de axiomas matemáticos, a partir de un cierto nivel de complejidad, es internamente contradictorio o incompleto.

En 1900 se celebró en París la Conferencia Mundial de Matemáticos, en la que David Hilbert (1862-1943) presentó en forma de tesis los 23 problemas más importantes, en su opinión, que los teóricos del próximo siglo XX debían resolver. El número dos de su lista era uno de esos problemas simples cuya respuesta parece obvia hasta que profundizas un poco más. En términos modernos, ésta era la pregunta: ¿son las matemáticas autosuficientes? La segunda tarea de Hilbert se redujo a la necesidad de demostrar estrictamente que el sistema de axiomas (enunciados básicos aceptados en matemáticas como base sin prueba) es perfecto y completo, es decir, permite describir matemáticamente todo lo que existe. Era necesario demostrar que era posible definir tal sistema de axiomas que, en primer lugar, serían mutuamente consistentes y, en segundo lugar, de ellos se podría sacar una conclusión sobre la verdad o falsedad de cualquier afirmación.

Tomemos un ejemplo de la geometría escolar. En la planimetría euclidiana estándar (geometría en un plano), se puede demostrar sin lugar a dudas que la afirmación “la suma de los ángulos de un triángulo es 180°” es verdadera, y la afirmación “la suma de los ángulos de un triángulo es 137°”. °” es falso. En esencia, en la geometría euclidiana cualquier afirmación es falsa o verdadera y no existe una tercera opción. Y a principios del siglo XX, los matemáticos creían ingenuamente que debería observarse la misma situación en cualquier sistema lógicamente consistente.

Y luego, en 1931, un matemático vienés con gafas, Kurt Gödel, publicó un breve artículo que simplemente trastornó al mundo entero de la llamada “lógica matemática”. Después de largos y complejos preámbulos matemáticos y teóricos, estableció literalmente lo siguiente. Tomemos cualquier afirmación como: “El supuesto número 247 en este sistema de axiomas es lógicamente indemostrable” y llamémosla “afirmación A”. Entonces, Gödel simplemente demostró la siguiente propiedad sorprendente de cualquier sistema de axiomas:

"Si puedes probar la afirmación A, entonces puedes probar la afirmación que no es A".

En otras palabras, si se puede probar la verdad de la afirmación “el supuesto 247 es indemostrable”, entonces también se puede probar la verdad de la afirmación “el supuesto 247 es demostrable”. Es decir, volviendo a la formulación del segundo problema de Hilbert, si un sistema de axiomas es completo (es decir, cualquier enunciado que contenga puede ser probado), entonces es contradictorio.

La única salida a esta situación es aceptar un sistema de axiomas incompleto. Es decir, tenemos que aceptar el hecho de que en el contexto de cualquier sistema lógico todavía tendremos enunciados “tipo A” que son obviamente verdaderos o falsos, y sólo podemos juzgar su verdad fuera del marco de la axiomática que tenemos. aceptado. Si no existen tales afirmaciones, entonces nuestra axiomática es contradictoria y, dentro de su marco, inevitablemente habrá formulaciones que puedan ser probadas y refutadas.

De ahí la formulación del primer teorema de incompletitud, o débil, de Gödel: "Cualquier sistema formal de axiomas contiene supuestos no resueltos". Pero Gödel no se detuvo ahí, formulando y demostrando el segundo, o fuerte, teorema de incompletitud de Gödel: “La completitud (o incompletitud) lógica de cualquier sistema de axiomas no puede probarse dentro del marco de este sistema. Para probarlo o refutarlo se requieren axiomas adicionales (fortalecer el sistema)”.

Sería más seguro pensar que los teoremas de Gödel son de naturaleza abstracta y no nos conciernen, sino sólo áreas de la lógica matemática sublime, pero de hecho resultó que están directamente relacionados con la estructura del cerebro humano. El matemático y físico inglés Roger Penrose (n. 1931) demostró que los teoremas de Gödel pueden utilizarse para demostrar la existencia de diferencias fundamentales entre el cerebro humano y una computadora. El significado de su razonamiento es simple. La computadora actúa de manera estrictamente lógica y no es capaz de determinar si el enunciado A es verdadero o falso si va más allá de la axiomática, y tales enunciados, según el teorema de Gödel, existen inevitablemente. Una persona, ante una afirmación A tan lógicamente indemostrable e irrefutable, siempre es capaz de determinar su verdad o falsedad, basándose en la experiencia cotidiana. Al menos en este sentido, el cerebro humano es superior a una computadora limitada por circuitos lógicos puros. El cerebro humano es capaz de comprender toda la verdad contenida en los teoremas de Gödel, pero el cerebro de una computadora nunca podrá hacerlo. Por tanto, el cerebro humano es cualquier cosa menos una computadora. Es capaz de tomar decisiones y pasará el Test de Turing.

Me pregunto si Hilbert tenía alguna idea de hasta dónde nos llevarían sus preguntas.

Kurt GODEL
Kurt Gödel, 1906–78

Matemático austriaco y luego estadounidense. Nacido en Brünn (actual Brno, República Checa). Se graduó en la Universidad de Viena, donde siguió siendo profesor en el departamento de matemáticas (desde 1930 - profesor). En 1931 publicó un teorema que más tarde recibió su nombre. Siendo una persona puramente apolítica, lo pasó muy mal con el asesinato de su amigo y colega de departamento por un estudiante nazi y cayó en una profunda depresión, cuyas recaídas lo persiguieron por el resto de su vida. En los años 30 emigró a Estados Unidos, pero regresó a su Austria natal y se casó. En 1940, en plena guerra, se vio obligado a huir a América en tránsito por la URSS y Japón. Trabajó durante algún tiempo en el Instituto de Estudios Avanzados de Princeton. Desafortunadamente, la psique del científico no pudo soportarlo y murió en una clínica psiquiátrica de hambre, negándose a comer, porque estaba convencido de que lo iban a envenenar.

Cómo se desarrolla el modelo científico en Ciencias Naturales? Las cosas cotidianas se acumulan o experiencia científica, sus hitos están cuidadosamente formulados en forma de postulados y forman la base del modelo: un conjunto de afirmaciones aceptadas por todos los que trabajan en el marco de este modelo.

Anatoly Wasserman

En 1930, Kurt Gödel demostró dos teoremas que, traducidos del lenguaje matemático al lenguaje humano, significan aproximadamente lo siguiente: Cualquier sistema de axiomas lo suficientemente rico como para usarse para definir la aritmética será incompleto o contradictorio. No Sistema completo- Esto significa que en el sistema es posible formular una afirmación que no puede ser probada ni refutada por medio de este sistema. Pero Dios, por definición, es la causa final de todas las causas. Desde el punto de vista de las matemáticas, esto significa que la introducción del axioma sobre Dios completa toda nuestra axiomática. Si hay un Dios, entonces cualquier afirmación puede ser probada o refutada, refiriéndose, de una forma u otra, a Dios. Pero según Gödel, el sistema completo de axiomas es inevitablemente contradictorio. Es decir, si creemos que Dios existe, entonces nos vemos obligados a llegar a la conclusión de que las contradicciones son posibles en la naturaleza. Y como no hay contradicciones, de lo contrario nuestro mundo entero se desmoronaría a causa de estas contradicciones, tenemos que llegar a la conclusión de que la existencia de Dios es incompatible con la existencia de la naturaleza.

Sosinsky A. B.

El teorema de Gödel, junto con los descubrimientos de la relatividad, la mecánica cuántica y el ADN, se considera generalmente el más grande. logro científico Siglo XX. ¿Por qué? ¿Cuál es su esencia? ¿Cuál es su significado? Estas cuestiones son abordadas en su conferencia en el marco del proyecto “Conferencias públicas “Polit.ru”” de Alexey Bronislavovich Sosinsky, matemático, profesor de la Universidad Independiente de Moscú, oficial de la Orden de las Palmas Académicas de la República Francesa, premio de Premio del Gobierno Ruso en el campo de la educación en 2012. En particular, se dieron varias formulaciones diferentes, se describieron tres enfoques para su demostración (Kolmogorov, Chaitin y el propio Gödel) y se explicó su importancia para las matemáticas, la física, la informática y la filosofía.

Uspensky V. A.

La conferencia está dedicada a la versión sintáctica del Teorema de Incompletitud de Gödel. El propio Gödel demostró la versión sintáctica utilizando un supuesto más fuerte que el de la consistencia, a saber, la llamada consistencia omega.

Uspensky V. A.

Conferencias en la escuela de verano “Matemáticas Modernas”, Dubna.