Inicio > Documentos > 2006_04_28_cripto

[Criptonomicón] Resolviendo el problema de la bicicleta de Turing

La cadena de Turing se caerá cuando su bicicleta alcance el estado (theta=0,C=0) y a la luz de lo que se ha escrito anteriormente, esto sucederá cuando i (que es simplemente un contador que indica cuantas veces ha girado la rueda trasera ) adopte un valor hipotético tal que i*n mod L = 0, o, dicho en román paladín, sucederá si hay algún múltiplo de n (como 2n, 3n, 395n, 109.948.368.443n) que resulta ser también un múltiplo exacto de L. Realmente puede haber varios de esos múltiplo llamados comunes, pero desde un punto de vista práctico el único que cuenta es el primero- el mínimo común múltiplo, o MCM- porque ese es el que se alcanzará primero y hará que la cadena se caiga.

Si, digamos, el piñón tiene 20 dientes (n=20) y la cadena tiene 100 eslabones (L=100) entonces después de una vuelta de rueda tendremos C=20, después de dos vuelta C=40, luego 60, luego 80 y luego 100, Pero como estamos trabajando con aritmética de módulo 100, este valor debe ser cambiado a cero. Así que después de 5 revoluciones de la rueda trasera, hemos alcanzado el estado (theta=0, C=0) y la cadena de Turing se cae. Cinco revoluciones de la cadena solo le hacen avanzar 10 metros por la carretera, así que con esto valores de n y de L la bicicleta es casi inservible. Por supuesto, eso es así sólo si Turing fuera lo suficientemente estúpido como para empezar a pedalear con la bicicleta en el estado es que la cadena se cae. Si, en el momento de empezar a pedalear, la bicicleta está en el estado (theta=0, C=1), entonces los valores sucesivos de C serán C= 21, 41, 61, 81,1,21... y así por siempre jamás - la cadena no se caerá nunca. Pero esto es un caso degenerado, donde "degenerado" para los matemáticos quiere decir "soporíficamente aburrido". En teoría, siempre que Turing ponga su bicicleta en el estado adecuado antes de aparcarla fuera de un edificio, nadie podrá robársela - la cadena se caería después de que hubiera avanzado no más de 10 metros.

Pero si la cadena de Turing tiene 101 eslabones (L=101) entonces después de 5 vueltas tenemos C=100 y depués de 6 tenemos C=19, y luego:

C= 39, 59, 79, 99,
18, 38, 58, 78, 98,
17, 37, 57, 77, 97,
16, 36, 56, 76, 96,
15, 35, 55, 75, 95,
14, 34, 54, 74, 94,
13, 33, 53, 73, 93,
12, 32, 52, 72, 92,
11, 31, 51, 71, 91,
10, 30, 50, 70, 90,
9, 29, 49, 69, 89,
8, 28, 48, 68, 88,
7, 27, 47, 67, 87,
6, 26, 46, 66, 86,
5, 25, 45, 65, 85,
4, 24, 44, 64, 84,
3, 23, 43, 63, 83,
2, 22, 42, 62, 82,
1, 21, 41, 61, 81,
CERO

Así pues hasta que la rueda no da 101 vueltas, la bicicleta no vuelve al estado (theta=0,C=0) en el que la cadena se cae. Durante esas 101 vueltas de rueda, la bicicleta de Turing ha avanzado un quinto de kilómetro por la carretera, lo que no es tan malo. Así que la bicicleta se puede usar. Sin embargo, al contrario que en el caso degenerado, _no_ es posible poner esta bicicleta en un estado inicial a partir del cual la cadena no se caiga nunca. Esto se puede demostrar observando que en la lista de valores anteriores de valores de C todos los valores posibles de C - es decir todos los números de 0 a 100- están en la lista. Lo que esto quiere decir es que no importa cual sea el valor de C cuando Turing empieza a pedalear: más pronto o más tarde acabará llegando al valor C=0 fatídico y la cadena se caerá. Así que Turing puede dejar la bicicleta en cualquier sitio confiando en que , si se la roban, nunca andarán más de un quinto de kilómetro antes de que la cadena se caiga.

