Metraipolis › archive › dc_3433369cf4db
Busy beaver — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Busy_beaver
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-01T13:11:41.885Z
- SHA-256 of the archived text
4e960a001b6c830e9f922016bc303331046d380c22b28ac174657ae65b7a5806- Stable URL of this page
https://metraipolis.com/documento/dc_3433369cf4db
How to cite
Busy beaver — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Busy_beaver (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_3433369cf4db (Metraipolis archive dc_3433369cf4db, sha256 4e960a001b6c830e9f922016bc303331046d380c22b28ac174657ae65b7a5806)
BibTeX
@misc{dc3433369cf4db,
title = {Busy beaver — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Busy_beaver},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_3433369cf4db; sha256 4e960a001b6c830e9f922016bc303331046d380c22b28ac174657ae65b7a5806},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Busy_beaver. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En ciencia computacional teórica, el juego del castor ocupado (nombre original en inglés: busy beaver) busca obtener un programa de un tamaño dado, que (según la definición) produzca la mayor cantidad de salida posible o se ejecute durante el mayor número de pasos antes de detenerse. Dado que es fácil concebir un programa en bucle infinito que produzca una salida infinita o se ejecute durante un tiempo infinito, dichos programas se excluyen del juego. En lugar de lenguajes de programación tradicionales, los programas utilizados en el juego son máquinas de Turing de n estados, uno de los primeros modelos de computación matemáticos. Las máquinas de Turing consisten en una cinta infinita y un conjunto finito de estados que sirven como el "código fuente" del programa. Producir la mayor cantidad de datos se define como escribir la mayor cantidad de unos en la cinta, también conocido como obtener la puntuación más alta, y ejecutar durante el mayor tiempo se define como tomar la mayor cantidad de pasos para detenerse. El juego del castor ocupado de n estados consiste en encontrar la máquina de Turing de n estados que ejecute n estados y finalmente se detenga. Se supone que dichas máquinas comienzan en una cinta en blanco, y se supone que la cinta contiene solo ceros y unos (una máquina de Turing binaria). El objetivo del juego es programar un conjunto de transiciones entre estados buscando la puntuación más alta o el tiempo de ejecución más largo, asegurándose de que la máquina se detenga finalmente. Decidir el tiempo de ejecución o la puntuación del n-simo castor ocupado no es computable. De hecho, tanto las funciones Σ(n) como S(n) finalmente se vuelven mayores que cualquier función computable. Esto tiene implicaciones en teoría de la computabilidad, en el problema de la parada y en la teoría de la complejidad computacional. El concepto de castor ocupado fue introducido por primera vez por Tibor Radó en su artículo de 1962, "Sobre funciones no computables". Una implicación del juego del castor ocupado es que, si fuera posible calcular las funciones Σ(n) y S(n) para todo n, entonces esto resolvería todas las conjeturas matemáticas que pueden ser reducidas a un problema de parada, por ejemplo, en una forma de "¿se detiene ⟨esta máquina de Turing⟩?". Por ejemplo, existe una máquina de Turing de 27 estados que verifica la conjetura de Goldbach para cada número y se detiene ante un contraejemplo; si esta máquina no se detuviera tras ejecutarse durante S(27) pasos, entonces debe ejecutarse indefinidamente, resolviendo así la conjetura. Muchos otros problemas, incluyendo la hipótesis de Riemann (744 estados) y la consistencia de la teoría de conjuntos de Zermelo-Fraenkel (745 estados), pueden expresarse de forma similar, donde como máximo se deben verificar infinitos casos numerables. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico). Fonte: Wikipedia in spagnolo, voce «Busy beaver» — https://es.wikipedia.org/wiki/Busy_beaver Wikidata Q1427965: «tipo di macchina di Turing» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1427965 Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Busy_beaver?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 174991979, consultata il 2026-11-01T13:03:50.468Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 006d3b57ec522bccf6c09744542a949777769fe8997f1f63160b9fd09f098937