Profile

Cover photo
Sergio Burdisso
Worked at Coradir S.A.
Attended National University of San Luis (Argentina)
Lives in San Luis, Argentina
71 followers|87,471 views
AboutPostsPhotosYouTube

Stream

Sergio Burdisso

Shared publicly  - 
 
Little’s Law, Scalability and Fault Tolerance: The OS is your bottleneck (and what you can do about it)
Little's Law helps us determine the maximum request rate a server can handle. When we apply it, we find that the dominating factor limiting a server's capacity is not the hardware but the OS. Should we buy more hardware if software is the problem? If not, how can we remove that software ...
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
Hoy me puse a "delirar" un poco, llevando las teorías de Alan Turing a nuestra realidad actual y terminé escribiendo esto así que quería compartirlo con ustedes, mis amigos programadores, que por ahí se sienten identificados con esto o les causa curiosidad como a mí (disculpen si por ahí me pongo un poco técnico u.u traté de hacerlo lo más "para mortales" posible).

Creo que como todo programador uno tiende a pensar que uno puede resolver casi cualquier cosa con la computadora.... pero después de un delirio filosófico con respecto a lo que se puede resolver y lo que no con una computadora he llegado a unas conclusiones muy locas y ciertas al mismo tiempo:

Comencemos con el flujo de deducciones. Es cierto que se puede ver a cualquier programa que podamos escribir como una función que recibe un Número Natural y devuelve un Número Natural, esto es como una funcion F:N->N, este hecho se puede demostrar de muchas maneras, algunas más formales que otras, pero intuitivamente esta afirmación es evidente si se tiene en cuenta que cualquiera sea la/s entrada/s o la/s salida/s de un programa, a bajo nivel, no dejan de ser una secuencia de símbolos (0's y 1's) y por ende se le puede dar un orden lexicográfico a las mismas de la misma forma que se pueden ordenar las palabras en el diccionario. Matemáticamente hablando dada una secuencia de símbolos 0's y 1's se puede definir la siguiente función total que ponga en correspondencia las cadenas binarias con los enteros concatenandole un 1 a la cadena de símbolos binarios y luego interpretando a éste como su correspondiente contraparte decimal, ejemplo:

supongamos que a bajo nivel al llamar a un programa arbitrario P con, sin perdida de generalidad, 3 parámetros a1,a2 y a3 de tipo carácter (es decir algo como P(a1,a2,a3) ) internamente supongamos que la secuencia binaria que representa a los parámetros en memoria es "a1,a2,a3" = 011100110110010101110010. Apliquemos el proceso antes descrito para obtener el número que le corresponde lexicograficamente, tenemos:

1) concatenamos 1, 011100110110010101110010 se transforma en 1011100110110010101110010
2) tratamos a dicha secuencia como si fuera un número binario y obtenemos su contraparte decimal decimal(011100110110010101110010) = 7562610

entonces para el ejemplo dado, los 3 parámetros se pueden ver como un sólo parámetro de tipo natural con valor 7562610.

Si todavía hay alguien que no está convencido uno puede probar este hecho en la práctica al darse cuenta que cualquiera sea el programa P que escribamos, siempre se puede ver de manera lógica como una función que recibe de 0 a n entradas (no importa desde donde las reciba, si de disco, parámetros formales, variables globales, eventos del usuario, etc), ejecuta la lógica de su definición (un algoritmo) y finalmente devuelve de 0 a m salidas, en pseudo-código sería algo como:

P(ET0 ent1, ET1 ent1, ... , ETn entn, out ST0 sal0, out ST1 sal1, ... , out STm salm){
[código con la lógica de ElPrograma]
}

y por ende se puede reescribir en términos de otro programa F que reciba un natural y devuelva un natural como se muestra a continuación:

Antes de comenzar noten que a cada string se le corresponde un entero y viceversa ya que los strings, al ser una secuencia de símbolos/caracteres, se pueden ordenar lexicograficamente tal cual como "si estuvieran en el diccionario". En base a eso uno puede afirmar que cualquiera sea el programa P que podamos escribir, siempre podemos reescribirlo en términos de otro programa F que reciba un número natural y devuelva un número natural, por ejemplo como se bosqueja en el pseudo-código de la imágen adjunta al final.

