Federico Calboli ha scritto:
Perchè è un linguaggio di programmazione, ed essendo Turing-completo,
Scusate l'ignoranza, cosa si intende per linguaggio "Turing completo" (a
saper chi e` Turing ci arrivo, ma oltre no)?
Il link di Tannoiser fornisce la definizione, io provo a spiegare meglio
il problema: uno dei teoremi fondamentali della computabilità insegna
che non è possibile, in generale, stabilire se un programma scritto in
un linguaggio Turing-completo andrà in loop o prima o poi terminerà.
Sembra inutile, ma i matematici sono fatti così e bisogna svolgere un pò
quanto loro danno per scontato.
Io ho un programma A che fa una cosa che mi serve, ma ha un baco che non
riesco a individuare; vorrei scrivere un programma B che esaminando il
programma A mi dicesse dov'è il baco. Prevedendo che presto avrò lo
stesso problema con un programma C, in realtà vorrei che B individuasse
un baco in un programma arbitrario (sorvoliamo su cosa costituisce un
baco). Ciò è equivalente a trasformare A in un programma A' (operazione
nota come compilazione) che si ferma quando si verifica il baco: ma se
A è scritto in un linguaggio Turing completo, in generale, ciò non è
possibile.
Siamo passati da individuare se un programma terminerà a se un programma
avrà per una data funzione del suo stato un valore vero a un certo punto
della sua esecuzione (a quel punto mi fermerei): il teorema ci dice che
analizzare un programma per mezzo di un altro, in generale, è
impossibile. Potrebbe sembrare che la scappatoia consista nell'eseguire
il programma sotto il controllo di un altro che controlla se la funzione
diventa vera, ma il teorema buttato fuori dalla porta rientra dalla
finestra: non saprò mai, durante tale esecuzione, se la funzione non
diventerà mai vera (e quindi se l'esecuzione si fermerà).
Il problema è che quasi tutti i linguaggi utili sono Turing completi:
basta un ciclo con condizione. Quando si riesce a esprimere un
comportamento utile usando una notazione che non è Turing completa, la
cosa apre la porta a tante applicazioni interessanti.
Davide Bolcioni
--
There is no place like /home.
|