funzioni versus algoritmi (domanda)

[Radicale]

Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?

Cioe' una procedura finita che dato n, in qualche modo caccia
fuori f(x) (dato x) in un tempo finito ?

Non necessariamente, perche' le funzioni sono molte di piu' degli
algoritmi. Non solo, a fronte di una stessa funzione possono esistere
diversi algoritmi che la realizzano (... diciamo)
per cui se chiamo A l' insieme di tutti gli algoritmi ed F quello di
tutte
le funzioni posso anche immaginare una funzione iniettiva fatta
cosi' :
g : A -> F tale che g(a) = f.

Sia g(A) l' immagine di questa funzione in F.

Mi chiedo se g appartiene a g(A).

[AndreaM]

Post by Radicale
Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?
Cioe' una procedura finita che dato n, in qualche modo caccia
fuori f(x) (dato x) in un tempo finito ?
Non necessariamente, perche' le funzioni sono molte di piu' degli
algoritmi. Non solo, a fronte di una stessa funzione possono esistere
diversi algoritmi che la realizzano (... diciamo)
 per cui se chiamo A l' insieme di tutti gli algoritmi ed F quello di
tutte
le funzioni posso anche immaginare una funzione iniettiva fatta
g : A -> F tale che g(a) = f.
Sia g(A) l' immagine di questa funzione in F.
Mi chiedo se g appartiene a g(A).

F l'insieme di tutte le funzioni da dove a dove?

[Radicale]

F l'insieme di tutte le funzioni da dove a dove ?

F : l' insieme di tutte le funzioni. Tutte.
A : l' insieme di tutti gli algoritmi. Tutti.

[AndreaM]

Post by Radicale

F l'insieme di tutte le funzioni da dove a dove ?

F : l' insieme di tutte le funzioni. Tutte.
A : l' insieme di tutti gli algoritmi. Tutti.

Cioè stai dicendo che F è l'unione disgiunta di Hom(X,Y) al variare di
X ed Y tra gli oggetti della categoria Sets ?
Questo mi piace proprio niente.

E poi, cos'è esattamente un algoritmo, in termini matematici?

[Radicale]

Post by AndreaM
E poi, cos'è esattamente un algoritmo, in termini matematici?

Un algoritmo e' una procedura di n passi discreti che, dato un
input, produce un output in un tempo finito. Se gli input sono
uguali, lo sono pure gli output, ma puo' darsi che due input diversi
producano lo stesso output.
Ovvio che ogni algoritmo definisce una funzione iniettiva tra l'
insieme
degli input e quello degli output.

L' insieme di tutti gli algoritmi cosi' definiti e' numerabile.
Ma l' insieme di tutte le funzioni non lo e'.

Quindi esistono funzioni a fronte delle quali non troviamo
algoritmi che possano descriverle.

Ora sia g la funzione che associa ad ogni algoritmo la sua
funzione corrispondente.
Domanda :

Questa g possiede a sua volta un algoritmo oppure no ?

[Radicale]

Post by AndreaM

Post by Radicale

F l'insieme di tutte le funzioni da dove a dove ?

F : l' insieme di tutte le funzioni. Tutte.
A : l' insieme di tutti gli algoritmi. Tutti.

Cioè stai dicendo che F è l'unione disgiunta di Hom(X,Y) al variare di
X ed Y tra gli oggetti della categoria Sets ?
Questo mi piace proprio niente.
E poi, cos'è esattamente un algoritmo, in termini matematici?

Vedo che io riesco a zittirti, Socratis no.
Ma non so se e' una cosa positiva o negativa ...
:-)

[Joubert]

Post by Radicale
le funzioni posso anche immaginare una funzione iniettiva fatta
g : A -> F tale che g(a) = f.

Scusami Radicale, tu dici che l'insieme degli algoritmi è più grande di
quello delle funzioni quindi ci dev'essere una funzione iniettiva bla
bla. Però non è detto che questa g che tu hai "definito" sia iniettiva.
Non ci possono essere due algoritmi che vanno nella stessa funzione? Ad
esempio due algoritmi che vanno nell'identità? A me pare di sì. Adesso
però bisogna dire che non so assolutamente una sega di algoritmi quindi
potrei aver detto una sciocchezza. Altrimenti forse sei stato un po'
troppo generico nella definizione. Boh.

