Lógica Matemática (I-2008)

← Horas de consulta especiales sobre el ejercicio 6 de la tarea 5 →

funciones hacendosas

Marzo 7, 2008 · 2 comentarios

Hemos mencionado unas cuantas veces en clase las funciones Busy Beaver (”castor hacendoso” puede ser una traducción al español): funciones sumamente rápidas.
Una manera de verlas es la siguiente:
Sea BB(n) el mínimo valor de f^1_P(0), donde P es un programa de computador especificado en \leq n instrucciones (y f^1_P(0) es la función {\mathbb N}\to {\mathbb N} calculada por el programa P). Demuestre que
  1. BB(n+5)\geq 2n
  2. BB(5n+2)\geq 2^{n+1}
  3. BB(7n+2)\geq 2^{2^n}
  4. ¿Qué más puede concluir?

Categorías: matemática
Etiquetado: ,

2 respuestas so far ↓

  • luis a. garcía // Marzo 7, 2008 en 11:58 pm

    Encontré hace un tiempo un artículo divulgativo sobre las funciones de Busy Beaver y las de Ackermann,y otras cosas interesantes de computación y lógica (no es muy difícil de encontrar, es el tercer artículo que sale en google al buscar busy beaver numbers). Aquí el link para los interesados:

    http://www.scottaaronson.com/writings/bignumbers.html

  • luis a. garcía // Marzo 8, 2008 en 12:01 am

    No me di cuenta, de pronto el artículo resuelve una de las preguntas que Andrés propuso… no estoy seguro.

Deja un comentario