Newsgroup: it.comp.ia
Titolo: Incomputabilità

Ciao a tutti,
qualcuno saprebbe indicarmi qualche problema incomputabile, come la
previsione di terminazione di un programma  ma più palesemente incomputabile
( visto che non sono proprio convinto che la terminazione di un programma
sia proprio un problema incomputabile ).
Grazie .

FleX  scrive :

Prova a computare questo :
y(x) = (x! elevato a x!)fatto x!  volte  . Con x almeno = 100 , o se non
sei contento anche un po' di piu' .
Ciao
---------------------------------------------------------------------
                                                      A.L.I.E.N.
P.S.  Per rispondere via E-Mail rimuovere la "P" da 
Pri...@col.it
--
Posted from [195.210.98.12]
via Mailgate.ORG Server - 
http://www.mailgate.org

Ciao
Non intendevo qualcosa di incomputabile a causa delle scarse potenzialità
degli elaboratori , ma un problema incomputabile su un elaboratore fittizzio
con velocità di calcolo quasi infinite e capacità di memoria quasi infinite.
Quello che chiedo è un problema incomputabile dal punto di vista teorico e
non pratico. L' esempio che mi hai posto è un problema incomputabile dal
punto di vista pratico perchè non esiste un PC tanto veloce e con un
capacità di memoria tale da poter dare un risultato , ma l' algoritmo esiste
eccome se esiste ed è computabile , lo hai scritto tu stesso . Io cerco un
problema di cui non si riesca neanche a scrivere l' algoritmo .
Ciao.

 degli elaboratori , ma un problema incomputabile su un elaboratore
fittizio...
Si, in effetti il nome tecnico e' "intrattabile" (e si parla di
complessita' computazionale, non computabilita').
Avevo scritto da qualche parte una versione "italianizzata" della
dimostrazione di Turing: se la trovo la posto! :)
--
God is Real, unless declared Integer
Sent via Deja.com 
http://www.deja.com/
Share what you know. Learn what you don't.

 problema di cui non si riesca neanche a scrivere l' algoritmo .
Puoi provare a cercare in :
http://www.nd.edu/~cholak/computability/computability.html
Comunque un problema , anche se banale , incomputabile perche' non
riesci
a scrivere l' algoritmo relativo e' quello della produzione di una serie
casuale (bada bene non tipo cifre decimali di PIgreco) come quella che
viene
fuori dai lanci di una moneta .
La successione e' "incomprimibile"  in un algoritmo  di lunghezza finita
,
anche in teoria .


 sia proprio un problema incomputabile ).
E come pensi che si potrebbe calcolare la terminzaione di un programma?

hai provato con le equazioni trascendentali?
se non ricordo male sono tipo
x=sen(x)
e devi ricavare x.
e poi ci sono anche serti integrali che non si riescono a risolvere, se non ricordo male credo sia
l'integrale di "e^(x^2)" in "dx"; se non ricordo male.
ciao, doc.
Se mi vuoi scrivere devi eliminare "cippalippa." dall'e-mail.
e-mail: 
Doc...@cippalippa.bigfoot.com
 

 non pratico. 