[Radicale]

Post by Joubert

Post by Radicale
le funzioni posso anche immaginare una funzione iniettiva fatta
g : A -> F tale che g(a) = f.

Scusami Radicale, tu dici che l'insieme degli algoritmi è più grande di
quello delle funzioni

No, veramente ho scritto esattamente il contrario.
L' insieme degli algoritmi e' numerabile, quello delle
funzioni e' piu' che numerabile.

[Joubert]

Post by Radicale
No, veramente ho scritto esattamente il contrario.
L' insieme degli algoritmi e' numerabile, quello delle
funzioni e' piu' che numerabile.

Intendevo il contrario anch'io, scusa. Il resto di quello che ho scritto
resta valido.

[Radicale]

Post by Joubert
Intendevo il contrario anch'io, scusa. Il resto di quello che ho scritto
resta valido.

Ah ok ! :-)

Post by Joubert
Non ci possono essere due algoritmi che vanno nella stessa funzione? Ad
esempio due algoritmi che vanno nell'identità? A me pare di sì.

si che ci possono essere.
se a1,a2 sono due algoritmi siffatti, allora g(a1) = g(a2) = f
Quindi la g non e' iniettiva, giusto.
Ma chissenefrega che non e' iniettiva

Purche' sia una funzione, cioe' che associ ad ogni algoritmo
una ed una sola funzione.

[mauro]

Post by Radicale
Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?

se la funzione e' calcolabile si' (cfr. tesi di Church-Turing)

Mauro

[Kiuhnm]

Post by Radicale
Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?

Sia A l'insieme di tutti gli algoritmi.
Sia f:A->{sì,no} la funzione t.c., per ogni a in A,
f(a) = sì <=> a termina
Non esiste alcun algoritmo che calcoli questa f.
Assumiamo per assurdo che tale algoritmo, chiamiamolo X, esista.
Consideriamo il seguente algoritmo:
Y
if (X(Y) = sì)
esegui loop infinito
else
termina

L'algoritmo Y passa se stesso a X per sapere se (Y) termina e poi si
comporta nel modo opposto, invalidando la risposta di X.

Dettaglio tecnico.
Y deve conoscere il proprio codice per poterlo passare a X.
Pensa a una macchina di Turing divisa in due parti A e B.
La parte A cancella il nastro e vi restituisce il codice di B.
La parte B esamina l'input, chiamiamolo M, su nastro e genera il codice
di una macchina che restituisca M.
Nota che, essendo Y = A B, eseguendo Y si esegue A e quindi B.
Dopo l'esecuzione di A il nastro contiene il codice di B che viene letto
da B, il quale genera il codice di una macchina che restituisce B, cioè
A. Ecco che ora conosce sia A che B, cioè Y.
Nota che B è indipendente da A, quindi un "programmatore" può prima
scrivere B e poi scrivere la funzione A che restituisce B.

Kiuhnm

[Giovanni]

Post by Kiuhnm

Post by Radicale
Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?

Sia A l'insieme di tutti gli algoritmi.
Sia f:A->{sì,no} la funzione t.c., per ogni a in A,
   f(a) = sì <=> a termina
Non esiste alcun algoritmo che calcoli questa f.
Assumiamo per assurdo che tale algoritmo, chiamiamolo X, esista.
Y
   if (X(Y) = sì)
     esegui loop infinito
   else
     termina
L'algoritmo Y passa se stesso a X per sapere se (Y) termina e poi si
comporta nel modo opposto, invalidando la risposta di X.

Un algoritmo termina per definizione.
Un programma no ma un algoritmo si'.

.
Giovanni

[Kiuhnm]

Post by Giovanni
Un algoritmo termina per definizione.

Non esiste una definizione standard.
Per es. Knuth e Kleene accettano algoritmi che non terminano e lo stesso
fanno molti altri autori.
Lo stesso faccio io in quanto ho scritto.

Post by Giovanni
Un programma no ma un algoritmo si'.

Kiuhnm

[Giovanni]

