Decidibilità congettura di Goldbach

[Rggb]

[ titolo modificato ]

Vista la giovane vita di questa sezione ne metto uno io - è di livello universitario, quindi "facile". Categoria: teoria della calcolabilità.

Teorema: dato il linguaggio della terminazione $L_(\s\t\o\p)$, o equivalentemente il problema della terminazione, dimostrare che se il linguaggio è decidibile allora la congettura di Goldbach è dimostrabile.

[gugo82]

[mod="gugo82"]

[ Il titolo è volutamente fuorviante: recentemente è tornato di moda, pure su questo forum ]

E dovresti sapere che i titoli fuorvianti non sono molto apprezzati, soprattutto se possono dar adito a clamorosi OT.
Quindi sei pregato di modificarlo almeno un po', grazie.[/mod]

[Rggb]

@gugo82
Non ho resistito Comunque hai ragione; titolo modificato.

PS.

soprattutto se possono dar adito a clamorosi OT

Previdente, ma se partono OT "clamorosi" pure qui, c'è da pensare...

[Deckard]

Tralasciando ogni formalizzazione:
basta costruire una procedura contenente un ciclo che per ogni numero pari maggiore di due controlla se esso può essere scritto come somma di due numeri primi. Se no, il ciclo termina e il programma restituisce 0 (la congettura di Goldbach è falsa), altrimenti continua a ciclare per esaminare gli altri numeri primi.
Il programma è facilmente implementabile. Se "Turing non fosse mai esistito" allora, poiché l'halting problem sarebbe decidibile, esisterebbe un algoritmo in grado di dirci se tale programma si arresta e in questo caso la congettura di Goldbach sarebbe falsa (esiste un numero pari n che non può essere scritto come somma di due primi), oppure continua ad essere eseguito all'infinito, ovvero non esiste un numero pari n per cui la congettura di Goldbach è falsa e quindi tale congettura sarebbe vera.

[nochipfritz]

La decidibilità del problema di Goldbach può essere espressa così: SPERO DI NON SBAGLIARMI!!!

definiamo un operatore di sottrazione "speciale" (che è già stato dimostrato calcolabile)
$x--y= x-y$ se $x \geq y$
e
$x--y=0$ altrimenti

a questo punto definiamo l'operatore di minimalizzazione limitata come segue

$f(m) = \mu z <m (1 -- Pr(z) \cdot Pr(2m -- z) = 0)$

dove $Pr(x)$ è la funzione che restituisce 1 se x è primo e 0 altrimenti ($Pr(x)$ è calcolabile).

Per la teoria della calcolabilità $f(m)$ è calcolabile.

A questo punto impostando la funzione

$g(n) = 1$ se $Pr(f(n/2)) \cdot PARI(n) = 1$
$g(n) = 0$ se $Pr(f(n/2)) \cdot PARI(n) = 0$


dove $PARI(n)$ è anch'essa calcolabile e restituisce 1 se n è pari e 0 se n è dispari.

In definitiva g(n) è la composizione di funzioni calcolabili , quindi è calcolabile e da qui deriva che il predicato $M(n) = "n \in GOLDBACH" $ dove $GOLDBACH$ è l'insieme di tutti i numeri pari che si possono esprimere come somma di due primi è decidibile.

[nochipfritz]

Aggiungo che se Goldbach è decidibile (a me sembra che lo sia ...almeno che ho fatto degli errori formali nella dimostrazione) ...questo non dimostra che tutti i numeri pari si possono esprimere come somma di due primi. Anzi il fatto che Goldbach è decidibile rende il problema della dimostrazione che tutti i pari stanno nell'insieme $GOLDBACH$, ancora più lontana.