A volte ritornano

[Vale]

Mi rendo conto di apparire monomaniacale ossessivo, ma vorrei riprendere la
questione del numero più grande (che aveva suscitato l'interesse di
centinaia di persone [io e Roberto Corda se non vado errato] e potrebbe
risollevare le sorti del newsgroup.

1- la questione è: qual è il numero più grande definibile con n caratteri?
2- la "definibilità" è una proprietà troppo vaga che porta direttamente a
paradossi del tipo: "1 + il numero più grande definibile con 52 caratteri".
3-si consideri allora un campo ristretto. Le macchine di Touring (MdT)
4-Sia data una MdT ha due nastri (un nastro di input e uno di output, anche
se teoricamente basterebbe un nastro) si cerca il programma P tale che:
-P è composto da massimo N caratteri
-la MdT, eseguendo P, si arresta in un tempo finito.
-Il numero di caratteri stampati dalla MdT eseguendo P sia massimo [tra
i programmi di n o meno caratteri]
5-La definizione è ben formulata poiché un programma o si arresta o non si
arresta, ovviamente. Tuttavia esiste un teorema [il teorema, guarda un po',
dell'arresto] che afferma che non esiste un algoritmo finito e meccanico
[cioè non esiste un programma per MdT] in grado di risolvere il problema
dell'arresto per ogni programma analizzato.
6- Il teorema dell'arresto non dice che non si può stabilire se un programma
si arresterà o meno, dice che una MdT non può farlo.
7- E' interessante ridefinire il massimo cercato [MAx(n)] non come il numero
di volte che la MdT stampa, ma come il numero di cicli eseguiti durante lo
svolgimento del programma.
8- Le definizioni date sono ovviamente del tutto equivalenti.
9- posta così la cosa conoscere Max(n) per i primi 1000 valori di n implica
la soluzione di pressochè tutti i problemi irrisolti della matematica!!!
10- in generale il maggiore n per cui è noto Max(n) è un buon indice dello
stato della matematica.
11- per capirci consideriamo una questione qualsiasi : "esistono perfetti
primi?"
12- scrivere un programma per cercare perfetti primi [in Basic, per esempio]
richiede non più di un centinaio di caratteri [In generale quasi tutte le
questioni irrisolte e fondamentali sono "testabili" con programmi brevi!].
Diciamo che tale programma ha 132 caratteri. allora si fa girare il
programma per un numero di cicli pari a Max(132). Se il programma trova un
perfetto dispari, bene. Se non l'ha trovato entro tale limite vuol dire che
non esiste.
13-questo è più o meno lo stato della discussione, dopo non averci pensato
più per diverso tempo, mi è capitato tra le mani un fascicoletto di Le
Scienze dal titolo "Caso, probabilità e statistica" in cui si parla di un
mirabolante numero omega. Omega è così definito:"la probabilità che una data
MdT si arresti con programma scelto a caso.". Si dimostra che la conoscenza
delle prime 1000 o 10000 cifre decimali di omega permetterebbe di risolvere
ogni questione matematica fondamentale (o quasi).
14-si osservi che è sempre possibile prendere l'insieme dei programmi per
una data MdT, numerarli [sono numerabili!!!], e costruire il numero in base
2 (chiamiamolo alfa) fatto così:
se l'ennesimo programma si arresta allora l'ennesima cifra [dopo la virgola]
vale 0, altrimenti vale 1.
15- anche tale numero da informazioni come omega sullo stato della
matematica, ma il fatto incredibile di omega è che le prime n cifre di alfa
danno informazioni su n programmi, le prime n cifre di omega [o i primi n
valori di Max(n)] danno informazioni su tutti i programmi di massimo n
cifre!!

Se qualcuno ha qualcosa da dire è le bienvenue.
Marcello

[Roberto Corda]

e ovviamente rispondo io :-)

> 6- Il teorema dell'arresto non dice che non si può stabilire se un
programma
> si arresterà o meno, dice che una MdT non può farlo.

gia' solo che la tesi di church-turing dice che ogni funzioni computabile
puo' essere
computata con una macchina di turing e viceversa. In altre parole se non
puo' farlo
un MdT non puo' farlo nessuno. Resta la possibilita' che la tesi sia
sbagliata cmq.

Vuoi dire che il problema posto potrebbe avere dei risvolti seri? Accidenti!

Roberto
[che sta riflettendo se votare o meno per it.fan.dewnwy]

[Elrond]

On 30 May 2000 10:50:21 +0200, "Vale" <nasom...@tin.it> wrote:

>Le macchine di Touring

Quelle del Club? :-))
--
ciao,
Elrond

[Vale]

> >Le macchine di Touring
>
> Quelle del Club? :-))

Ops, Turing, pardon.

marc