Blog de la Biblioteca de Matemàtiques

Blog de la Biblioteca de Matemàtiques de la Universitat de Barcelona


Deixa un comentari

Alguns vincles entre els teoremes de Gödel i Turing

Josep Pla i Carrera

Josep Pla i Carrera

El passat 7 de febrer, Josep Pla i Carrera, professor emèrit del Departament de Probabilitat, Lògica i Estadística de la Universitat de Barcelona (UB), publicava un article al bloc col·lectiu El año de Turnig del diari El País, amb el títol Algunos vínculos entre los teoremas de Gödel y Turing.

Partint de l’obra de David Hilbert (1862-1943), el Doctor Pla estableix diversos vincles entre els treballs de Kurt Gödel (1906-1978) i els d’Alan Turing (1912-1954).

Hemos relacionado, pues, Turing con Hilbert.

Pero, ¿qué lo vincula con Gödel? La respuesta nos las dan las ‘funciones recursivas [parciales]’. Una máquina de Turing calcula las funciones recursivas y sólo éstas. Este es un vínculo muy estrecho entre algunos de los conceptos introducidos por Gödel y algunos de los conceptos introducidos por Turing que justifican, creo, que en 1963 Gödel añadiera un apéndice al artículo de su teorema de 1931 afirmando que las aportaciones de Turing permitían “una definición precisa e indudablemente adecuada de la noción general de sistema formal de los teoremas vi y xi”.

Pla i Carrera, Josep. Algunos vínculos entre los teoremas de Gödel y Turing.

Josep Pla ha publicat molt recentment El teorema de Gödel. Un análisis de la verdad matemática, un llibre editat per la Real Sociedad Matemática Española (RSME), que es divideix en tres parts. En la primera, Pla ofereix una aproximació a l’epistemologia de la matemàtica, centrant-se en el problema de la veritat en matemàtiques. En la segona part, de caràcter més tècnic, aborda la demostració dels teoremes d’incompletesa de Gödel. En la darrera part hi analitza les conseqüències dels teoremes del matemàtic austríac. El llibre permet dues lectures: la del lector que busqui un text divulgatiu sobre l’obra de Gödel i la de l’especialista que vulgui una aproximació rigorosa als seus teoremes.


Deixa un comentari

Ignacio Luengo: «La criptografia ens envolta per tot arreu»

Ignacio Luengo

Ignacio Luengo, fotografiat per Gert-Martin Greuel. Imatge provinent de la Oberwolfach Photo Collection, sota llicència CC-BY-SA 2.0

L’edició de El País del 16 de desembre passat, inclou una entrevista al catedràtic d’Àlgebra de la Universidad Compulense de Madrid (UCM), Ignacio Luengo, arran de la conferència que va pronunciar a la Fundación Ramón Areces, en el marc de les celebracions de l’Any Turing.

Luengo parla de criptografia en general, de la seva presència en tots els àmbits de la nostra vida diària, fent esment especial a la figura d’Alan Turing i l’abast de les fites que va aconseguir.

¿Existe el código imbatible? “Sí, uno en que la longitud de la clave es igual a la longitud del mensaje y si la clave se elige aleatoriamente, es indescifrable”, responde este especialista. “Pero es poco práctico”, añade, “porque si tienes que decirle al otro la clave te cuesta lo mismo decirle el mensaje entero; solo se usa cuando los dos interlocutores pueden ponerse de acuerdo de antemano con la clave, como el teléfono rojo entre los presidentes estadounidense y soviético en la guerra fría”.


Deixa un comentari

Un nou repte matemàtic de la RSME

Números bonics, números lletjos

Ara que s’acosta el sorteig de la Loteria de Nadal, El País i la Real Sociedad Matemática Española (RSME), recuperen els reptes matemàtics que van proposar durant tot l’any passat per celebrar el centenari de la institució. En aquesta ocasió es planteja un sol repte, de la mà d’Adolfo Quirós, vicepresident de la RSME i professor de la Universidad Autónoma de Madrid (UAM).

