Compattezza macchinosa
Compattezza macchinosa
C'è una congettura che ci è venuta in mente durante il Winter Camp:
abbiamo una sequenza di naturali $ s(n) $ e un programma (tipo macchina di Turing) che, ricevendo in input un intero n, stampa la successione $ s_1,s_2,\ldots,s_n $.
Si può dire che esiste un programma che, non ricevendo nessun input, stampa tutta la successione senza terminare??
abbiamo una sequenza di naturali $ s(n) $ e un programma (tipo macchina di Turing) che, ricevendo in input un intero n, stampa la successione $ s_1,s_2,\ldots,s_n $.
Si può dire che esiste un programma che, non ricevendo nessun input, stampa tutta la successione senza terminare??
Forse ho capito male, ma mi sembra di si. Se il programma che genera la sequenza dato un n si chiama s(n), basta costruire un programma piu' grande che contiene s(n) come subroutine del tipo:
01 n=1
02 Stampa l'n-simo numero di s(n)
03 n=n+1
04 goto 02
05 end
Ho capito male?
PS: Per la procedura "Stampa l'n-simo numero di... " si possono immaginare numerosi sequenze di comandi e non e' un problema
01 n=1
02 Stampa l'n-simo numero di s(n)
03 n=n+1
04 goto 02
05 end
Ho capito male?
PS: Per la procedura "Stampa l'n-simo numero di... " si possono immaginare numerosi sequenze di comandi e non e' un problema
Ah sì, certo. -.-
Comunque effettivamente avevamo anche una versione meno banale del problema: ora l'ipotesi è che esista un programma che soltanto per infiniti input n (non necessariamente per tutti) stampa la successione $ s_1,s_2, \ldots, s_n $.
Ora è chiaro che serve quest'ipotesi più forte rispetto all'avere semplicemente un progamma che stampa $ s_n $ per infiniti n.
Comunque effettivamente avevamo anche una versione meno banale del problema: ora l'ipotesi è che esista un programma che soltanto per infiniti input n (non necessariamente per tutti) stampa la successione $ s_1,s_2, \ldots, s_n $.
Ora è chiaro che serve quest'ipotesi più forte rispetto all'avere semplicemente un progamma che stampa $ s_n $ per infiniti n.
Codice: Seleziona tutto
numeri_stampati=0;
for(n=0;;n++)
for(k=0;k<n;k++)
esegui un'istruzione di P_k;
if(P_k ha terminato){
stampa tutte le cifre da numeri_stampati+1 fino a k;
numeri_stampati=k;
}
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
No aspetta, è più complicato perchè il programma P_k potrebbe benissimo terminare per qualche input k, ma scrivere un mucchio di fandonie. Tutto quello che sappiamo è che esistono infiniti valori di k (ma non sappiamo quali valori) il programma stampa l'output corretto, ovvero i valori della successione da 1 a k.
Il punto è che se l'insieme dei valori "buoni" di k fosse calcolabile (anzi, basta che un suo sottoinsieme infinito sia calcolabile), potremmo scrivere un programma simile a quello di fph per stampare la successione.
Il problema nasce dal fatto che quest'insieme di valori buoni potrebbe essere non calcolabile, e a questo punto sfuma la possibilità di una dimostrazione semplice, cioè tramite l'esibizione esplicita di un programma che sfrutti i vari P_k per stampare tutta la successione.
D'altra parte, credo che anche un controesempio alla tesi non sarebbe tanto banale da trovare.
Il punto è che se l'insieme dei valori "buoni" di k fosse calcolabile (anzi, basta che un suo sottoinsieme infinito sia calcolabile), potremmo scrivere un programma simile a quello di fph per stampare la successione.
Il problema nasce dal fatto che quest'insieme di valori buoni potrebbe essere non calcolabile, e a questo punto sfuma la possibilità di una dimostrazione semplice, cioè tramite l'esibizione esplicita di un programma che sfrutti i vari P_k per stampare tutta la successione.
D'altra parte, credo che anche un controesempio alla tesi non sarebbe tanto banale da trovare.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Beh, allora, da semi-profano di teoria della calcolabilità, mi sembra anche più semplice di così: supponi per assurdo che esista il programma magico e considera il momento (finito) in cui stampa $ s_1 $. Sono state eseguite un numero finito di istruzioni, quindi sono stati "toccati" un numero finito di programmi $ P_i $, diciamo un sottoinsieme di $ P_1, P_2,\dots,P_n $. Questo dovrebbe essere vero per ogni scelta della successione $ (P_i) $, ma è chiaro che puoi scegliere $ P_{n+1}, P_{n+2},\dots $ in modo che gli output di $ P_1, P_2,\dots,P_n $ siano solo spazzatura.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Non so se ci stiamo capendo. Credo che edriv intendesse fissare un programma $ $P $, e che i suoi $ $P_k $ siano in realtà dei $ $P(k) $, ovvero gli output di $ $P $ su input $ $k $.
Detto ciò, non ho capito l'ultimo post di fph (non ho capito nemmeno qual è la tesi che dimostra ).
Detto ciò, non ho capito l'ultimo post di fph (non ho capito nemmeno qual è la tesi che dimostra ).
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Da come l'ho interpretata io dimostra che non esiste un tale programma se la non sappiamo che la successione dei P_k buoni è calcolabile.
Mi sembra che l'assunzione di fph sia che il metaprogramma si prenda in pasto la lista dei P_k, e restituisca la successione. Come fa vedere fph un tale metaprogramma non può esistere.
Mi sembra che l'assunzione di fph sia che il metaprogramma si prenda in pasto la lista dei P_k, e restituisca la successione. Come fa vedere fph un tale metaprogramma non può esistere.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Sì ma non è questa la richiesta del problema. Non dev'esserci nessun metaprogramma... Dev'esserci solo un programma P che ogni tanto spara fuori segmenti iniziali di una successione non calcolabile. Voglio dire che P non è input di nessun metaprogramma, ovvero non deve necessariamente esistere una procedura che, dato P, stampa la successione.
Esempio: P(n) è una sequenza di n volte 0, oppure n volte 1, a seconda di n. Le 2 successioni "plausibili" sono solo 0000... e 1111..., e sono entrambe calcolabili. Tuttavia P(n) può enumerare l'una o l'altra con pattern arbitrariamente contorti... Non so se mi spiego.
Comunque: il mio controesempio funziona in realtà sotto delle ipotesi più deboli, perché avevo letto male il testo. Ovvero: per ogni n, esiste un k tale che P(k) = (s1, s2, ..., sn). In questo caso c'è una semplice costruzione che fa saltare tutto. Per il caso più specifico descritto da edriv invece non ho una risposta pronta, ma ho forti sospetti che sia vero...
Esempio: P(n) è una sequenza di n volte 0, oppure n volte 1, a seconda di n. Le 2 successioni "plausibili" sono solo 0000... e 1111..., e sono entrambe calcolabili. Tuttavia P(n) può enumerare l'una o l'altra con pattern arbitrariamente contorti... Non so se mi spiego.
Comunque: il mio controesempio funziona in realtà sotto delle ipotesi più deboli, perché avevo letto male il testo. Ovvero: per ogni n, esiste un k tale che P(k) = (s1, s2, ..., sn). In questo caso c'è una semplice costruzione che fa saltare tutto. Per il caso più specifico descritto da edriv invece non ho una risposta pronta, ma ho forti sospetti che sia vero...
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]