la definizione di funzione usuale in matematica e' fatta in termini insiemistici:
una funzione f:X→Y e' un particolare sottoinsieme di XxY, cioe' f∈P(XxY) f appartiene all'insieme delle parti di XxY.
{ f∈P(XxY) : ∀x∈X ∃!(x,y)∈f } e' l'insieme delle f da X a Y.
ref: Funzione da un insieme ad un altro. | Spazio funzionale delle funzioni da un insieme ad un altro.
D: E' possibile descrivere esattamente ogni particolare funzione ?
Si puo' pensare a funzioni definibili in tutti i modi che si possono creare, non solo con le usuali 4 operazioni o operazioni geometriche.
R: Fino a che si rimane negli insiemi finiti, tutto si puo' dettagliare-costruire elencando in termini finiti. Questo si puo' ritenere calcolabile almeno in linea di principio, poiche' quando i nr diventano grandi, elencare diventa impossibile in pratica per limiti di tempo e materia.
Ma cosa dire quando si considera una funzione di dominio infinito, ad es una f sui numeri naturali?
f:ℕ→ℕ o anche solo f:ℕ→{0,1} quante sono? hanno la potenza del continuo, non sono numerabili.
Dobbiamo renderci conto che
la calcolabilita' dipende dal
MODELLO DI CALCOLO
Prima richiesta: data una funzione f, la descrizione di ogni immagine f(x) deve essere finita: un nr finito di parole di un alfabeto finito.
Corollario: non ci sono abbastanza descrizioni per descrivere tutte le funzioni, poiche' sono di piu' che numerabili.
Turing pensava che il modo-modello di calcolo dovesse essere un CALCOLO MECCANICO, quindi penso' a un meccanismo materialmente realizzabile, che fosse facilmente schematizzabile matematicamente, e poi sviluppo' la teoria di tale modello matematico.
La macchina di Turing e' un modello matematico di computazione.
L'esito dello studio dei matematici e' stato
use different representations for the functions, function inputs and outputs, but
models translate one in the other,
describe essentially the same functions
giving rise to the opinion that formal computability is both natural and not too narrow.
Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions that later were shown to be equivalent, and lead to the definition of computable funtions.
a function computable from a computer program is a computable function.
Cioe': una funzione computabile in senso informale, lo e' anche in senso formale.
Non provabile poiche' lega l'ambito informale dei calcolo reale a quello formale dei modelli di calcolo. E' una linea guida accettata.
i suoi valori si possono determinare con un programma di computer.
occorre formalizzare la nozione di procedimento di calcolo, cioe'
dato un input, come calcolare il corrispondente output.
The class of computable functions can be defined in many equivalent models of computation.
≡ computer science ≡ theory of computation,
detta anche "recursion theory", poiche' il calcolo in generale e' definito come operazione ricorsiva.
La "scienza del calcolare", come ogni scienza deve circoscrivere l'oggetto di studio, e quindi indagare-decidere cosa intendere per "calcolare" nel senso piu' generale possibile.
Risponde la: computability, computability theory; a branch of computer science and mathematical logic;
introduce i concetti di: computability, effective computability, computable set, computable function.
Some commentators argue that both the names "recursion theory" and "computability theory" fail to convey the fact that most of the objects studied in computability theory are not computable.
in informatica le chiamano "macchine" o "macchine astratte", ma per chi viene dal di fuori dell'informatica teorica, es io, risulta confusionario: sono macchine, ma macchine di calcolo, in 1 parola "calcolatori".
ebiquity.umbc.edu/how-dr-suess-would-prove-the-halting-problem-undecidable
A "computer", originally 1930s-40s, was a person who performed arithmetic calculations.
precisely /prɪˈsʌɪsli/
in exact terms; without vagueness.
"the guidelines are precisely defined"
exactly (used to emphasize the complete accuracy or truth of a statement).
"at 2.00 precisely, the phone rang"
dove /dʌv/ colombo colomba
1. Doves are generally smaller and more delicate than pigeons, but many kinds
have been given both names.
2. a person who advocates peaceful or conciliatory policies, especially in
foreign affairs.
"he was the cabinet's leading dove, the only minister to advocate peace talks"
The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics
exist translations between any two models, and so every model describes essentially the same class of functions