Proprio in questi giorni sto affrontando l'esame di Metodi per il
Trattamento dell'Informazione (C.d.L Scienze dell'Informazione), il cui
programma verte proprio sulla calcolabilità e su come trattare i
problemi incalcolabili.
Quella che segue è l'introduzione del mio professore al corso
"La teoria della computabilità riguarda le funzioni calcolate da
algoritmi. Un algoritmo mal progettato ma in grado di girare, spesso non
termina per qualche valore di input. Questo fenomeno, computazioni
indefinite o divergenti, costituisce una delle caratteristiche
fondamentali della teoria della computazione. Dobbiamo rendere
matematicamente trattabile questo aspetto della teoria."
L'esempio classico di problema non calcolabile è il seguente:
PROBLEMA: Non esiste un algoritmo per decidere se un programma di
calcolo arbitrario si ferma per un input arbitrario.
Sfruttando la Tesi di Church (qualsiasi funzione definita
algoritmicamente può essere computata da un algoritmo), la
goedelizzazione (procedura di assegnamento sistematico di numeri
naturali a oggetti sintattici) ed un linguaggio di programmazione molto
semplice (il linguaggio WHILE, simile al Pascal e Turing equivalente)
si dimostra il seguente:
TEOREMA: Stabilire se un programma di calcolo arbitrario si ferma se
applicato al proprio indice è un problema indecidibile.
Un altro teorema usato per provare l'esistenza di funzioni non
calcolabili è l'argomento diagonale di Cantor.
TEOREMA: il numero di Funzioni Calcolabili è strettamente minore del
numero di Funzioni Possibili.
Dimostrazione (accennata): Si tratta di una dimostrazione in tre passi
1. #{Funzioni calcolabili} <= #{Numeri Naturali}
2. #{Parti dei Numeri Naturali} <= #{Funzioni possibili}
3. #{Numeri Naturali}<#{Parti dei Numeri Naturali} 
E' una dimostrazione quasi banale, basata sul concetto di cardinalità di
un insieme (il numero di elementi contenuti nell'insiome).
Questo ti dovrebbe bastare per dimostrare rigorosamente che esistono
funzioni non calcolabili (quindi programmi che non termineranno mai!)
Ti consiglio di leggerti il libro
A.J.Kfoury, R.N.Moll, M.A.Arbib
"Programmazione e Computabilità"
ETAS LIBRI
Se ti possono interessare gli appunti del corso suddetto, posso farti
avere delle fotocopie con tanto di esercizi d'esame ^__^.
-- 
Max Manfrin
Via Orvieto, 7
59100 Prato
Tel & Fax : 
+39 0574 35282
e-mail    : 
max.m...@conmet.it
--


Te ne sarei grato :) , grazie

...

Ciò che ho esposto è solo un dubbio che ho , dovuto probabilmente a delle
carenze nella conoscenza dell' argomento .
Comunque per quanto riguarda  la terminazione di un programma io l' ho
pensata in questi termini : ho un certo linguaggio costituito da una serie
di istruzioni ognuna delle quali esegue delle operazioni che modificano la
memoria o stato e contemporaneamente il cui funzionamento dipende dalla
memoria o stato (per cui riesco a prendere la fascia più estesa dei
linguaggi formali) .
Ora fatte queste ipotesi posso dire sicuramente che se l' elaboratore si
trova ad eseguire più di una volta l' istruzione di tipo I alla posizione P
e con uno stato o memoria O , il programma non terminerà mai .
A questo punto ho trovato dei casi in cui un programma non termina ma niente
mi dice che questi siano tutti i casi in cui un programma non termina.
Per dire qualcosa sugli altri casi dovrei fare delle altre ipotesi.
1) Il numero di istruzioni di un programma deve essere non infinito.
2) Il numero di stati o quantità di memoria deve essere non infinito.
Facendo queste ipotesi mi sembrerebbe che un programma non terminerà  se e
solo se è verificata la condizione che ho detto in precedenza  e cioè che ci
sia una ripetizione di (I,P,O) , per cui il problema della terminazione
passerebbe da incomputabile ad intrattabile.
Ovviamente queste potrebbero essere delle grosse restrizioni.
Che ne pensi?
Ciao e grazie per l' interesse , Flex
Fl...@geocities.com









 Che ne pensi?
Questo è il modo classico di affrontare il problema della fermata nel
caso in cui l'insieme di operazioni e lo spazio di memoria dell'agente
di calcolo siano finiti.
In tal caso l'agente di calcolo può assumere solo un numero finito di
configurazioni, infatti l'insieme dei programmi che terminano diventa un
insieme ricorsivo (ovvero la sua funzione caratteristica è computabile).
Le condizioni di non terminazione si controllano proprio con la tecnica
da te esposta.
Purtroppo per noi, la teoria della computazione impone dei criteri cui
sia gli algoritmi che gli agenti di calcolo devono sottostare, e
precisamente i seguenti:
ALGORITMO
1. La sequenza di istruzioni deve essere finita (Non sono esclusi i
cicli)
2. Deve esistere un "agente di calcolo" capace di eseguire le istruzioni
3. Il calcolo avviene per passi discreti (non sono accettate cose del
tipo "genera tutti i numeri primi")
4. Il calcolo è deterministico (stesso input --> stesso output)
AGENTE DI CALCOLO
1. L'agente di calcolo ha memoria illimitata ed infinita
2. Non ci sono limiti all'input (ma deve essere finito)
3. Sono ammesse esecuzioni con passi illimitati e infiniti (cicli while,
o until)
Sono d'obbligo due osservazioni: Nella teoria dei sistemi interattivi
l'input non viene presentato tutto insieme prima della computazione;
Accettare algoritmi che non terminano è un prezzo da pagare per avere
più generalità.
 
