Hay algunos problemas que son imposibles de resolver. No porque se necesite a alguien que sea un genio para resolverlos, sino porque simplemente no tienen solución. Estos problemas ponen un límite a lo que se puede resolver mediante el cómputo.
El más famoso de estos problemas es el Halting Problem (HP) o Problema de la detención en español.
El enunciado de este problema es: "Dada una descripción de un programa y una entrada inicial, determinar si el programa, cuando se ejecuta con esa entrada, se detiene".
En 1936 Alan Turing demostró que un algoritmo general para resolver este problema para todas las posibles entradas no podía existir.
Aunque las consecuencias de resolver este problema podrían parecer triviales a simple vista (un compilador que determine si el programa que estamos compilando tiene un loop infinito), son muy importantes.
Una de las más importantes es que no podemos construir un algoritmo para determinar si un enunciado acerca de los números naturales es verdadero. Esto está relacionado con la principal búsqueda de los matemáticos a principios del siglo XX: un algoritmo que dado un enunciado (posible teorema), determine si éste es verdadero. Si HP pudiera resolverse, entonces muchos teoremas podrían ser fácilmente probados mediante el sencillo procedimiento de hacer un algoritmo de fuerza bruta que pruebe todos los posibles valores y se detenga en el primer valor que no cumpla el enunciado. Luego determinamos si el algoritmo se detiene, si es así, entonces el teorema no se cumplía. La mayoría de los problemas abiertos de teoría de números, caerían ante este procedimiento. Los matemáticos de principios del siglo XX eran bastante ambiciosos.
De todas formas se puede argumentar que ese algoritmo sólo es teórico, ya que en la práctica las computadoras tienen un límite en la cantidad de números que pueden representar y sería imposible chequear todos los naturales.
Halting problem
sábado, 30 de diciembre de 2006
martes, 12 de diciembre de 2006
Geeksta rap II
Esta es la primer canción nerdcore que escuché. Si la entienden y se cagan de risa ya no hay vuelta atrás, jaja. Los mp3's se pueden bajar de www.monzy.com y esta canción de KillDashNine.mp3
I guess I'll have to shut you down for good this time,
Already tried a SIGQUIT, so now it's KILL DASH 9.
You gotta learn when it's time for your thread to yield;
It shoulda slept; instead you stepped and now your fate is sealed.
I'll take your process off the run queue without even asking
'Cause my flow is like reentrant and preemptive multitasking.
Your sad rhymes are spinnin' like you're in a deadlock,
You're like a synchronous sock that don't know when to block;
So I pull out my keyboard and I pull out my glock,
And I dismount your girl and I mount /proc
And I've got your fuckin pid and the bottom line
Is that you best not front or else it's KILL DASH NINE.
KILL DASH NINE,No more CPU time.
I run KILL DASH NINE,
And your process is mine.
I run KILL DASH NINE,
'Cause it's MY time to shine
So don't step outta line or else it's
KILL DASH NINE!
See it ain't about the Benjamins or Pentiums or Athlons,
But you rappin' 50 meters while I'm spittin' in decathlons.
Your shit's old and busted, mine's the new hotness;
You're like CLR and I'm like CLRS.
You're running csh and my shell is bash,
You're the tertiary storage; I'm the L1 cache.
I'm a web crawling spider; you an Internet mosquito;
You thought the 7-layer model referred to a burrito.
You're a dialup connection; I'm a gigabit LAN.
I last a mythical man-month; you a one-minute man.
It's like I'm running Thunderbird and you're still stuck with Pine,
Which is why I think it's time for me to KILL DASH NINE.
Yeah it's KILL DASH NINE
No more CPU time.
'Cause it's KILL DASH NINE,
And your process is mine.
I said KILL DASH NINE
'Cause it's my time to shine,
So don't step outta line or else it's
KILL DASH NINE!
My posse throws down like leaky bucket regulators;
I was coding shit in MIPS while you were playing Space Invaders.
With my finger on the trigger I run ./configure
Yo, this package is big, but MY package is bigger.
I roll my weed with Zig Zag while I zag-zig splay,
And I do a bounds check before I write to an array.
I'm a loc'd out baller writing KLOCS a day,
'Cause it's publish or perish, fool, what can I say?
I'm 26 now, will I live to see 28?
Some days I wonder if I'll survive to graduate.
But hey, that's just fine, I won't ever resign,
And if fools try to step then it's KILL DASH NINE!
Yeah it's KILL DASH NINE,
From my command line
It's KILL DASH NINE
Sending chills down your spine,I said KILL DASH NINE,
'Cause it's my time to shine,
So don't step outta line or else it'sKILL DASH NINE!
fs sa rlidwka
I'll chown your home and take your access away
Comin' straight outta Stanford, ain't nobody tougher,
Control-X, Control-C, I'll discard your fuckin' buffer.
You're outside your scope, son, close them curly brackets,
'Cause I drop punk-ass bitches like a modem drops packets.
Dump your motherfucking core, and trace your stack
'Cause where your ass is going, there won't be no callback.
See my style is divine and my code is sublime,
My career's in a climb and yours is in a decline.
I'll write a pound-define and assign you as mine,
So refine those sad rhymes or remove your plus signs,
Or it's KILL DASH NINE,
No more CPU time,
'Cause it's KILL DASH NINE,
And your process is mine,
I said KILL DASH NINE'Cause it's my time to shine,
Bitch you stepped outta line and now it's KILL DASH NINE!
I guess I'll have to shut you down for good this time,
Already tried a SIGQUIT, so now it's KILL DASH 9.
You gotta learn when it's time for your thread to yield;
It shoulda slept; instead you stepped and now your fate is sealed.
I'll take your process off the run queue without even asking
'Cause my flow is like reentrant and preemptive multitasking.
Your sad rhymes are spinnin' like you're in a deadlock,
You're like a synchronous sock that don't know when to block;
So I pull out my keyboard and I pull out my glock,
And I dismount your girl and I mount /proc
And I've got your fuckin pid and the bottom line
Is that you best not front or else it's KILL DASH NINE.
KILL DASH NINE,No more CPU time.
I run KILL DASH NINE,
And your process is mine.
I run KILL DASH NINE,
'Cause it's MY time to shine
So don't step outta line or else it's
KILL DASH NINE!
See it ain't about the Benjamins or Pentiums or Athlons,
But you rappin' 50 meters while I'm spittin' in decathlons.
Your shit's old and busted, mine's the new hotness;
You're like CLR and I'm like CLRS.
You're running csh and my shell is bash,
You're the tertiary storage; I'm the L1 cache.
I'm a web crawling spider; you an Internet mosquito;
You thought the 7-layer model referred to a burrito.
You're a dialup connection; I'm a gigabit LAN.
I last a mythical man-month; you a one-minute man.
It's like I'm running Thunderbird and you're still stuck with Pine,
Which is why I think it's time for me to KILL DASH NINE.
Yeah it's KILL DASH NINE
No more CPU time.
'Cause it's KILL DASH NINE,
And your process is mine.
I said KILL DASH NINE
'Cause it's my time to shine,
So don't step outta line or else it's
KILL DASH NINE!
My posse throws down like leaky bucket regulators;
I was coding shit in MIPS while you were playing Space Invaders.
With my finger on the trigger I run ./configure
Yo, this package is big, but MY package is bigger.
I roll my weed with Zig Zag while I zag-zig splay,
And I do a bounds check before I write to an array.
I'm a loc'd out baller writing KLOCS a day,
'Cause it's publish or perish, fool, what can I say?
I'm 26 now, will I live to see 28?
Some days I wonder if I'll survive to graduate.
But hey, that's just fine, I won't ever resign,
And if fools try to step then it's KILL DASH NINE!
Yeah it's KILL DASH NINE,
From my command line
It's KILL DASH NINE
Sending chills down your spine,I said KILL DASH NINE,
'Cause it's my time to shine,
So don't step outta line or else it'sKILL DASH NINE!
fs sa rlidwka
I'll chown your home and take your access away
Comin' straight outta Stanford, ain't nobody tougher,
Control-X, Control-C, I'll discard your fuckin' buffer.
You're outside your scope, son, close them curly brackets,
'Cause I drop punk-ass bitches like a modem drops packets.
Dump your motherfucking core, and trace your stack
'Cause where your ass is going, there won't be no callback.
See my style is divine and my code is sublime,
My career's in a climb and yours is in a decline.
I'll write a pound-define and assign you as mine,
So refine those sad rhymes or remove your plus signs,
Or it's KILL DASH NINE,
No more CPU time,
'Cause it's KILL DASH NINE,
And your process is mine,
I said KILL DASH NINE'Cause it's my time to shine,
Bitch you stepped outta line and now it's KILL DASH NINE!
viernes, 8 de diciembre de 2006
Geeksta rap
Esta es una letra de un género que descubrí gracias a Fidel (un profesor de la facu). Es un género similar al rap, pero trata sobre temas geekescos. Finalmente hay canciones de rap de las que puedo entender tanto la sintaxis como la semántica.
Yo, MC Plus Plus, my rhymes are so phat,
I'm PSPACE-complete but I'll reduce you to 3-SAT.
My crew is so hard that we roll in NP,
And bitches dereference my pointer for free.
When I'm linear probing they're like, "Damn that's gigantic,"
I showed it to your mom and she used Hoare semantics.
She jumped like JNE up onto my erection
And I picked up that ho like straight garbage collection.
("That's right, mark-and-sweep on these nuts, bitch.")
My lyrics get stolen by sucker MCs,
I gotta sign my rhymes with PGP;
But I keep on generatin' like a CFG
'Cause there's so much drama in the PhD.
What's wrong MC Plus Plus, am I making you nervous?
Even skanky fat hoes give you denial of service.
You'll probably go to jail before you write your dissertation
So prepare your asshole for some internal fragmentation;
Penetration, as they fill it up with jism,
It's too bad you aren't closed under homomorphism.
Your problem, Plus Plus, is that your typing isn't strict:
In ML my type is real and your type is 'a dict.
I control my flow better than TCP,
I rep the west coast like Eazy-E,
You best not front if you can't pass the GRE,
'Cause there's so much drama in the PhD.
My flow is so intense that I will overflow your buffer,
Corrupt your stack pointer makin' all your data suffer.
I've got saturated edges but your flow is sparser,
Real gangstas sip on Yacc; instead you generate a parser.
While you're busy poppin' stacks I'll pop a cap in your skull,
While you smoke your crack pipe I'm gonna pipe you to /dev/null.
I may not have a label but I rap like a star;
I'm an unsigned long int and you're an 8-bit char.
Your mom circulates like a public key,
Servicing more requests than HTTP.
She keeps all her ports open like Windows ME,
Oh, there's so much drama in the PhD.
DWORD to your moms, I came to drop bombs;
I've got more rhymes that San Jose's got dotcoms.
I rep the Farm like 50 reps Queens,
With more power than multitape Turing Machines.
Blowin' up the rap scene faster than factorial functions,
I'm dope like PNP transistors and I'll saturate your junctions.
By the time you've rhymed one line, I've already busted ten;
You rap in exponential time and I'm big-O of log(n).
I run gmake and gcc,
And I ain't never called malloc without calling free.
I'll beat your ass until it's colored like a red-black tree
'Cause there's so much drama in the PhD.
Yo, MC Plus Plus, my rhymes are so phat,
I'm PSPACE-complete but I'll reduce you to 3-SAT.
My crew is so hard that we roll in NP,
And bitches dereference my pointer for free.
When I'm linear probing they're like, "Damn that's gigantic,"
I showed it to your mom and she used Hoare semantics.
She jumped like JNE up onto my erection
And I picked up that ho like straight garbage collection.
("That's right, mark-and-sweep on these nuts, bitch.")
My lyrics get stolen by sucker MCs,
I gotta sign my rhymes with PGP;
But I keep on generatin' like a CFG
'Cause there's so much drama in the PhD.
What's wrong MC Plus Plus, am I making you nervous?
Even skanky fat hoes give you denial of service.
You'll probably go to jail before you write your dissertation
So prepare your asshole for some internal fragmentation;
It's too bad you aren't closed under homomorphism.
Your problem, Plus Plus, is that your typing isn't strict:
In ML my type is
I control my flow better than TCP,
I rep the west coast like Eazy-E,
You best not front if you can't pass the GRE,
'Cause there's so much drama in the PhD.
My flow is so intense that I will overflow your buffer,
Corrupt your stack pointer makin' all your data suffer.
I've got saturated edges but your flow is sparser,
Real gangstas sip on Yacc; instead you generate a parser.
While you're busy poppin' stacks I'll pop a cap in your skull,
While you smoke your crack pipe I'm gonna pipe you to /dev/null.
I may not have a label but I rap like a star;
I'm an unsigned long int and you're an 8-bit char.
Your mom circulates like a public key,
Servicing more requests than HTTP.
She keeps all her ports open like Windows ME,
Oh, there's so much drama in the PhD.
DWORD to your moms, I came to drop bombs;
I've got more rhymes that San Jose's got dotcoms.
I rep the Farm like 50 reps Queens,
With more power than multitape Turing Machines.
Blowin' up the rap scene faster than factorial functions,
I'm dope like PNP transistors and I'll saturate your junctions.
By the time you've rhymed one line, I've already busted ten;
You rap in exponential time and I'm big-O of log(n).
I run gmake and gcc,
And I ain't never called malloc without calling free.
I'll beat your ass until it's colored like a red-black tree
'Cause there's so much drama in the PhD.
viernes, 1 de diciembre de 2006
Los peligros de enseñar sólo Java
Encontré esta página, bastante interesante:
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
Suscribirse a:
Entradas (Atom)
