Quote:
Originariamente inviato da SUPERALEX
nn risolvibile nel senso che nn termina...cosa che va contro la definizione di algoritmo
|
Non si capisce bene dall'articolo perchè non utilizzano termini formali.
Non risolvibile nel senso di non computabile significa che non esiste alcun algoritmo che risolva il problema. Il primo esempio è l'halting problem (o problema dell'arresto) formulato da Turing nello stesso articolo in cui gettava le basi della teoria della computabilità. Puoi guardarti la dimostrazione che non è troppo complicata. In sostanza dice che non esiste un algoritmo che per ogni programma ti sappia dire se questo termina oppure no.
Plausibilmente nell'articolo si intende non risolvibile nel senso di non efficientemente computabile intendendo con questo la classe dei problemi NP-hard non in P, ovvero quei problemi per cui non esiste un algoritmo deterministico con complessità polinomiale. Infatti finora la computazione quantistica non si è dimostrata capace di andare oltre la Turing completezza (ovvero i problemi non computabili per i computer odierni lo sono anche per i computer quantistici) e d'altronde se ciò si rivelasse errato, l'intera teoria della computabilità andrebbe riscritta!