A este punto tengo que haberlos convencido de que los programas son en realidad funciones que van de los naturales a los naturales, es decir, formalmente son funciones F's tales que F:N->N ¿verdad? teniendo en cuenta eso uno se da cuenta que los problemas que uno puede resolver como humano escribiendo programas son todos los problemas "en nuestra realidad" que se pueden corresponden con una función F:N->N, esto quiere decir que, de todos los problemas que existen en el universo estamos limitados a resolver sólo los que se puedan expresar como una función de los naturales a los naturales, es decir que "nuestro universo de problemas" como programadores está limitado al conjunto de funciones de los naturales a los naturales.

Ahora bien... la cosa es aún "más triste", uno puede preguntarse, dentro de este "universo de problemas de funciones de naturales a naturales, F:N->N" ¿podremos resolverlos a todos? intentemos responder esta pregunta, pero antes tengamos algo más en cuenta:

recuerden que los programas no son más que una secuencia de caracteres también (no importa el lenguaje, escribimos literalmente el programa como una secuencia de caracteres), entonces, dado un programa cualquiera podemos a éste asignarle un número, el número que le corresponde en orden lexicográfico ya sea usando el ascii de los caracteres o la técnica binara que vimos, por lo tanto podemos hablar del "i-ésimo programa java" o el "i-ésimo programa C", por ejemplo:

main(){
printf("hola");
}

que en binario-ascii sería:

0110110101100001011010010110111000101000001010010111101100001101 0000101001110000011100100110100101101110011101000110011000101000 0010001001101000011011110110110001100001001000100010100100111011 000011010000101001111101

usando la técnica de enumeración que vimos podemos decir que es el "44996533974017112843396296001261230365974526204199621591261055613-ésimo" programa C.

Esto quiere decir que la cardinalidad del conjunto de todos los programas es igual a la cardinalidad de los números naturales (ya que hemos encontrado una función total, uno a uno y suryectiva entre los naturales y el conjunto de los programas que se pueden escribir) en "criollo" sería, dado un programa podemos asignarle un número natural, que sería el índice que le corresponde en la lista de "todos los programas" si los listamos "alfabéticamente" (lexicográficamente sería el término correcto ya que los programas tienen caracteres que no figuran en nuestro alfabeto XD) y dado un número podemos decir qué programa es si usamos a ese número para buscarlo en dicha lista de los programas ordenados "alfabéticamente".

ahora sí estamos listos para responder nuestra última interrogante: dentro de este pequeño conjunto de problemas que podemos resolver como programadores, es decir, el "universo de problemas que se resuelven con funciones de naturales a naturales(F:N->N)" ¿podremos resolverlos a todos? veamos

Sabemos que como programadores estamos limitados a resolver problemas que se corresponden con funciones del tipo, F:N->N. Si podemos demostrar que podemos listar todos los problemas que se pueden resolver con la computadora habremos podido demostrar que como programadores podemos escribir al menos un programa que resuelva cada problema, cada "F:N->N" del conjunto de problemas, ya que sabemos que es posible listar a los programas que podemos escribir "alfabéticamente" y por ende siempre podríamos emparejar un programa de la "lista de programas" con un problema de la "lista de problemas" (ambos tendrían la misma cardinalidad que los números naturales, e.d. cardinalidad infinito numerable para ser más formal).

Veamos si es posible listar todos los problemas. SUPONGAMOS que podemos listar todos los problemas que se pueden resolver con la computadora, esto es, listar todas las funciones que van de los naturales a los naturales:

F1:N->N
F2:N->N
F3:N->N
....
....
(y así sucesivamente)

entonces podríamos definir una nueva función FDistinto(n)=Fn(n)+1, esto es, Fdistinto recibe un número n natural, busca en la lista "todos los problemas pueden resolver con la computadora" la n-ésima función Fn, calcula Fn(n) y al resultado le suma uno. Básicamente FDistinto(n) es igual "al resultado de la n-ésima función más 1". Ahora bien, esta función FDistinto claramente recibe un entero y devuelve un entero ¿verdad? entonces tiene que estar en la lista de "todas las funciones de F:N->N" ¿verdad? ya que supusimos que podemos listar exhaustivamente todas las funciones F:N->N ("problemas que podemos resolver con la computadora"). Sin perdida de generalidad supongamos que FDistinto está en la posición "k-ésima" de la lista, esto es FDistinto sería la función Fk de la lista, en símbolos FDistinto(n)=Fk(n), pero entonces Fk(k)=FDistinto(k)=Fk(k)+1 ¿qué? que Fk(k)=Fk(k)+1, es decir que que Fk(k) != Fk(k) cualquiera sea el k lo que es una contradicción, ya que estamos diciendo que Fk es distinta de sí misma.

