12 votos

Jerarquía de rápido crecimiento y máquinas de Turing

¿Es posible obtener una estimación del tamaño de una máquina de Turing que calcula$f_\alpha(n)$, para un$\alpha$ dado (estoy especialmente interesado en$\alpha$ moderadamente grande como el ordinal de Fefferman-Schütte, o el ordinal de Veblen pequeño)? La idea es tener una idea del tamaño de la función BusyBeaver$BB(n)$ para valores moderados de$n$, ya que la literatura generalmente solo menciona los valores conocidos exactos (para$n\le 6$) y el hecho que dichos valores probablemente nunca se conocerán para$n=10$, digamos.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X