edición general
33 meneos
188 clics
Se demuestra que la función castor afanoso BB(5) = 47.176.870

Se demuestra que la función castor afanoso BB(5) = 47.176.870

El castor afanoso (busy beaver) es la máquina de Turing con n estados que escribe el máximo número de palotes (unos) antes de parar a partir de una cinta vacía; la función castor afanoso BB(n) es dicho número máximo de palotes. Se sabe que BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107; se conjeturó en 1990 que BB(5) ≥ 47.176.870. El Busy Beaver Challenge anunció el 2 de julio que logró demostrar que BB(5)=47.176.870. Prueba que todas las máquinas de Turing con 5 estados que ejecutan más de 47.176.870 pasos nunca paran; ninguna es un castor afanoso.

| etiquetas: castor afanoso , máquina de turing , problema de la parada , indecidibilidad
27 6 0 K 18 ciencia
21 comentarios
27 6 0 K 18 ciencia
Comentarios destacados:    
WarDog77 #1 WarDog77 *
Puedo afirmar con rotundidad que he leído el artículo varias veces con atención y detenimiento y no he entendido nada de nada (y hacia muchos, muchos años que no me pasaba).
7 K 64
onainigo #3 onainigo
#1 Leído varias veces con atención en 5 min. No entiendo nada de nada y lo meneo ?(

Yo si que no lo entiendo
2 K 35
WarDog77 #5 WarDog77
#3 El artículo es bien corto, da para leerlo 3 veces.
Y si, lo meneo porque intuyo de que habla y se que es relevante (algo así como el descubrimiento de una fórmula nueva para encontrar más números primos)
0 K 10
onainigo #6 onainigo
#5 Pero no con atención. Y parece que algo si has entendido.
0 K 20
WarDog77 #10 WarDog77
#6 Desconozco tu velocidad lectora, con la mia puedo leer perfectamente un texto de poco más de 500 palabras 3 veces en 5 minutos (300p/min)

Y entendido nada, intuido algo.
0 K 10
onainigo #11 onainigo
#10 Venga majo. Que después de meter la gamba vas a acabar insultando. Adiós.
1 K 29
WarDog77 #19 WarDog77
#11 Tú eres el que falta al reporto poniendo en duda mis palabras cuando no tienes base para hacerlo.
0 K 10
#17 Tecar
#1 Una máquina de turing es un dispositivo teórico conceptual que ejecuta algorítmos.
Cualquier ordenador covencional de hoy día, independientemente de su capacidad, puede reducirse a una máquina de turing.
Si algo no se puede ejecutar en una máquina de turing, no puede ejecutarse en un ordenador convencional, da igual el dinero que se gastes.
Es por lo que estar teorías tienen su imporntancia, marcan el límite de los problemas que pueden resolverse computacionalmente.
1 K 17
#8 mcfgdbbn3 *
#1: Yo he intentado entenderlo, y lo único que he entendido es la razón por la que me prohibieron las matemáticas. xD

Ahora, que vayan a por la Conjetura de Collatz, fácil de entender, difícil de demostrar, no sigo más que vienen a por mí. :-P
0 K 12
WarDog77 #21 WarDog77
#13 Pues es un muy buen vídeo. Muy intuitivo. Evidentemente no para entender el concepto matemático pero si el físico, que ya es algo.
0 K 10
#2 tednsi
#1 Si, es que se explica como un libro cerrado.
0 K 9
#16 Ginto
#1 Como tú no lo he entendido y he descubierto una nueva palabra: "indecidibilidad".
Que intuyo qué puede ser.....
0 K 6
WarDog77 #20 WarDog77
#16 Que no se puede decidir (resolver o demostrar si es verdadero o falso)

Decidir:
3. tr. Resolver o hacer que se solucione completamente (algo dudoso). No han decidido cuándo será el examen. La última canasta decidió el encuentro
0 K 10
#4 Anonimatron
No sé ni qué es “afanoso” así que no sé de qué me sorprendo al no haber entendido absolutamente nada de este artículo.
1 K 9
#7 mcfgdbbn3
#0: Añade la etiqueta mates, así será más fácil encontrar la noticia.
0 K 12
Cherenkov #9 Cherenkov
Artículo muy interesante, recomiendo a todos su lectura.

Excepto a los que votan duplicada un hecho histórico que salió hace 34 años, esos mejor no lean nada xD
1 K 32
#12 Catalana
No hay voto incomprensible?
0 K 10
JohnSmith_ #14 JohnSmith_
En esta conferencia, Sanez de Cabezon habla sobre los castores afanosos. A partir del minuto 42 empieza la explicacion de la Maquina de Turing (cuya comprension es necesaria para entender lo de los castores). Os recomiendo la charla entera, interesantisima!.

www.youtube.com/watch?v=EtSN8GGBwsM
1 K 19
Doisneau #15 Doisneau
Computerphile hizo un video hace tiempo del tema (en ingles)

m.youtube.com/watch?v=CE8UhcyJS0I&pp=ygUXYnVzeSBiZWF2ZXIgbnVtYmVyc
0 K 10
#18 Tecar
En informática, un problema es "Decidible" cuando existe un algoritmo que lo resuelve en un tiempo finito.
Teóricamente es cuando existe una una máquina de Turing que puede decidirlo.
Indecicible es cuando no existe.
No se habla de coste ni de tiempos, es un marco teórico que ayuda a identificar los problemas que son computacionalmente abordables.
0 K 7
comentarios cerrados

menéame