[Generale]Come si impara un linguaggio di programmazione?

[cdimauro]

Ma i linguaggi che usiamo generalmente sono Turing-completi.

[PGI-Bis]

Il problema non è se l'applicazione sia piccola o grande, se sia Hello World o tutto il codice di Windows. Il problema è che non è possibile dimostrare nello stesso modo che la decidibilità del programma "Hello World" valga anche per il programma "Windows". O è possibile ma allora non sarà possibile dimostrare che il programma "JVM" sia decidibile nello stesso modo di "Hello World" e "Window". O magarì per quei tre vale ma...eccetera eccetera...ci sarà sempre almeno un programma la cui decidibilità non è dimostrabile come lo è per tutti gli altri.

Non dice affatto che uno specifico programma sia dimostrabilmente privo di bug.

Questo per come l'ho capita io: la faccenda è molto complicata.

[cdimauro]

E lo è sicuramente. Il nocciolo della questione è che non è possibile realizzare un'applicazione che sia in grado di decidere se una qualunque altra applicazione sia bacata o meno (senza tirare in ballo il concetto di arresto).

Quindi è una questione prettamente programmatica o, usando un termine caro a noi programmatori, di automazione di questo tipo di calcolo, che è irrealizzabile.

Su singole, specifiche, applicazioni la questione è decidibile o meno, a seconda se riusciamo a produrre una dimostrazione.
Quindi data l'applicazione f e l'input x provare che il calcolo viene completato (non c'interessa il tempo, purché sia sicuramente finito) e l'output sia effettivamente y (quello che ci aspettavamo).

Questo sul piano formale rimanendo nell'ambito della pura teoria della computabilità.

Nella realtà, invece, la situazione è anche peggiore, perché valgono anche le considerazioni di Kralizek, per cui anche il tuo banalissimo "Hello, world!" può risultare bacato, a seconda delle condizioni esistenti al momento della sua esecuzione.

[Kralizek]

Originariamente inviato da cdimauro

E lo è sicuramente. Il nocciolo della questione è che non è possibile realizzare un'applicazione che sia in grado di decidere se una qualunque altra applicazione sia bacata o meno (senza tirare in ballo il concetto di arresto).

Quindi è una questione prettamente programmatica o, usando un termine caro a noi programmatori, di automazione di questo tipo di calcolo, che è irrealizzabile.

Su singole, specifiche, applicazioni la questione è decidibile o meno, a seconda se riusciamo a produrre una dimostrazione.
Quindi data l'applicazione f e l'input x provare che il calcolo viene completato (non c'interessa il tempo, purché sia sicuramente finito) e l'output sia effettivamente y (quello che ci aspettavamo).

Questo sul piano formale rimanendo nell'ambito della pura teoria della computabilità.

Nella realtà, invece, la situazione è anche peggiore, perché valgono anche le considerazioni di Krallo, per cui anche il tuo banalissimo "Hello, world!" può risultare bacato, a seconda delle condizioni esistenti al momento della sua esecuzione.

fixed, so che é stupido, ma Kralizek é troppo "ufficiale", un po' come se mi chiamassi "sig. Nome Cognome" :P

[cdimauro]

OK, Krallo.

[banryu79]

Credo sia neccessario, per chiarezza, considerare sempre il linguaggio in cui è espresso il programma in questione.

[1]
Come si legge in quelle pagine di Wikipedia, un Decider (macchina che termina sempre) è meno potente di una MdT, però non soffre del problema della fermata (che anzi garantisce sempre).

Il fatto è che un Decider ha a che fare con programmi espressi in linguaggi ricorsivi.

La MdT invece, ha a che fare con linguaggi ricorsivamente enumerabili e c'è il problema della fermata.
Per come l'ho capita io, le implicazioni di questo teorema non sono che "non è mai possibile determinare se un programma terminerà in un tempo finito" o meno, ma soltanto(si fa per dire) che "non è possibile realizzare un algoritmo che riesca a determinare se un programma terminerà o no, per qualsiasi programma espresso in un linguaggio ricorsivamente enumerabile ci venga in mente".

[2]
Prendendo l'esempio di PGI:

public class Main {
    public static void main(String[] args) {
        System.out.println("hello world");
    }
}

Questo programma è un esempio di programma che, seppur scritto in un linguaggio ricorsivamente enumerabile (Java) non presenta operazioni che ne rendano impossibile determinare quando terminerà.

Cito un passaggio importante:

In pratica, è possibile costruire una macchina che termini sempre, e già computa molte funzioni interessanti, come da esempio, quando si limita le capacità di controllo di flusso così che nessun programma farà entrare la macchina in un ciclo infinito. Come esempio banale, un albero di decisione finito non contiene cicli, così termina naturalmente. Non si richiede che la macchina non abbia capacità di svolgere cicli. Se si limitano i cicli ad un ben definito limite prevedibile (come il ciclo FOR in BASIC), possiamo esprimere tutte le funzioni ricorsive primitive (Meyer and Ritchie, 1967). Un esempio di tale macchina è fornito dal linguaggio di programmazione giocattolo PL-{GOTO} di Brainerd e Landweber (1974).

Quindi come una MdT, per determinati programmi, non riesce "a consumare" tutto il flusso di esecuzione a tal punto da riuscire a dire che il programma terminerà oppure entrerà in un ciclo infinito senza prima esserci entrata lei stessa nel ciclo infinito, così non è (secondo me) possibile garantire con un algoritmo che un programma scritto in un linguaggio Turing-completo sia privo di bug, proprio perchè quell'algoritmo deve essere mandato in esecuzione con il modello di calcolo della MdT stessa, soffrendo dei limiti associati al problema della fermata.

Certo ciò non significa che "è impossibile scrivere un programma privo di bug" ma solo che "è impossibile provare, per qualsiasi programma espresso in un linguaggio ricorsivamente enumerabile, eseguito da una MdT, che quel programma è privo di bug".

O almeno è quello che ho capito io.
Come ha detto marco.r, forse bisogna passare ad un altro modello diverso da quello della MdT.

[Kralizek]

certo che a studiare teoria della computazione, leopardi si sarebbe sparato una dose endovena. "questa roba" (cit.) é piú pessimista di lui



(tralasciamo che in realtá lui fosse un ottimista secondo alcuni critici letterari, per la massa lui é Il Pessimista)

[cdimauro]

E non avrebbe avuto tutti i torti.

Comunque le macchine che terminano sempre (decider) risolvono soltanto una parte dei problemi formalizzabili sotto forma di algoritmi. Non possono, pertanto, computare tutti i tipi di problemi che una macchina Turing-completa (o equipotente che dir si voglia) è in grado di risolvere.

Se praticamente tutti i linguaggi di programmazione conosciuti sono Turing-completi non è certo per capriccio, ma perché serve la loro "potenza espressiva".

Per quanto riguarda il problema di bug / terminazione & affini, è corretta l'interpretazione di banryu (e di PGI in precedenza), ma... anche l'osservazione di monsieur Krallo.

[~FullSyst3m~]

Originariamente inviato da PGI-Bis

Teoria e pratica, teoria e pratica, teoria e pratica. Agitare (mai mescolare!) per un cinque-sei anni di seguito, ogni giorno, non meno di quattro ore al giorno. Tutta la teoria, dall'orientamento agli oggetti alla gestione della memoria, dai database ai modelli di sviluppo software, algoritmi, analisi matematica - uhhh quanta analisi, ci finisci quasi in analisi dopo tutta quell'analisi.

Quando studi un linguaggi ti prendi uno, due tre libri su quel linguaggio, li leggi - non sia mai che si pensi che basti prenderli . Ripetutamente, leggi. Ci sono libri che a volte rileggendoli verrebbe da dire: "Ohilà, ma questo non è il libro che ho letto l'altra volta!". Poi c'è la rete che è una preziosa fonte di informazione con tutti i blog di personaggini mica da ridere, le mailing list degli sviluppatori, i whitepaper e gli studi pubblicati da aziende e università. C'è anche tanta monnezza ma quella di solito la distingui dopo un po' che pascoli per i prati telematici.

Ci sono i forum in cui puoi trovare spunti di riflessioni ma anche risposte. Ah, i forum. Ricordo quando mi avventurai le prime volte su quello ufficiale di Sun.

- Salve, sto imparando Java, avrei un dubbio su...
- LEGGI IL FOTTUTO MANUALE!!!

Ahhh, americani, sempre così affabili con i principianti...

Questa dell'agitare 4 ore al giorno per 5/6 anni non me l'avevi mai detta... mi hai dato pacco in pratica

Poi tu che andavi nei forum??