Pagina 1 di 1

Compattezza macchinosa

Inviato: 25 gen 2010, 15:54
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??

Inviato: 25 gen 2010, 20:27
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

Inviato: 25 gen 2010, 23:55
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.

Inviato: 26 gen 2010, 00:00
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;
    }

Inviato: 26 gen 2010, 01:05
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.

Inviato: 26 gen 2010, 02:21
da Tibor Gallai
C'è un controesempio costruibile senza cannoni, che usa solo il fatto che esistono insiemi semidecidibili ma non decidibili. :roll:

Inviato: 26 gen 2010, 09:41
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.

Inviato: 26 gen 2010, 10:17
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: ).

Inviato: 26 gen 2010, 11:40
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.

Inviato: 26 gen 2010, 11:51
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...