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 
Yo si que no lo entiendo
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)
Y entendido nada, intuido algo.
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.
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í.
Que intuyo qué puede ser.....
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
Excepto a los que votan duplicada un hecho histórico que salió hace 34 años, esos mejor no lean nada
www.youtube.com/watch?v=EtSN8GGBwsM
m.youtube.com/watch?v=CE8UhcyJS0I&pp=ygUXYnVzeSBiZWF2ZXIgbnVtYmVyc
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.