Entre els encertants se sortejarà una biblioteca matemàtica com la que va oferir el diari durant el 2011, a banda del llibre Desafíos matemáticos, que recull els 40 reptes proposats durant l’any del centenari. Per participar-hi, podeu enviar la resposta abans de les 00:00 de dissabte 22 de desembre a problemamatematicas@gmail.com.


Deixa un comentari

Solucionat el quarantè i últim repte matemàtic de El País

Ja hi ha solució per al quarantè i últim repte matemàtic amb els quals El País ha estat durant el 2011 commemorant el centenari de la Real Sociedad Matemática Epañola (RSME). El text xifrat que contenia el següent missatge:

47175413325413337313226277154179412371521522771

és Las matemáticas están a tu alrededor.

993 dels 994 lectors que han enviat una resposta han encertat el contingut del missatge. El lector restant, ha enviat una resposta diferent perquè volia transmetre també un missatge: Por sentido común el mensaje cifrado dice: ¡Feliz Navidad! Un saludo a todos y gracias por los problemillas.

Podeu consultar l’explicació íntegra per resoldre el problema a la pàgina del diari. I si ho voleu, també podeu repassar tots els reptes plantejats al llarg d’aquest any de commemoració.


Deixa un comentari

Quarantè i últim repte matemàtic de El País: Un missatge xifrat de comiat

Ahir es va presentar el quarantè i últim repte matemàtic amb els quals El País ha estat commemorant el centenari de la Real Sociedad Matemática Epañola (RSME). En aquesta ocasió el presenta Adolfo Quirós, professor de la Universidad Autónoma de Madrid i coordinador des de la RSME de la iniciativa del centenari.

Podeu enviar la vostra solució com a màxim fins les 00:00 hores de dimarts 20 de desembre a problemamatematicas@gmail.com i participareu, entre els encertants, en el sorteig d’una biblioteca matemàtica completa.

Enunciat:

Queremos transmitir un mensaje secreto. Para eso vamos a transformar un texto, que está escrito en el alfabeto castellano de 27 letras, de la A a la Z (incluyendo Ñ y W), en otro texto que se escribe usando solo 9 símbolos: los números del 1 al 9. Veamos como lo hacemos y lo ilustraremos con dos ejemplos.

Primero numeramos las letras por orden del 0 al 26, A=0, B=1, C=2, D=3,…, N=13, Ñ=14,…, W=23, X=24, Y=25, Z=26.

Por ejemplo:

HOLA-> 7,15,11,0

PEDRO->16,4,3,18,15

A continuación escribimos cada uno de esos números como un número de tres cifras en base 3. Recordemos lo que esto quiere decir: Los números los escribimos normalmente en base 10, usando unidades (1=10^0), decenas (10=10^1), centenas (100=10^2), etc. Así, 3418 representa el número 3×10^3+4×10^2+1×10+8. Para escribir en base 3 usamos potencias de 3, y sólo necesitamos las cifras 0, 1 y 2. Por ejemplo, la expresión 212 en base 3 representa la cantidad 2×3^3+1×3+2, que en base 10 se escribiría como 23.

Nuestras letras quedarán entonces representadas por A=000, B=001, C=002, D=010, …, N=111, Ñ= 112,…, W=212, X=220, Y=221, Z=222. Siguiendo con nuestros ejemplos:

HOLA-> 7,15,11,0 -> 021120102000

PEDRO->16,4,3,18,15 -> 121011010200120

Obsérvese que hemos escrito 3 cifras por cada número (no hemos quitado los ceros a la izquierda) y, también, que hemos escrito todos los números seguidos, sin las comas que los separaban antes. Ahora viene la parte secreta. Haciendo algo que no os vamos a decir, porque descubrirlo es precisamente el desafío, transformamos finalmente nuestros textos en otros escritos usando sólo los números del 1 al 9. En los ejemplos:

