Funzioni di misura

Nel post ... si è accennato a qualche regola per le funzioni di misura. Considerazioni ovvie date dalla consuetudine, per certi versi quello del metodo scientifico (prova e riprova), sono ovvie osservazioni e ci portano a dedurre semplicemente dettagli molto difficili poi da dimostrare nella pratica. Detto in modo grezzo: aumentare le risorse ingrassa la...

L’asimmettria di NP

Una breve premessa per presentare nel blog NP, è forse la prima volta che si usa realmente. In qualche post precedente ho definito la classe P. Quella di NP è la stessa cosa, tranne che si usa NTIME: il tempo su una macchina non deterministica; per il resto rappresenta la classe dei problemi risolvibili in...

La simmetria di P

Nell'ambito della complessità ma, anche nella calcolabilità, spesso si parla di insiemi/classi complementari. Quello di cui non si parla mai è di coP: la classe dei problemi complementari a quelli in P; Come mai ? Dato un problema I in P, ci si  chiede a quale classe possa appartenere il suo complementare I (Lo scriverò...

Trattabilità vs Intrattabilità

Nell'ambito della calcolabilità si discute dei sistemi decidibili e non decidibili (ci sono anche quelli semi-decidibili). Nell'ambito della complessità delle funzioni calcolabili (il primo gruppo della calcolabilità) ci si imbatte invece nella trattabilità o meno dei problemi.

Teorema linear speed-up (accelerazione lineare)

Date due MdT: M e M' M' può simulare M con un guadagno di un fattore moltiplicativo facendo in un passo quello che la M fa in 'molti'. Basta condensare l'input. Per qualsiasi ε > 0: TIME (f(|n|)) = TIME (ε * f(|n|) * |n| ) Note: Il fattore n è aggiunto per non ottenere...

Teorema di Rice

Utilizzando il padding lemma (vedi:  Infinite macchine di Turing ) si genera un'insieme di indici partendo dal numero di Gödel. Il numero può essere visto come seme da cui si parte nella generazione. Questo insieme non contiene però non li contiene tutti. Un'insieme (A) di indici che contiene tutte gli indici di una determinata funzione è...

TIME & PTIME

La calcolabilità, mira, per quanto possibile a fornire e studiare la complessità degli algoritmo a fine di definirne delle classi. Prima definiamo le risorse; ovviamente si parlerà di tempo e spazio. E' bene ricordare che in alcuni casi le risorse possono essere anche altre: a seconda del contesto possono cambiare, nelle reti, nella mobilità, in...

Macchine deterministiche e non deterministiche

Per macchina si intende sempre la macchina di Turing non le automobili 😉 Le macchina di Turing deterministiche (MdT) sono quelle che usano per passare da una configurazione alla successiva una funzione di transizione La computazione è così univocamente determinata. Precisamente: dallo stato corrente, una porzione dei dati sul nastro (finita!) e dalla funzione transizione....

Infinite macchine di Turing

Partiamo da una funzione calcolabile  e dal suo numero di Godel (z) : questo rappresenta la computazione, la macchina, l'algoritmo che calcola la funzione. Prendiamo allora la macchina z:  aggiungiamo uno stato e una transazione fittizia (che non siano già presenti). Otteniamo così una nuova macchina, che calcola ancora la funzione di partenza! Di queste...

Teorema del parametro ( s-m-n )

Prendiamo l'insieme di tutte le funzione parziale di m + n parametri; al variare del numero di Gödel ne otteniamo una diversa, ipotizziamo di avere come numero z. Il teorema proposto da Kleene definisce che è possibile calcolare il numero di Gödel per una nuova funzione di n parametri mediante il parametro z e gli...