Problemi collegati a questo sono la decidibilità dell'appartenenza di
una stringa ad un linguaggio generato da una grammatica. I risultati
teorici sono i seguenti:
Grammatica di tipo 0 (libere) - L'appartenenza è semidecidibile
Grammatica di tipo 1 (contestuali) - Decidibile in tempo esponenziale
rispetto alla lunghezza della stringa
Grammatica di tipo 2 ( context free) - Decidibile in tempo polinomiale
rispetto alla lunghezza della stringa
Grammatica di tipo 3 (regolari) - Decidibile in tempo lineare rispetto
alla lunghezza della stringa
Le grammatiche LL e LR sono meno espressive delle context free ma si
calcolano in modo meno che polinomiale ma più che lineare (questo è
quanto mi basta per i linguaggi di programmazione).
Un buon libro sui linguaggi formali è il seguente:
Thomas A.Sudkamp
"Languages and Machines" 
An Introduction to the Theory of Computer Science - 2nd Edition
ADDISON WESLEY 
ISBN 0-201-82136-2


 2) Il numero di stati o quantità di memoria deve essere non infinito.
Il numero di stati di un programma (intendendo con "programma" ciò che viene
preso in considerazione nel problema della terminazione) è illimitato,
quindi non si può applicare la tua idea che dimostra soltanto che la
terminazione di un automa a stati finito è decidibile.

...

Mi sembra un po' impossibile però costruire un elaboratore con memoria ( e
per cui stati ) infinita , per cui mi sembra un restrizione non tanto
campata in aria

 wrote in message 7kj9h3$rir$1...@fe2.cs.interbusiness.it...

Non infinita, illimitata. Sono due cose diverse.
Non è affatto difficile immaginare di costruire un calcolatore con memoria
illimitata, anzi direi che i normali pc lo sono (basterebbe costruire un'
interfaccia a cui si possono collegare un numero qualsiasi di moduli di
memoria).
Tu cercavi un problema indecidibile in qualche modo più concreto del
problema della terminazione, ma in realtà tutti i problemi indecidibili sono
di questo genere. Hanno cioè un qualcosa di "illimitato" nella loro
formulazione.
Prendi ad esempio questo problema: date in input due stringhe ed un certo
numero di regole di riscrittura decidere se la seconda stringa si può
ottenere dalla prima per mezzo di applicazioni ripetute delle regole di
riscrittura. Se si ammette che le regole possono essere di un tipo
abbastanza generale questo è un problema indecidibile. Nella "generalità"
delle regole deve essere ammesso che le stringhe prodotte non abbiano
nessuna limitazione in lunghezza (pur rimanendo finite!). Non appena si
impone che le regole non possano produrre stringhe di lunghezza superiore un
limite prefissato il problema diventa decidibile (basta applicare le regole
in tutti i modi possibili fino ad aver prodotto tutte le stringhe di
lunghezza inferiore al limite).

