title: L (linguaggio)
text: # L (linguaggio)
  
  Il linguaggio L è un linguaggio di programmazione ideato da Albert R. Meyer e da Dennis Ritchie che calcola solamente funzioni ricorsive primitive. I programmi scritti in linguaggio L prendono il nome di "programmi Loop" (Loop programs).
  
  ## Istruzioni
  
  Il linguaggio L prevede cinque tipi di istruzioni:
  
  * azzeramento: V = 0
  * incremento: V = V + 1
  * assegnazione: V = V'
  * ciclo: LOOP V
  * termine del ciclo: END
  
  Le istruzioni 4 e 5 si comportano come le parentesi.
  
  Un blocco di codice inserito tra un LOOP-END viene eseguito esattamente il numero di volte del valore assunto dalla variabile V all'inizio del ciclo, indipendentemente dal fatto che tale valore possa variare nel corso dell'iterazione. Questo assicura la terminazione dei programmi Loop.
  
  ## Profondità di nidificazione
  
  È possibile inserire cicli all'interno dei blocchi LOOP-END. Un programma che presenta n cicli annidati ha profondità n ed appartiene alla classe $L_{n}$. Un programma che utilizza solo le istruzioni 1, 2 e 3 ha profondità 0 ed appartiene alla classe $L_{0}$.
  
  Se ${\mathcal {L}}_{n}$ è la classe delle funzioni calcolabili dai programmi appartenenti alla classe $L_{n}$, ${\mathcal {L}}=\bigcup _{n=_{0}}^{\infty }{\mathcal {L}}_{n}$ è la classe delle funzioni calcolabili in L.
  
  ## Funzioni ricorsive primitive
  
  Il linguaggio L calcola tutte le funzioni ricorsive primitive essendo le funzioni base calcolabili utilizzando programmi di profondità 0 ed essendo la classe ${\mathcal {L}}$ chiusa per composizione e ricorsione.
  
  ## Tempo di esecuzione
  
  Il tempo di esecuzione di un programma Loop è il numero d'istruzioni eseguite per calcolare la funzione. La funzione $T_{P}(x_{1},\ldots ,x_{n})$ di un programma P $\in L_{n}$ appartiene a ${\mathcal {L}}_{n}$.
  
  