Teoria della computabilità

[cammeddru]

Salve, dato che per ora sto utilizzando molto la programmazione per il calcolo scientifico, mi risulta ovvio capire cosa è in grado di computare la macchina, ovvero quali sono le potenzialità e i limiti. Sapete consigliarmi un buon libro sulla calcolabilità/complessità che sia abbastanza completo però, non introduzioni o quant`altro perchèTesto visibile solo ai moderatori e all'autore del post quel tipo di libri non mi piace nemmeno un po’.

[Raptorista]

È una domanda un po' vaga, e inoltre nel calcolo scientifico si sorvola su certi aspetti che sono importanti per gli informatici invece. Che cosa vuoi imparare di preciso?

Moderatore: Raptorista

e scusate il linguaggio

Scusiamo niente. Evita.

[cammeddru]

Di preciso quali siano le funzioni calcolabili e quali no. Cioè per esempio il logaritmo di un numero è una funzione calcolabile o devo arrivarci tramite approssimazione con i polinomi di taylor ? ovviamente che ne parli in modo abbastanza approfondito. Ĕ un esempio banale e neache so se sia corretto ma credo che riesca ad esplicare bene il concetto.

[gugo82]

Moderatore: gugo82

@cammeddru: Per farti modificare il testo del post dobbiamo inviarti una raccomandata, oppure credi che due avvisi gialli bastino?
Facci sapere, così ci attrezziamo...

[cammeddru]

L`ho cambiato secondo i dettami del forum.

[Raptorista]

L`ho cambiato secondo i dettami del forum.

Grazie per la collaborazione.

Tornando alla tua domanda, i computer usano una rappresentazione finita dei numeri reali, il che è un altro modo di dire che i computer possono memorizzare solo alcuni numeri razionali, e nessun irrazionale [ma solo approssimazioni più o meno buone]. Non è possibile nemmeno memorizzare il numero \(\frac 1 3\), per esempio, e tanto meno \(\ln 2\) o cose simili. Un computer sa fare solo le operazioni aritmetiche di base, le operazioni logiche e un altro paio di trucchetti [tipo bit-shift] e con quelle si deve arrangiare. Ogni volta che un computer calcola un seno, un logaritmo o altro in realtà usa dei trucchi per ottenere una buona approssimazione, come ad esempio un'approssimazione in serie.

Non so se c'è del buon materiale a riguardo. Ricordo che all'inizio di Quarteroni, Sacco, Saleri, Gervasio se ne parla [capitolo 2] ma non c'è molto perché la verità è che non è una questione molto interessante.
Le questioni interessanti relative a "ciò che si può calcolare" sono più che altro quelle di complessità degli algoritmi, tipo P=NP e simili.

[feddy]

Riguardo a quello che dice Raptorista, una lettura interessante è questa

[Albesa81]

per esempio il logaritmo di un numero è una funzione calcolabile o devo arrivarci tramite approssimazione con i polinomi di taylor ? ovviamente che ne parli in modo abbastanza approfondito. Ĕ un esempio banale e neache so se sia corretto ma credo che riesca ad esplicare bene il concetto.

Se vuoi approfondire queste tematiche, potrebbe esserti utile consultare un qualche testo di analisi numerica o di calcolatori elettronici; il link di feddy è un ottimo punto di partenza. Della teoria della computabilità propriamente detta se ne occupa più che altro l'informatica teorica.