Luego nuestra suposición de que podemos listar todos los problemas (funciones de naturales a naturales) es falsa, por ende, no es posible listar los problemas con lo que llegamos a la conclusión que el conjunto de problemas F:N->N que se podrían llegar a resolver con una computadora es infinitamente mayor al conjunto de programas que podemos escribir (formalmente, el tamaño del conjunto infinito de programas que se pueden escribir es Aleph0 mientras que el conjunto de problemas que "en principio" podrían resolverse con la computadora es de tamaño infinito Aleph1 -Googlear Aleph0-1 para los no entendidos).

Como conclusión tenemos que, del conjunto de todos los problemas que existen en nuestra realidad hay un subconjunto muy pequeño del mismo, el conjunto que está compuesto por los problemas que se pueden expresar como una función F:N->N, dentro de ese conjunto a su vez hay otro subconjunto infinitamente menor a éste que es el que realmente podemos resolver como programadores (como se muestra gráficamente en la imagen).

-
Una muestra de que esto es cierto, por ejemplo, el primer reto que subí a mi muro estaría dentro del conjunto de "Problemas que se pueden expresar como F:N->N" pero no dentro del conjunto "Problemas que se pueden resolver programando".
 ·  Translate
2
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
Any NP problem can be converted to SAT in polynomial time
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
Sparse binary matrices!  wow! que buena idea! usar AFD para comprimir matrices binarias para, por ejemplo, responder consultas sobre una cantidad masiva de datos con una complexidad temporal O(log(n))  
 ·  Translate
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
Finite State Automata as a Data Storage
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
Reto para los programadores: sea P el código de un programa y n una entrada válida para P, escribir un programa que reciba pares (P,n) y cuya salida sea:

"si"  - si P ejecutado con n imprime "Hola mundo" como su primera salida.
"Hola mundo" - en cualquier otro caso (incluido cuando se lo llama sin parametros)

¿no encuentran una solución? no se sientan mal, sigan leyendo XD

supongamos que ustedes logran escribir dicho hipotético programa, y sin perdida de generalidad que éste se llama "HolaMundoTester", entonces uno podría definir un nuevo programa C de la siguiente manera:

string C(string P){
    return HolaMundoTester(P, P); 
}

¿verdad?

ahora ¿qué pasaría si se llamara a C con el código de sí mismo? esto es

C(<C>);

supongamos que C(<C>) devuelve "sí" esto es HolaMundoTester(<C>, <C>) devuelve "sí" eso quiere decir que según HolaMundoTester, C ejecutado con sí mismo devuelve "Hola mundo" ¡pero supusimos que devolvía "sí"! lo que es una contradicción; si C(<C>) no devuelve "sí" entonces debe devolver "Hola mundo" con lo que estaríamos diciendo que HolaMundoTester(<C>, <C>) devuelve "Hola mundo" y esto es que C ejecutado con sí mismo devuelve algo distinto a "Hola mundo" lo que es una contradicción!

Paradoja! Luego dicho programa C no existe y por ende hemos contradecido nuestra asunción de que HolaMundoTester existe! por lo que hemos demostrado que no existe un programa que puede decir si un programa cualquiera P ejecutado con n imprime "hola mundo" como su primer salida.

... y sí, hay problemas que la computadora no puede resolver Jajaja
 ·  Translate
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
"Though Church's thesis is valid in the narrow sense that Turing Machines express the behavior of algorithms, the broader assertion that algorithms precisely capture what can be computed is invalid"
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
"There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false"
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
1
Add a comment...

Sergio Burdisso

Shared publicly  - 
 
About GPUMLib. GPUMLib is an open source Graphic Processing Unit Machine Learning Library. This library aims to provide machine learning researchers and practitioners with a high performance library by taking advantage of the GPU enormous computational power. The library is developed in C++ and ...
1
Add a comment...
Story
Tagline
"Debe entenderse que TODOS somos educadores. Cada acto de nuestra vida cotidiana tiene implicancias, a veces significativas. Procuremos entonces enseñar con el EJEMPLO." (Dr. René Favaloro)
Education
  • National University of San Luis (Argentina)
    Analista programador universitario, 2006 - 2011
  • Colegio Nº 20
    Técnico en Informática, 2003 - 2005
  • National University of San Luis (Argentina)
    Licenciatura en Ciencias de la Computación (Computer Science), 2015
Basic Information
Gender
Male
Work
Employment
  • Coradir S.A.
    Software developer & Graphic designer, 2011 - 2013
Places
Map of the places this user has livedMap of the places this user has livedMap of the places this user has lived
Currently
San Luis, Argentina
Links