cos'è un modello di calcolo?

• astrazione di una classe di agenti di calcolo (esecutori di algoritmi)

ingredienti tipici di un modello di calcolo:

• interazione ingresso/uscita con l'ambiente
• capacità di memoria (illimitata)
• nucleo essenziale di primitive di calcolo
• transizioni di stato dipendenti dall'ingresso e dallo stato

N.B. per semplicità, la classe degli algoritmi in considerazione è limitata al calcolo di funzioni sui numeri naturali, cioè di tipo N^m→N

• il calcolo di funzioni di altro tipo può ridursi a questo mediante codifica

a che servono i modelli di calcolo?

• fondamentalmente: a stabilire cosa non è calcolabile (!)
• a prefigurare nuovi sistemi di calcolo e paradigmi di programmazione

un modello di calcolo concettualmente fedele all'architettura Von Neumann:

• memoria: una sequenza illimitata di registri R₁, R₂, ..., R_n, ...
  da cui il nome del modello: Unlimited Register Machine (URM)
• istruzioni primitive:
  • Z(n)       azzera R_n
  • S(n)        incrementa R_n
  • T(m,n)    copia R_m in R_n
  • J(m,n,q)  salta alla q-sima istruzione se R_m e R_n hanno uguale
                  contenuto, altrimenti procedi in sequenza
• interazione I/O: mediante (alcuni dei) registri

la classe delle funzioni URM-calcolabili coincide con la classe delle funzioni calcolabili da una Macchina di Turing

non tutte le funzioni sui numeri naturali sono URM-calcolabili:

• l'insieme delle funzioni sui naturali ha la cardinalità del continuo
• l'insieme delle URM è numerabile
• ogni URM calcola esattamente una funzione (parziale) sui naturali

per la stessa ragione, non miglior sorte tocca alla sottoclasse delle funzioni in questione costituita dalle funzioni caratteristiche di appartenenza a un insieme (sottoinsieme di N^m), le quali hanno immagine in {0, 1}

• ovvero: non tutti i predicati sui naturali sono URM-decidibili

decidibilità di un insieme = calcolabilità della sua funzione caratteristica

un insieme è semidecidibile, ovvero ricorsivamente enumerabile, se è calcolabile la sua funzione caratteristica parziale, data dalla co-restrizione della funzione caratteristica all'immagine {1}:

• i.e. coincide con la caratteristica se questa vale 1, altrimenti è indefinita

una Macchina di Turing (MdT), modello già noto dalle lezioni precedenti, è essenzialmente determinata dal suo programma, e calcola dunque una (sola) funzione, tuttavia ...

esiste una MdT in grado di calcolare ogni funzione calcolata da qualsiasi MdT, e detta pertanto MdT Universale (MdTU)

• come è possibile? non c'è qui una palese contraddizione?

il "trucco" sta nell'ingresso della MdTU, la quale emula una data MdT: una codifica di questa (ovvero del suo programma) e il suo input costituiscono l'input della MdTU

• geniale intuizione del concetto di macchina da calcolo a programma memorizzato, ovvero di calcolatore general purpose

epperò anche la MdTU ha i suoi limiti, non diversi da quelli delle URM

• il caso che segue li rivela, in connessione profonda con il paradosso di Russell, il teorema di incompletezza di Gödel e la diagonalizzazione di Cantor

problema: decidere, per qualsiasi MdT M e input I, se l'esecuzione di M con input I giunga o meno all'arresto

ipotizziamo per assurdo la decidibilità del problema: esiste allora una MdT P che, con input M*bI, dà output 1 quando M con input I si arresta, 0 in caso contrario, dove M* è la codifica di M e b è il simbolo blank che li separa nel nastro

• P, dunque, si arresta in ogni caso

l'arresto di una MdT avviene per mancanza di istruzioni applicabili, possiamo quindi aggiungere opportune istruzioni a P per ottenere una MdT Q che

• non si arresta mai quando M con input I si arresta
• si arresta con output 0 quando M con input I non si arresta

esiste poi una MdT S che duplica il contenuto del nastro e poi esegue Q su tale input

• che succede se si esegue S con input la sua stessa codifica S* ?

dopo la duplicazione di S* sul nastro, S esegue Q con input S*bS*... si traggono due conclusioni alternative, che ricordano quelle del paradosso di Russell:

• S con input S* non si arresta quando S con input S* si arresta con output 0
• S con input S* si arresta con output 0 quando S con input S* non si arresta

