Una máquina Turing es una computadora (PC, Mac, iPhone o Conway’s Game of Life, elija la que esté más familiarizada) con almacenamiento ilimitado (memoria, disco duro, no importa). Suponga que puede programar la computadora en algún lenguaje de programación y que está interesado en lo que puede y no puede calcular. “Calcular” significa “leer alguna entrada, hacer cosas, escribir alguna salida”.
Esta no es la descripción habitual de una máquina de Turing, por supuesto, pero para el estudio de la computabilidad, que es principalmente para lo que son buenas las máquinas de Turing, es completamente equivalente.
El problema de Busy Beaver es el siguiente: supongamos que le desafío a escribir un programa de computadora (nuevamente, elija su lenguaje de programación favorito) cuyo único propósito en la vida sea imprimir una larga cadena de puntos y luego detenerse. Si la longitud de su programa está limitada a [math] k [/ math] caracteres, ¿qué longitud de cadena puede hacer?
- ¿Cómo se puede escribir un programa Java que imprima un conjunto completo de las primeras cuatro tablas de multiplicación (hasta 12) organizadas en columnas?
- Cómo explicar la organización de un microprocesador / microordenador
- ¿Por qué las letras P, Q, R, S y T se usan tan comúnmente en matemáticas?
- ¿Existe un vínculo entre el procesamiento de señales y la teoría de grafos?
- ¿Cuál es un ejemplo de un problema cuya respuesta no es obvia, pero si los datos se visualizan de una manera nueva, se vuelven más fáciles de resolver?
Debe quedar claro que esta pregunta tiene una respuesta, para cualquier elección de lenguaje de programación y cualquier límite dado [math] k [/ math]. Después de todo, solo hay finitamente muchos posibles programas de computadora de longitud, digamos, 10,000 caracteres en, digamos, C ++; algunos de ellos imprimen cadenas finitas de puntos, y de todos los que lo hacen, podemos elegir el (o los) que imprimen la cadena absolutamente más larga.
Si sabe algo sobre programación, también debe quedar claro que tan pronto como [math] k [/ math] se vuelva razonablemente grande para acomodar algunos programas no triviales, la respuesta será increíblemente enorme. Es bastante fácil, por ejemplo, escribir un programa de computadora que imprima [math] 100 ^ {100} [/ math] puntos y luego se detenga, y en los lenguajes de programación más razonables esto no debería ocupar más de unos pocos cientos de caracteres para implementar. Con un poco de inteligencia puedes obtener números mucho más altos.
La función Busy Beaver es una tabla que enumera, para cualquier [matemática] k [/ matemática] dada, la respuesta a este problema: la longitud de la cadena de puntos más larga que puede lograr con un programa de longitud [matemática] k [/ matemática] que imprime dicha cadena y se detiene. Esta función, o tabla, es bastante salvaje: se puede demostrar que crece más rápido que cualquier función computable. Por lo tanto, en sí mismo no es computable. Es incognoscible en un sentido bastante fuerte.
Si no sabe qué significa “lenguaje de programación” o qué pueden hacer los lenguajes de programación, puede imaginarse que le está dando a un amigo un cuaderno con instrucciones muy precisas de modo que, si su amigo sigue esas instrucciones, terminará escribir una gran cantidad de puntos en una hoja de papel muy grande. No es necesario suponer que la amiga es un genio de las matemáticas, pero puede suponer que es inmortal, muy paciente y capaz de seguir instrucciones simples como “escriba el número 6 en la nota adhesiva amarilla” o “lea el número en la nota adhesiva naranja, bórrelo y reemplácelo con el siguiente número de conteo “. Está bien si ella misma no puede contar más de mil millones: con suficientes notas adhesivas podemos ayudarla a superar eso.