Post by Kiuhnm

Post by Giovanni
Un algoritmo termina per definizione.

Non esiste una definizione standard.
Per es. Knuth e Kleene accettano algoritmi che non terminano e lo stesso
fanno molti altri autori.
Lo stesso faccio io in quanto ho scritto.

Post by Giovanni
Un programma no ma un algoritmo si'.

Kiuhnm

Ok, possiamo allora identificare un algoritmo con un generico
programma.
Siccome non si puo' sapere a priori se un generico programma termina,
allora non possiamo nemmeno essere sicuri di avere sempre degli output
e cosi' nemmeno possiamo associarci una funzione.

Quindi g non e' calcolabile e percio' non appartiene a g(A).

.
Giovanni

[gomi no sensei]

Post by Giovanni
Siccome non si puo' sapere a priori se un generico programma termina,
allora non possiamo nemmeno essere sicuri di avere sempre degli output
e cosi' nemmeno possiamo associarci una funzione.

certo che possiamo: mettiamo di limitarci ai programmi con un parametro
naturale che ritornano valori naturali, allora le funzioni calcolate da
questi programmi saranno funzioni dai naturali ai naturali, e se un
programma non termina su input in un certo sottoinsieme dei naturali
allora la funzione che calcola semplicemente sara' una funzione parziale
che non e' definita su quel sottoinsieme

[Denis]

Post by gomi no sensei
certo che possiamo: mettiamo di limitarci ai programmi con un parametro
naturale che ritornano valori naturali, allora le funzioni calcolate da
questi programmi saranno funzioni dai naturali ai naturali, e se un
programma non termina su input in un certo sottoinsieme dei naturali
allora la funzione che calcola semplicemente sara' una funzione parziale
che non e' definita su quel sottoinsieme

Si ma come fai a sapere se "un programma non termina su input in un certo
sottoinsieme dei naturali " ?
Se mi dai la risposta ho qui pronta una dimostrazione di P!=NP per il
Claymath

[gomi no sensei]

Post by Denis
Si ma come fai a sapere se "un programma non termina su input in un certo
sottoinsieme dei naturali " ?

non lo sai, infatti l'insieme dei programmi che terminano su un dato
input non e' ricorsivamente enumerabile.

[jesko]

Post by gomi no sensei

Post by Denis
Si ma come fai a sapere se "un programma non termina su input in un certo
sottoinsieme dei naturali " ?

non lo sai, infatti l'insieme dei programmi che terminano su un dato
input non e' ricorsivamente enumerabile.
--
Call any vegetable
And the chances are good
Ooooh! The vegetable
Will respond to you

Scusa ma questa è la più grande che avete senteziato in questo ng.
Meglio del cabaret.

Un programma che termina su dato input è un numero naturale quindi il
loro insieme è numerabile.

Ciao

[Enrico Gregorio]

Post by jesko

Post by gomi no sensei

Post by Denis
Si ma come fai a sapere se "un programma non termina su input in un certo
sottoinsieme dei naturali " ?

non lo sai, infatti l'insieme dei programmi che terminano su un dato
input non e' ricorsivamente enumerabile.
--
Call any vegetable
And the chances are good
Ooooh! The vegetable
Will respond to you

Scusa ma questa è la più grande che avete senteziato in questo ng.
Meglio del cabaret.
Un programma che termina su dato input è un numero naturale quindi il
loro insieme è numerabile.