HOLA-> 7,15,11,0 -> 021120102000 -> 357471

PEDRO->16,4,3,18,15 -> 121011010200120 -> 64523161

El desafío consiste en leer el siguiente mensaje, que ha sido cifrado usando el procedimiento que hemos descrito, incluida la parte secreta:

47175413325413337313226277154179412371521522771

ALGUNAS OBSERVACIONES IMPORTANTES. En el texto original no se utilizan signos de puntuación, acentos, ni siquiera los espacios entre palabras, que serían otro símbolo. Una buena idea es ir probando los procedimientos que se os ocurran en los dos ejemplos. Estrictamente hablando, el procedimiento es ligeramente distinto si el texto original tiene un número par o impar de letras, pero la diferencia no influye en nada en cómo leer los mensajes, es una cuestión puramente técnica que resultará evidente a posteriori. Se considerará válida cualquier solución que haya sido capaz de descifrar el código y dé el mensaje correcto, pero, como siempre, nos gustaría saber cómo habéis llegado a ella.


Deixa un comentari

Solució al trenta-novè repte matemàtic de El País

Ja s’ha resolt el trenta-novè repte matemàtic que plantejava Miguel Ángel Morales Medina, llicenciat en Matemàtiques per la Universitat de Granada i editor del Boletín de la RSME, amb els quals El País celebra el centenari de la Real Sociedad Matemática Española (RSME).

S’han rebut 285 respostes dins del termini amb un encert del 95%. Si voleu consultar els detalls de la solució, s’expliquen extensament al web del diari.


Deixa un comentari

Trenta-novè repte matemàtic de El País: dos segments iguals i en angle recte

Miguel Ángel Morales Medina, llicenciat en Matemàtiques per la Universitat de Granada i editor del Boletín de la RSME, proposa i presenta el penúltim repte amb el qual El País celebra el centenari de la Real Sociedad Matemática Española (RSME). Podeu participar-hi si enviant la vostra solució abans de les 00:00 hores de dimarts 13 de desembre a l’adreça de correu problemamatematicas@gmail.com.

Enunciat

Partiendo de un triángulo cualquiera de vértices ABC, tomamos dos de sus lados, AB y AC por ejemplo, y dibujamos cuadrados apoyados en ellos. Llamamos I y J a los centros de los dos cuadrados y H al punto medio del lado del triángulo donde no hemos apoyado ningún cuadrado (el BC en este caso).

El desafío de esta semana consiste en demostrar que los segmentos HI y HJ tienen la misma longitud y que además forman un ángulo de 90º. La situación inicial puede verse en esta figura.


Deixa un comentari

Trenta-vuitè repte matemàtic de El País: Rock’n'Roll a la plaça del poble

Francisco Javier Masip Uson, llicenciat en Medicina i cap de la Secció de Control de Mercat de la Dirección General de Consum de la Diputació General d’Aragó, proposa i presenta el tercer dels reptes enviats pels lectors, el trenta-vuitè amb el qual El País celebra el centenari de la Real Sociedad Matemática Española (RSME). Podeu participar-hi si envieu la vostra solució abans de les 00:00 hores de dimarts 6 de desembre a l’adreça de correu problemamatematicas@gmail.com.

Enunciat

El Ayuntamiento de un pueblo quiere asfaltar una plaza circular que tiene en el centro una fuente, también circular, para celebrar allí conciertos de música a lo largo del año.

Al redactar el pliego de condiciones, el Consistorio necesita saber la superficie a asfaltar, que es la del anillo circular comprendido desde donde acaba la fuente y hasta el perímetro de la plaza, para así poder fijar el precio de licitación de la subasta. Al consultar con un aparejador para que haga el estudio, éste señala que cobra un importe por cada medición que haga entre cada dos puntos. Como el Ayuntamiento está recortando gastos, pretende que esa partida sea lo más económica posible.

