Teorema da incompletude de Gödel em 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)=$. , , . , . .

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

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

, , . , . , :

• "Qualquer frase no idioma chinês é uma afirmação verdadeira se estiver contida na citação do camarada Mao Zedong e estiver incorreta se não estiver".

Então, o algoritmo de prova completo e consistente correspondente (pode ser chamado de "dedução dogmática") é mais ou menos assim:

• “Percorra a citação do camarada Mao Zedong até encontrar a declaração que está procurando. Se for encontrado, é verdade, e se o livro de cotações acabou e a declaração não foi encontrada, está incorreto. ”

Aqui somos salvos pelo fato de que qualquer livro de cotações é obviamente finito, de modo que o processo de "prova" inevitavelmente terminará. Assim, o TGN não é aplicável à linguagem dos enunciados dogmáticos. Mas estávamos conversando sobre linguagens complexas, certo?