Vaig llegir, si no recordo malament a Microsiervos, una anotació que parlava sobre nombres que no són computables (és a dir: nombres reals tals que no existeix cap algorisme que els calculi). El primer que vaig pensar era que no podia ser possible, que tot nombre real havia de poder ser aproximat amb tanta precisió com es volgués; pensant-hi una mica més profundament, però, resulta que és ben cert.
Remeto aquí una demostració que m'ha vingut al cap per demostrar l'existència d'aquests nombres (la demostració en si no té res en especial -si no no l'hagués trobat-, és només d'idea feliç):
Enunciat: Existeixen nombres tals que no poden ser calculats amb un algorisme amb una precisió tan gran com es vulgui.
Demostració:
Considerem el conjunt de tots els algorismes que poden ser implementats en un ordinador: per força han de ser algorismes finits. Tals algorismes estan escrits amb els caràcters usuals: per tant, podem pensar en un algorisme com una fila de caràcters ordenats l'un darrere l'altre. Definim, doncs, una bijecció entre aquests algorismes i els nombres naturals:
Senzillament comptem quants caràcters s'utilitzen per a fer els algorismes -podem suposar que els algorismes s'escriuen en codi ASCII, que té 128 caràcters diferents-, i enviem cada algorisme al seu corresponent nombre en un sistema de numeració en base 128. Evidentment molts d'aquests "nombres" no tindran sentit com a algorismes, per tant el conjunt d'algorismes implementats i amb sentit és un conjunt més petit, i és un subconjunt dels nombres naturals (tot i que és un subconjunt prou gran com per seguir tenint el mateix cardinal: n'hi ha prou amb pensar, per exemple, que en qualsevol algorisme ben implementat hi podem afegir el caràcter "espai" arbitràriament i seguirà funcionant). La resta és història: els nombres naturals i els nombres reals no tenen el mateix cardinal, i es conclou la prova.
Em sembla una cosa ben curiosa tenir la idea d'això: la part intel·ligent no és la demostració, sinó l'enunciat.
Per cert, si voleu veure una demostració que els nombres reals i els nombres naturals no tenen el mateix cardinal (per dir-ho intuïtivament -però malament!-, que el conjunt dels nombres reals és més gran que el dels naturals) aneu aquí.
Remeto aquí una demostració que m'ha vingut al cap per demostrar l'existència d'aquests nombres (la demostració en si no té res en especial -si no no l'hagués trobat-, és només d'idea feliç):
Enunciat: Existeixen nombres tals que no poden ser calculats amb un algorisme amb una precisió tan gran com es vulgui.
Demostració:
Considerem el conjunt de tots els algorismes que poden ser implementats en un ordinador: per força han de ser algorismes finits. Tals algorismes estan escrits amb els caràcters usuals: per tant, podem pensar en un algorisme com una fila de caràcters ordenats l'un darrere l'altre. Definim, doncs, una bijecció entre aquests algorismes i els nombres naturals:
Senzillament comptem quants caràcters s'utilitzen per a fer els algorismes -podem suposar que els algorismes s'escriuen en codi ASCII, que té 128 caràcters diferents-, i enviem cada algorisme al seu corresponent nombre en un sistema de numeració en base 128. Evidentment molts d'aquests "nombres" no tindran sentit com a algorismes, per tant el conjunt d'algorismes implementats i amb sentit és un conjunt més petit, i és un subconjunt dels nombres naturals (tot i que és un subconjunt prou gran com per seguir tenint el mateix cardinal: n'hi ha prou amb pensar, per exemple, que en qualsevol algorisme ben implementat hi podem afegir el caràcter "espai" arbitràriament i seguirà funcionant). La resta és història: els nombres naturals i els nombres reals no tenen el mateix cardinal, i es conclou la prova.
Em sembla una cosa ben curiosa tenir la idea d'això: la part intel·ligent no és la demostració, sinó l'enunciat.
Per cert, si voleu veure una demostració que els nombres reals i els nombres naturals no tenen el mateix cardinal (per dir-ho intuïtivament -però malament!-, que el conjunt dels nombres reals és més gran que el dels naturals) aneu aquí.
.png)
3 comentaris:
Això és una conseqüència del fet (que, més o menys, ja descrius) que tot i que el cardinal del conjunt de tots els subconjunts de N és més gran que el cardinal de N, el del conjunt de tots els subconjunts finits de N sí que és el cardinal de N.
Sant Cantor!!!!!!
Sí, sí, és clar. El que em sembla curiós és fer el pas de números a calculabilitat per algorismes :)
Ja em semblava a mi que no podia ser qualsevol cosa... M'ha agradat investigar què és aquesta gran parrafada llatina...
Fins dimecres!!!
I.
Publica un comentari a l'entrada