La diferencia entre el caso degenerado y el no degenerado tiene que ver con las propiedades de los números involucrados. La combinación de (n=20, L=100) tiene unas propiedades radicalmente diferentes de la combinación (n=20, L=101). La diferencia fundamental es que 20 y 101 son "primos relativos" es decir que no tienen factores comunes. Esto quiere decir que su mínimo común múltiplo, MCM, es un número grande, es de hecho igual a L*n=20+101=2020. Mientras que el MCM de 20 y 100 es solo 100. La bicicleta con L=101 tiene un periodo largo - pasa por muchos estados diferentes antes de volver al estado inicial-mientras que la bicicleta con L=1000 tiene un periodo de solo unos pocos estados.

FIN del extracto del Criptonomicón.

Mis dudas filosófico-matemáticas surgen en este último párrafo. Para mi el que determina la longitud del periodo de la bicicleta no es el MCM si no el máximo común divisor, MCD. No he conseguido demostrarlo, pero en los casos en los que lo he probado, el número de estados posibles es igual a L / MCD.

Por ejemplo, en el caso degenerado: 100 / 20 = 5 estados posibles y en el caso no degenerado 101 / 1 = 101 estados posibles.

No entiendo que quiere decir cuando habla de 100 y de 2020 en esos dos mismos casos :(

Para dejar un comentario resolviendo mi duda o añadiendo dudas nuevas :) darle al botón "Atrás" del navegador o pinchar aquí


Lo que el viento se llevó
<Abril 2020
Lu Ma Mi Ju Vi Sa Do
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      


Aquí escriben:
  • Anónima
  • El Rodríguez -blog-
  • Nfer


  • Últimos comentarios
  • Anónimo en Tuiter, los puentes y una poesía.
  • Adilkhatri en Milagros, Naturaleza y Ciencia
  • tom en El lado oscuro de la amistad
  • sabung.net en sabor a meme
  • DewiFortunaQQ en Milagros, Naturaleza y Ciencia
  • manish en Milagros, Naturaleza y Ciencia
  • www.avg.com/retail en El lado oscuro de la amistad
  • www.avg.com/retail en El lado oscuro de la amistad
  • Norton login en ¡Estoy de mudanza!
  • Norton login en ¡Estoy de mudanza!

  • Blogalia

    Blogalia




    View My Stats

    Nos gusta dispersarnos en estos sitios ¡y en otros!
  • ::Fabio.com.ar:: (Fabio Baccaglioni)
  • Almada de noche (Almada)
  • Atalaya (JJ)
  • Babayaes (Xac)
  • Bloxito (Malambo)
  • chez Thëtée (Thelma Contino)
  • Cambalache - La vidriera irrespetuosa (Zifra)
  • Cuaderno de bitácora (rvr)
  • Desbarradas de Akin
  • Dulce de Leche
  • Ego,Dem (Dem)
  • El Forastero
  • El Macasar (senior citizen)
  • El Lobo Rayado
  • Evolucionarios (BioMaxi)
  • El PaleoFreak
  • Facdeiuser (GraneC)
  • FotoLuz (Glauka)
  • GATTACA (HighToro)
  • Gradicela (Peke)
  • Guerra a la penumbra (Nat)
  • Hellcenter (Fabián)
  • La cosa húmeda (Algernon)
  • La Divina Comedia (Vailima)
  • Lolaberinto(Lola)
  • Comida ecléctica(Mar)
  • Notas en el margen (Nat)
  • Pluma y Pixel (Sofocador)
  • Psicofonías (Psicobyte)
  • Reflexiones e irreflexiones (fernand0)
  • Sauria
  • Sin que sirva de precedente(Jaio)
  • Tejedora
  • Todo lo sólido �se desvanece en el aire (Ylek)
  • Una cuestión Personal (Vendell)
  • Ventanas (Descalza)
  • Un argentino en Eslovenia (Carlitos)
  • Velocidad de escape (Jomaweb)
  • Lecturas:
  • Lecturas anónimas

  • comentaristas dispersas (blog)