Teorema de incompletitud de Gödel en 20 minutos

, , . . , - . — , , «, ». ( ), -, «, , ». , , , , . , , , , , , , .

, ? « » . , , . , ( , -, ), - .

— , — . , , « ». , , « » /, 15-20 .

, , . .

, , . - . , : «$$$\forall x \; (x-1)(x-2)-2=x(x-3)$» (, $$$\forall$ « » « »). , , , :

1. $$$\forall x \; (x-1)(x-2)-2=x(x-3)$
2. $$$\forall x \; x^2-3x+2-2=x^2-3x$
3. $$$\forall x \; x^2-3x–x^2+3x=0$
4. $$$\forall x \; 0 = 0$

. 4- 5- , , , — . , , . — - . . ( ), ( ) .

. , - , , $$$S$ — , . , $$$P$, $$$S$ : ( $$$B$ ).

— $$$S$ $$$P$ $$$S$ $$$B$ — « ». , . , « !» , , , .

. — . : «» — («»), . — - , . , — , , .

: $$$P$ « » (, , «»), , , ? : ? , , , — . , .

, . . -, , « $$$X$ » « $$$X$». , , . (, ), — . , , :

• $$$x, y, z$ $$$n>2$, $$$x^n+ y^n = z^n$.

( ). . , , ( ) .

. , - ( ) . ? , . , . — . — . . , . , - . — , — . , . , : « , » — .

« » , , . - , , .

, , , «» ( « » « » — ). , , , $$$\sin x$ , . , , — , . , , , — , , , .

« ». , , ( ), , , , , $$$\exists$ («») $$$\forall$ (« ») , , - ( ). , (, «$$$12 = + \forall x>$» — ). ( , ) .

:

• $$$1=1$
• $$$2\times2=5$
• $$$\exists x \; x>3$
• $$$\forall y \; \forall z \; y\times z>y+z$

.. « » () , , . ( $$$x$):

• $$$x=0$
• $$$2\times2=x$
• $$$\exists y \; x+y>x$

.. , .

$$$F$. , (, , — ..; , ). , $$$k$ , $$$F_k$.

:

• .

.

, , . $$$A$, $$$k$ :

1. $$$k$- $$$F$.
2. $$$k$ .
   
3. ( , ), .
4. .

, , .

, .

, , , $$$F$ , , – . :

• : , , - $$$F$.

, , , , . , , . , , , , , Brainfuck, , , , . , — , , .

, .

, $$$A$. , , . - $$$F$ — , $$$n$. , $$$F_n(n)$? . , $$$A$ ( , $$$F_n$), , $$$n$ $$$F_n$ — . : $$$F_n(n)=$ $$$F_n(n)=$. , , . , . .

(. ), , , , — , . ( « ») : « ». , , .

, . , , (, , ?). . , .

, , . , . , :

• "Cualquier frase en el idioma chino es una declaración verdadera si está contenida en la cita del camarada Mao Zedong, y es incorrecta si no lo está".

Entonces, el algoritmo de prueba completo y consistente correspondiente (se puede llamar "deducción dogmática") se parece a esto:

• “Desplácese por la cita del camarada Mao Zedong hasta que encuentre la declaración que está buscando. Si se encuentra, entonces es cierto, y si el libro de citas ha terminado y no se encuentra la declaración, entonces es incorrecto ".

Aquí nos salva el hecho de que cualquier libro de citas es obviamente finito, por lo que el proceso de "prueba" inevitablemente terminará. Por lo tanto, TGN no es aplicable al lenguaje de las declaraciones dogmáticas. Pero estábamos hablando de idiomas complejos, ¿verdad?