qui però non siamo in presenza di un paradosso, bensì di una dimostrazione dell'assurdità dell'ipotesi di decidibilità del problema dell'arresto della MdTU

il λ-calcolo, fondamento della programmazione funzionale, fu ideato da A. Church per fondare la matematica sul concetto (intensionale) di funzione quale regola di calcolo

• sintassi dei λ-termini:     E ::= V | λV.E | (EE)

dove il non-terminale V produce un insieme infinito di variabili e l'operatore di astrazione lega una variabile nell'ambito di un λ-termine

• la giustapposizione designa l'applicazione funzionale; la semantica del λ-calcolo va dunque cercata in un opportuno spazio di funzioni (di ordine superiore), che permetta fra l'altro l'autoapplicazione

analogamente a quanto accade con i quantificatori nella logica predicativa, si definiscono le variabili libere di un λ-termine, la libera sostituibilità di un λ-termine per una variabile in un λ-termine, e si stipula l'α-convertibilità di λ-termini

• ovvero l'invarianza semantica per ridenominazione di variabili vincolate

le regole del λ-calcolo formalizzano la relazione (binaria) di β-riduzione "→" fra λ-termini, che mutua il nome dalla regola:

• (β)       (λx.E)M → E[x/M]

dove E[x/M] è il λ-termine ottenuto da E per sostituzione delle occorrenze libere di x con M (dopo l'eventuale ridenominazione di variabili vincolate in E, per garantire la libera sostituibilità)

le altre regole del λ-calcolo formalizzano le proprietà di riflessività, transitività e chiusura per contesti della β-riduzione, nonché le proprietà della relazione di equivalenza (invero, congruenza) da essa generata, detta β-convertibilità

per l'applicabilità in contesto della β-regola, ossia a sottotermini propri di un dato λ-termine, questo può avere riduzioni distinte; il Teorema di Church-Rosser garantisce che ciò non danneggia la semantica funzionale della β-riduzione:

• confluenza: se E → M e E → N, allora esiste F tale che M → F e N → F
• se M e N sono β-convertibili, allora hanno un comune β-ridotto

un combinatore è un λ-termine privo di variabili libere; eccone esempi significativi:

• Ω = (λx.xx)(λx.xx)
• I = λx.x, K = λx.λy.x, S = λx.λy.λz.(xz)(yz)

Ω mostra l'esistenza di β-riduzioni infinite; la β-regola in questo caso dà solo Ω→Ω

le riduzioni dei combinatori I, K, S, possono essere formalizzate senza ricorso esplicito alla λ-astrazione, ottenendo così un calcolo applicativo senza variabili vincolate, detto logica combinatoria:   Ix → x, Kxy → x, Sxyz → (xz)(yz)

• N.B. dove si conviene che l'applicazione associ a sinistra: EMN = (EM)N

un λ-termine è una forma normale se non è suscettibile di β-riduzione

• il termine x è una forma normale

un λ-termine ha una forma normale se è β-riducibile ad una forma normale

• il combinatore Ω non ha forma normale

il fatto che un termine abbia forma normale non garantisce che ogni sua β-riduzione termini, tuttavia vale l'unicità della forma normale:

• se un λ-termine ha una forma normale, allora questa è unica

il calcolo di funzioni sui numeri naturali nel λ-calcolo si rappresenta mediante una rappresentazione dei numeri, e di operazioni elementari quali: successore, condizionale, coppia ordinata e proiezioni, etc., quali combinatori

• Church (1941) rappresenta i numeri naturali mediante i seguenti combinatori (tutti forme normali): λfλx.fⁿx, dove f⁰x = x e fⁿ⁺¹x = f(fⁿx)

una funzione sui naturali è λ-calcolabile se esiste un combinatore che, applicato alle rappresentazioni degli argomenti, β-riduce alla rappresentazione del risultato ogniqualvolta la funzione sia definita

1. ideare un programma URM per il calcolo della somma di due numeri
2. se un predicato è semidecidibile, e lo è anche la sua negazione, allora il predicato è decidibile; perché?
3. la composizione di funzioni λ-calcolabili è λ-calcolabile; perché?
4. reperire in rete la definizione della funzione di Ackermann e farsi un'idea della sua velocità di crescita; cosa si può dire in proposito?
5. ciascuno dei modelli di calcolo indicati alla fine della lezione costituisce un tema suscettibile di vari approfondimenti, quali: caratteristiche del modello, rappresentazione del calcolo nel modello, relazione con altri modelli, paradigmi correlati, etc. (né questa lista di tipi di approfondimento, né la lista di modelli proposta, sono esaustive)