Puoi considerarlo meglio del cabaret; purtroppo stai continuando a
dimostrare di non sapere nulla e a dire sciocchezze. :(

Ciao
Enrico

[jesko]

Post by Enrico Gregorio

Post by jesko

Post by gomi no sensei

Post by Denis
Si ma come fai a sapere se "un programma non termina su input in un certo
sottoinsieme dei naturali " ?

non lo sai, infatti l'insieme dei programmi che terminano su un dato
input non e' ricorsivamente enumerabile.
--
Call any vegetable
And the chances are good
Ooooh! The vegetable
Will respond to you

Scusa ma questa è la più grande che avete senteziato in questo ng.
Meglio del cabaret.
Un programma che termina su dato input è un numero naturale quindi il
loro insieme è numerabile.

Puoi considerarlo meglio del cabaret; purtroppo stai continuando a
dimostrare di non sapere nulla e a dire sciocchezze. :(
Ciao
Enrico- Nascondi testo citato
- Mostra testo citato -

Se qualcuno invece di ripondere in modo rigoroso si mette sulla
difensiva
offendendo l'interlocutore sono due i casi o è in difficoltà a
sostenere le proprie
tesi o è un maleducato.
Se con quel messaggio vi riferite all'Halting Problem , beh avete
proprio bagliato disciplina
Ci sono hobbies molto più divertenti ma meno impegnativi.

Ciao

[Barone Barolo]

Post by jesko
Scusa ma questa è la più grande che avete senteziato in questo ng.
Meglio del cabaret.

Meglio del cabaret, dici, ma a quanto pare non meglio del cabernet.
Bevi meno, è un consiglio da enofilo.

[gomi no sensei]

Post by jesko
Scusa ma questa è la più grande che avete senteziato in questo ng.
Meglio del cabaret.

tu sei quello che non sa cos'e' una funzione, giusto?

Post by jesko
Un programma che termina su dato input è un numero naturale quindi il
loro insieme è numerabile.

cosa centra la cardinalita' di un insieme con la sua calcolabilita'?

[jesko]

Post by gomi no sensei

Post by jesko
Scusa ma questa è la più grande che avete senteziato in questo ng.
Meglio del cabaret.

tu sei quello che non sa cos'e' una funzione, giusto?

Post by jesko
Un programma che termina su dato input è un numero naturale quindi il
loro insieme è numerabile.

cosa centra la cardinalita' di un insieme con la sua calcolabilita'?
--
Call any vegetable
And the chances are good
Ooooh! The vegetable
Will respond to you

Un programma di quel tipo è descritto perfettamente da un unico numero
naturale.
Ora i naturali sono numerabili. Quindi....

Ciao

[gomi no sensei]

Post by jesko
Ora i naturali sono numerabili. Quindi....

ripeto: cosa centra la cardinalita' di un insieme con la sua
calcolabilita'? manco fosse finito...

<http://it.wikipedia.org/wiki/Ricorsivamente_enumerabile>

[jesko]

Post by gomi no sensei

Ora i naturali sono numerabili.  Quindi....

ripeto: cosa centra la cardinalita' di un insieme con la sua
calcolabilita'? manco fosse finito...
<http://it.wikipedia.org/wiki/Ricorsivamente_enumerabile>
--
Call any vegetable
And the chances are good
Ooooh! The vegetable
Will respond to you

Secondo te un insieme è calcolabile?
Ripeto ci sono molti argomenti interessanti, non so la biologia marina
l'ippica o giocare a carte o a pallone.

La matematica è la regine delle scienze e come tale è molto esigente.

Ciao

[Giovanni]

Post by Radicale
Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?
Cioe' una procedura finita che dato n, in qualche modo caccia
fuori f(x) (dato x) in un tempo finito ?
Non necessariamente, perche' le funzioni sono molte di piu' degli
algoritmi.

Giusto

Post by Radicale
Non solo, a fronte di una stessa funzione possono esistere
diversi algoritmi che la realizzano (... diciamo)
 per cui se chiamo A l' insieme di tutti gli algoritmi ed F quello di
tutte le funzioni posso anche immaginare una funzione iniettiva fatta
g : A -> F tale che g(a) = f.

L'insieme di tutte le funzioni e' un insieme molto grosso e potrebbe
incorrere in qualche problema.
Ma per il resto mi sembra tutto giusto.

Post by Radicale
Sia g(A) l' immagine di questa funzione in F.

g(A) e' un sottoinsieme di F, e rappresenta le funzioni calcolabili

Post by Radicale
Mi chiedo se g appartiene a g(A).

La domanda e' quindi se anche g e' calcolabile.
Mah, dato un algoritmo, trovare la funzione che gli corrisponde e'
certamente piu' facile che fare il contrario.
Ovviamente se si conosce lo scopo per cui e' costruito un certo
algoritmo e' ancora piu' facile trovare la funzione corrispondente
(anche perche' spesso in un algoritmo si usano appunto particolari
funzioni di calcolo).
Dato invece semplicemente un algoritmo a caso, se non si riconoscono
nella procedura delle funzioni, bisogna provare diversi input e vedere
quali output da'.
In genere bisogna studiarne la struttura per capire quali funzioni
simula.

Se g e' calcolabile allora sia G l'algoritmo che la calcola.
G prende in input un qualunque algoritmo e da' in output la funzione
corrispondente.
Quindi possiamo dare G in pasto a se stesso !
L'output in tal caso deve essere g.
Non vedo per ora una contraddizione.

.
Giovanni

[Vend]

Post by Radicale
Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?
Cioe' una procedura finita che dato n, in qualche modo caccia
fuori f(x) (dato x) in un tempo finito ?

Questa è la definizione di algoritmo che termina.
In generale esistono algoritmi che non terminano.

Post by Radicale
Non necessariamente, perche' le funzioni sono molte di piu' degli
algoritmi. Non solo, a fronte di una stessa funzione possono esistere
diversi algoritmi che la realizzano (... diciamo)
 per cui se chiamo A l' insieme di tutti gli algoritmi ed F quello di
tutte
le funzioni posso anche immaginare una funzione iniettiva fatta
g : A -> F tale che g(a) = f.
Sia g(A) l' immagine di questa funzione in F.
Mi chiedo se g appartiene a g(A).

Sì, se A è l'insieme degli algoritmi che terminano.
Altrimenti g non è definita, poichè alcuni algoritmi non corrispondono
ad alcuna funzione.

[jesko]

Post by Radicale
Data una funzione, deve da qualche parte necessariamente
esistere un algoritmo corrispondente ?
Cioe' una procedura finita che dato n, in qualche modo caccia
fuori f(x) (dato x) in un tempo finito ?
Non necessariamente, perche' le funzioni sono molte di piu' degli
algoritmi. Non solo, a fronte di una stessa funzione possono esistere
diversi algoritmi che la realizzano (... diciamo)
 per cui se chiamo A l' insieme di tutti gli algoritmi ed F quello di
tutte
le funzioni posso anche immaginare una funzione iniettiva fatta
g : A -> F tale che g(a) = f.
Sia g(A) l' immagine di questa funzione in F.
Mi chiedo se g appartiene a g(A).

Esitono più funzioni che algoritmi ----- > Cantor

Ciao

[r***@gmail.com]

Esitono più funzioni che algoritmi   ----- >  Cantor

Si, buongiorno.
Svegliato adesso ?

[jesko]

Post by r***@gmail.com

Esitono più funzioni che algoritmi   ----- >  Cantor

Si, buongiorno.
Svegliato adesso ?

No , tu invece che sei ancora ottenebrato dall'istituzionalizzazione
della teoria degli insiemi
invece? Stai dormendo?

[Radicale]

Post by jesko
No , tu invece che sei ancora ottenebrato dall'istituzionalizzazione
della teoria degli insiemi invece? Stai dormendo?

Ottenebrato dagli insiemi io ?
Mai.

Semmai dall' alcool. E' dall' '87 che non bevo piu' un goccio
d'acqua,
e mi fa schifo solo a pensarci.

[jesko]

Post by Radicale

Post by jesko
No , tu invece che sei ancora ottenebrato dall'istituzionalizzazione
della teoria degli insiemi invece? Stai dormendo?

Ottenebrato dagli insiemi io ?
Mai.
Semmai dall' alcool. E' dall' '87 che non bevo piu' un goccio
d'acqua,
e mi fa schifo solo a pensarci.

Un modico consumo di alcol può schiarire le idee su temi che
altrimenti
sarebbe avvolti da un maggior mistero.

[Radicale]

Post by jesko

Post by Radicale
Ottenebrato dagli insiemi io ?
Mai.
Semmai dall' alcool. E' dall' '87 che non bevo piu' un goccio
d'acqua,
e mi fa schifo solo a pensarci.

Un modico consumo di alcol può schiarire le idee su temi che
altrimenti sarebbero avvolti da un maggior mistero.

Sono d'accordo.
:-))