Compattezza macchinosa

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Compattezza macchinosa

Messaggio da edriv »

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??
geda
Messaggi: 125
Iscritto il: 30 ott 2007, 12:03

Messaggio da geda »

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
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

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]
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

C'è un controesempio costruibile senza cannoni, che usa solo il fatto che esistono insiemi semidecidibili ma non decidibili. :roll:
[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]
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

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]
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

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 :oops: ).
[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]
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto »

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.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

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...
[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]
Rispondi