Y el desafío de esta semana es: ¿Cuál sería el menor número de mediciones, consideradas entre cada dos puntos, que serían necesarias para calcular el área de ese anillo circular?, ¿a qué se correspondería o corresponderían esa o esas distancias? y ¿cómo se hallaría la superficie del anillo en base a ese o esos datos?


Deixa un comentari

Solució al trenta-setè repte matemàtic de El País

Ja hi ha solució al repte matemàtic que plantejava dijous passat, Francisco Antonio González, desenvolupador informàtic d’Indra. Sembla que aquest repte ha presentat més dificultats als lectors. S’han rebut 120 respostes dins del termini, un 75% de les quals correctes.

Podeu llegir el desenvolupament complet de la solució al web de El País.


Deixa un comentari

Trenta-setè repte matemàtic de El País: Un veïnat emprenedor

Francisco Antonio González, desenvolupador informàtic d’Indra, presenta el trenta-setè repte amb el qual El País celebra el centenari de la Real Sociedad Matemática Española (RSME). Podeu enviar la solució abans de les 00.00 hores de dimarts 29 de novembre a l’adreça problemamatematicas@gmail.com. entre els encertants se sortejarà una biblioteca matemàtica completa.

Enunciat

El pueblo de Bolci solo tiene solo una calle y su terreno se divide en 20 parcelas alineadas y numeradas como se muestra en la figura 1. En esas parcelas, viven 26 familias que hemos nombrado con letras desde la A a la Z. Diremos que dos familias del pueblo son vecinas cuando vivan en la misma parcela (como ocurre con E y G) o cuando vivan en parcelas adyacentes, (como ocurre con D y G).

Debido al estado de deterioro de las casas, los habitantes de Bolci han decidido derribar sus viviendas actuales y construir una manzana de pisos que ocupará unas pocas parcelas. El resto del terreno lo habilitarán para zonas verdes, comercios y otros servicios para lograr un pueblo más moderno, habitable y ecológico. No se conoce aún donde estarán los pisos, ni cuantas viviendas habrá en cada edificio. Tampoco se sabe cómo los ocuparán las familias. pero los habitantes del pueblo han acordado que en el nuevo proyecto se deben respetar las tres condiciones siguientes:

1.- Respetar las divisiones parcelarias: Cada vivienda nueva debe estar completamente ubicada dentro de alguna de las primitivas parcelas.

2.- Mantener la vecindad: Las familias que ahora son vecinas deben seguir siéndolo cuando se trasladen a su nueva vivienda. Se puede tener también nuevos vecinos, pero los viejos hay que mantenerlos.

3.- Cambiar obligatoriamente de parcela: Ninguna familia puede mantenerse en su parcela inicial, todas deben cambiar de número de parcela.

Solo si se cumplen esas tres condiciones podremos decir que un proyecto es válido como, por ejemplo, el que muestra lafigura 2. Fijémonos que en el ejemplo que damos se da una circunstancia curiosa: Las familias vecinas L y M siguen estando en las parcelas 9 y 10. Tan solo han intercambiado entre sí el número de parcela. Decimos entonces que en las parcelas 9 y 10 hay un sitio de cruce. En cada proyecto, llamaremos sitio de cruce a dos parcelas que tienen al menos dos familias vecinas que intercambian entre sí el número de parcela que tenían en la distribución original.

Y el desafío de la semana consiste en determinar la cantidad mínima y máxima de sitios de cruce que puede llegar a tener un proyecto válido. En la respuesta, debéis indicar el valor mínimo y el valor máximo, aportar al menos un proyecto de ejemplo de cada caso, y señalar las razones que garantizan que no hay posibilidad de construir proyectos válidos con una cantidad de sitios de cruce fuera de ese rango.

Follow

Get every new post delivered to your Inbox.

Join 73 other followers