Sorry, non ho letto tutti i follow-up, per cui è possibile che qualcuno
abbia già detto quello che sto per scrivere.
Quello che tu esponi, è un perfetto algoritmo che decide in tempo finito se
il programma X termina o meno durante la sua esecuzione con particolari
parametri di input.
Ciò che è rende intrattabile il problema invece è:
a) il programma X termina per OGNI suo input?
b) come posso determinare se il programma X termina per OGNI input?
Capirai che, tranne che per casi piuttosto banali, ciò non può essere
determinato facilmente.
In più, se non ti bastasse, IL problema intrattabile non è neanche quello
appena esposto, ma il seguente:
!!!) Come determinare (in un tempo finito) la classe dei problemi che NON
terminano in un tempo finito?
Capirai che, anche se per ogni programma potessi determinare se termina o
meno in un tempo finito, ci sarà sempre un programma che termina almeno
un'istruzione dopo il numero di istruzioni che sono disposto a seguire.
Perciò il fatto di spostare l'attenzione sull'insieme di stati, non fa altro
che spostare il problema su: come posso determinare l'insieme di stati (che
tra parentesi dovrebbero contenere gli input) che fanno terminare il
programma, posto che questo insieme, anche se finito per ogni programma, ha
dimensioni qualunque?
Come vedi, il vero problema è, in un certo senso, su un gradino più elevato
di quello che tu dici (e di cui hai fornito un elegantissimo algoritmo
risolutivo con un numero prefissato di passi, la cardinalità dell'insieme
degli stati possibili), anche senza introdurre infiniti o amenità varie.
Il problema dell'intrattabilità è ancora diverso, e si basa sui tempi di
esecuzione, ma fortunatamente quando si parla di teoria, questi non sono un
problema. Possiamo benissimo pensare di far funzionare un PC per quanti
miliardi di anni vogliamo, purchè alla fine sputi fuori il risultato.
Spero di essere stato chiaro, comunque esistono parecchi libri/articoli in
cui viene spiegato meglio.
Alessandro Monti
--
Posted from 
ro...@polic.cilea.it
 [131.175.215.1]


O anche che le regole non possano essere applicate più di un tot di volte, o
che esse siano di forma particolare (mi sembra linguaggi di tipo 2, ma non
ricordo bene).
Vero per l'illimitatezza, come ho spiegato anche in un'altra risposta, ma
ciò non dovrebbe spaventare, ciò che interessa non è IL caso specifico, di
norma decidibile, la CLASSE di casi.
NOTA: perchè un programma non termini è già necessario introdurre il
concetto di illimitatezza, per cui non ha senso poi scandalizzarsi se questo
produce altre quantità illimitate.
Per mantenere l'esempio della produzione di stringhe a partire da regole, un
programma che NON termina, necessariamente deve fare qualcosa senza fine. O
è un programma fesso che tenta più volte la stessa strada, oppure sta è
intelligente (o se vogliamo corretto) e sta seguendo tutte le infinite
strade per arrivare alla soluzione (o una strada infinita). Un esempio
tipico è nelle prime pagine del libro già gitato "Godel, Escher, Bach", con
solo 3 regole, di cui 2 che aumentano la dimensione della stringa, e una che
le riduce (se non ricordo male, l'ho letto qualche anno fa).


Grazie per tutte le risposte ricevute  ( "Godel, Escher, Bach" lo ho  letto
finalmente :) ) comunque mi sembra che in generale la risposta sull'
incomputabillità sia strettamente legata alla risposta della seguente
domanda : è sempre possibile dare un limite superiore alla memoria di un
programma ?
In un Pc lo si potrebbe far coincidere con le capacità hardware messe a
dispoizione , ma in generale si dovrebbe scoprire se esiste in natura un
dispositivo fisico tale da poter gestire indirizzamenti relativi tipo liste
, code ,ecc..
Comunque anche l' esistenza di queste strutture non implicherebbe l'
impossibilità dell'esistenza di un limite massimo  .
Alla fine si arriverebbe a chidersi se la memoria dell' universo sia finita
, in qual caso questo sarebbe in ogni caso il limite massimo .
Comunque ai fini pratici l' esistenza o meno di un limite reale è pressochè
ininfluente visto che posso comunque porre un limite fittizzio in base alle
necessità del programma , per cui in pratica posso sempre implementare un
problema NC.

 problema NC.
Esattamente. Solo che non sarai mai sicuro che ti risponda.
Idem ovviamente per NP, qui il problema è che non sai quando risponderà.
Alessandro Monti
P.S.
Ho notato che ho scritto delle inesattezze in vari post precedenti, spero mi
perdonerete, i miei neuroni biologici talvolta fanno cilecca.