Funzioni Analitiche
La funzione f è detta analitica se esprime una relazione
tra valori in un dominio X e in un codominioY:
per ogni
e
il codomino Y è anche detto insieme immagine del dominio
X secondo la funzione f. Il dominio X è anche detto
insieme di definizione.
Una funzione analitica fornisce quindi una relazione, espressa mediante
una formulazione matematica, tra valori del dominio e del codominio. La
condizione di analiticità è espressamente caratterizzata dal fatto che
tutto il dominio è mappato nel suo insieme immagine con valori univoci.
Funzioni computabili, macchine di Turing
Diamo in questa sede una definizione formale di una macchina di Turing,
rimandando il lettore ad un approfondimento in rete.
Una macchina di Turing (deterministica ad un solo nastro) è definita
dalla quadrupla DTM = (Q, S, f, s0) ove
- Q è l’insieme finito degli stati ammessi dalla DTM
- S è l’insieme dei simboli o alfabeto che la DTM
gestisce, inclusi i simboli speciali di controllo. - f è la funzione di transizione da Q x S ® Q x S x
D - D è l’insieme dei comandi di controllo del nastro D = {avanti,
indietro, stop} - s0 è lo stato iniziale.
La DTM è programmata definendo la funzione di transizione f
tra gli stati che, per ogni stato corrente q e simbolo correntemente
osservato sul nastro s, definisce lo stato successivo, il simbolo
da scrive