| dbo:abstract
|
- In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. Since an endlessly looping program producing infinite output is easily conceived, such programs are excluded from the game. More precisely, the busy beaver game consists of designing a halting Turing machine with alphabet {0,1} which writes the most 1s on the tape, using only a given set of states. The rules for the 2-state game are as follows: 1.
* the machine must have two states in addition to the halting state, and 2.
* the tape initially contains 0s only. A player should conceive a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually. An nth busy beaver, BB-n or simply "busy beaver" is a Turing machine that wins the n-state Busy Beaver Game. That is, it attains the largest number of 1s among all other possible n-state competing Turing Machines. The , for instance, achieves four 1s in six steps. Determining whether an arbitrary Turing machine is a busy beaver is undecidable. This has implications in computability theory, the halting problem, and complexity theory. The concept was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions". (en)
- Fleißige Biber (auch englisch busy beaver) sind spezielle Turingmaschinen, die möglichst viele Einsen auf das Band schreiben und die nach einer endlichen Anzahl Rechenschritte den Halt-Zustand einnehmen (also anhalten). Die Radó-Funktion (auch Fleißiger-Biber-Funktion) gibt die maximale Anzahl der Einsen an, die ein fleißiger Biber mit einer gegebenen Anzahl von Zuständen schreiben kann. Beides wurde erstmals 1962 vom ungarischen Mathematiker Tibor Radó betrachtet. Die Fleißiger-Biber-Funktion ist in der theoretischen Informatik ein Standardbeispiel für eine endliche, aber im Allgemeinen nicht berechenbare Funktion. (de)
- Un castor affairé est, en théorie de la calculabilité, une machine de Turing qui maximise son « activité opérationnelle » (comme le nombre de pas effectués ou le nombre de symboles écrits avant son arrêt) parmi toutes les machines de Turing d'une certaine classe. Celles-ci doivent satisfaire certaines spécifications et doivent s'arrêter après être lancées sur un ruban vierge.Une fonction du castor affairé, ou fonction du nombre maximal de pas quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n'est pas calculable. En fait, à partir d'un certain point, cette fonction croît plus rapidement que n'importe quelle fonction calculable. Déterminer le castor affairé parmi un ensemble de machines de Turing à n états donnés est un problème insoluble algorithmiquement ; en pratique, on ne peut même pas espérer exhiber un castor affairé pour un nombre n au-delà de 10. Le concept, introduit en 1962 par le mathématicien hongrois Tibor Radó, est l'un des premiers exemples connus de fonction non calculable. (fr)
- Een busy beaver met toestanden is een terminerende turingmachine die een zo groot mogelijk aantal stappen doet. De busybeaverfunctie wijst aan een getal het aantal stappen toe dat de busy beaver met toestanden doet. De busybeaverfunctie is een totale functie die niet berekenbaar is. (nl)
- 이해하기 쉽게 설명하자면, 이론 컴퓨터 과학에서 바쁜 비버 게임(영어: busy beaver game)은 주어진 크기에서 가능한 최대치의 출력값을 구하는, 스스로 종결하는 프로그램을 구하는 것을 목표로 한다. 좀 더 정확하게는, 바쁜 비버 게임은 주어진 상태 모음만 사용하여 테이프에 제일 많은 1들을 기록하는 것을 목표로 하는, 정지하는 2진법 튜링 기계로 이루어진다. 이 게임의 규칙은 다음과 같다: 1.
* 기계는 정지 상태를 포함해 두 상태를 가져야 하고, 2.
* 테이프는 처음에는 0들만을 포함한다. 참여자는 기계가 결국 멈출 것을 전제로, 1들로 이루어진 제일 긴 출력을 목표로 하는 전이표를 가지고 있어야 한다. n번째 바쁜 비버(영어: nth busy beaver), BB-n, 단순히 바쁜 비버(영어: busy beaver)는 n 개의 상태를 지니는 바쁜 비버 게임을 수행하는 튜링 기계다. 즉, 이 기계는 존재할 수 있는 모든 n 개의 상태를 지니는 튜링 기계들 사이에서 제일 큰 개수의 1들을 출력한다. 예를 들자면 BB-2 튜링 머신은 네 개의 1들을 여섯 단계 동안 달성한다. 바쁜 비버 게임은 계산 가능성 이론, 정지 문제, 복잡도 이론과 연관되어 있다. 이 개념은 1962년에 출판한 (:en:Tibor Radó)의 논문, "On Non-Computable Functions"에서 최초로 소개되었다. (ko)
- Zajęty bóbr (ang. busy beaver) – maszyna Turinga o z góry zadanej liczbie stanów N, która zaczynając od pustej taśmy (same zera), generuje jak najdłuższy ciąg jedynek (lub też w innym sformułowaniu: wykonuje jak najwięcej kroków), po czym zatrzymuje się (maszyna, która nie zatrzymuje się jest dyskwalifikowana). Okazuje się, że zdefiniowana w ten sposób funkcja S(N) nie jest obliczalna, co więcej – rośnie ona szybciej niż każda funkcja obliczalna. Początkowe wartości są znane i łatwo je wyznaczyć (np. S(3)=21), ale już dla N>4 znane są tylko dolne oszacowania wartości funkcji. Busy Beaver jest powiązany z problemami tego typu co problem Collatza. W istocie maszyny, które podejrzewa się o bycie pracowitymi bobrami wykonują pewną funkcję mocno zbliżoną do funkcji Collatza. (pl)
- ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。 ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数はいかなる計算可能関数よりも急速に増大するということを証明できる。ビジービーバー関数の概念は、による1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。 (ja)
- Nella teoria della computabilità un alacre castoro (in inglese "busy beaver", letteralmente "castoro indaffarato", dall'espressione colloquiale per indicare una persona industriosa) è una macchina di Turing che ottiene la massima "attività delle operazioni" (come misurato dal numero di passi eseguiti, o dal numero dei simboli non vuoti che essa stampa sul nastro) tra tutte quelle in una determinata categoria. Un alacre castoro deve rispettare dei vincoli sulla sua struttura, fra cui il requisito che esso deve terminare in un numero finito di passi nel caso parta su un nastro vuoto. Si può dimostrare che una funzione dell'alacre castoro, che quantifica il limite superiore dell'attività di una macchina di Turing di una data classe, è una funzione non computabile, in quanto cresce asintoticamente più di quanto faccia una qualunque funzione computabile. Il concetto fu introdotto per la prima volta da in un articolo del 1962, On Non-Computable Functions (Sulle funzioni non computabili). (it)
- Em Teoria da Computação, o algoritmo do castor (busy beaver) é uma máquina de Turing que, após iniciada em uma fita vazia (todas as posições em branco ou com 0), executa o maior número de passos possível, mas eventualmente para. Esta máquina atinge o limite na quantidade de tempo e espaço que uma máquina de Turing com parada da mesma classe pode consumir. A função busy beaver quantifica estes limites e é um exemplo de uma função não computável. Na verdade, pode ser mostrado que ela cresce mais rapidamente do que qualquer função computável. O conceito foi introduzido pela primeira vez por Tibor Radó como o jogo do castor "ocupado" em seu artigo de 1962, "On Non-Computable Functions". (pt)
- 在计算机科学中，忙碌的海狸（Busy Beaver）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1. 包含两个状态的忙碌的海狸游戏有下面两条规则： 1.
* 该图灵机包括除终止态以外的两个状态 2.
* 纸带初始值都是0 玩家需要设计出可能输出最多1的状态转换表格，同时也要确保图灵机是会终止的。 能赢得n个状态的忙碌的海狸游戏的图灵机，称为第n个忙碌的海狸，或者用BB-n表示(BB是英文忙碌的海狸的缩写)。BB-n，是在所有n个状态的图灵机里面，可以输出最多的1的。比如BB-2，可能通过6次状态转换输出4个1。 忙碌的海狸游戏是由匈牙利的数学家在1962年发表的论文《On Non-Computable Functions》中提出的。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 47732 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:align
| |
| dbp:caption
|
- 1.0
- Evolution of 2-state busy beaver until halt. (en)
- Evolution of 3-state busy beaver until halt. (en)
- Rules for 1-state busy beaver. (en)
- Rules for 2-state busy beaver. (en)
- Rules for 3-state busy beaver. (en)
- Rules for 4-state busy beaver. (en)
|
| dbp:captionAlign
| |
| dbp:direction
| |
| dbp:header
|
- Evolution of Busy Beavers with 1-4 States (en)
|
| dbp:headerAlign
| |
| dbp:image
|
- Busybeaver1.svg (en)
- Busybeaver1rules.png (en)
- Busybeaver2.svg (en)
- Busybeaver2rules.png (en)
- Busybeaver3.svg (en)
- Busybeaver3rules.png (en)
- Busybeaver4.png (en)
- Busybeaver4rules.png (en)
|
| dbp:imageGap
| |
| dbp:perrow
| |
| dbp:project
| |
| dbp:text
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:width
|
- 75 (xsd:integer)
- 200 (xsd:integer)
- 225 (xsd:integer)
- 300 (xsd:integer)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Een busy beaver met toestanden is een terminerende turingmachine die een zo groot mogelijk aantal stappen doet. De busybeaverfunctie wijst aan een getal het aantal stappen toe dat de busy beaver met toestanden doet. De busybeaverfunctie is een totale functie die niet berekenbaar is. (nl)
- ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。 ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数はいかなる計算可能関数よりも急速に増大するということを証明できる。ビジービーバー関数の概念は、による1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。 (ja)
- 在计算机科学中，忙碌的海狸（Busy Beaver）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1. 包含两个状态的忙碌的海狸游戏有下面两条规则： 1.
* 该图灵机包括除终止态以外的两个状态 2.
* 纸带初始值都是0 玩家需要设计出可能输出最多1的状态转换表格，同时也要确保图灵机是会终止的。 能赢得n个状态的忙碌的海狸游戏的图灵机，称为第n个忙碌的海狸，或者用BB-n表示(BB是英文忙碌的海狸的缩写)。BB-n，是在所有n个状态的图灵机里面，可以输出最多的1的。比如BB-2，可能通过6次状态转换输出4个1。 忙碌的海狸游戏是由匈牙利的数学家在1962年发表的论文《On Non-Computable Functions》中提出的。 (zh)
- Fleißige Biber (auch englisch busy beaver) sind spezielle Turingmaschinen, die möglichst viele Einsen auf das Band schreiben und die nach einer endlichen Anzahl Rechenschritte den Halt-Zustand einnehmen (also anhalten). Die Radó-Funktion (auch Fleißiger-Biber-Funktion) gibt die maximale Anzahl der Einsen an, die ein fleißiger Biber mit einer gegebenen Anzahl von Zuständen schreiben kann. Beides wurde erstmals 1962 vom ungarischen Mathematiker Tibor Radó betrachtet. (de)
- In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. Since an endlessly looping program producing infinite output is easily conceived, such programs are excluded from the game. More precisely, the busy beaver game consists of designing a halting Turing machine with alphabet {0,1} which writes the most 1s on the tape, using only a given set of states. The rules for the 2-state game are as follows: (en)
- Un castor affairé est, en théorie de la calculabilité, une machine de Turing qui maximise son « activité opérationnelle » (comme le nombre de pas effectués ou le nombre de symboles écrits avant son arrêt) parmi toutes les machines de Turing d'une certaine classe. Celles-ci doivent satisfaire certaines spécifications et doivent s'arrêter après être lancées sur un ruban vierge.Une fonction du castor affairé, ou fonction du nombre maximal de pas quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n'est pas calculable. En fait, à partir d'un certain point, cette fonction croît plus rapidement que n'importe quelle fonction calculable. (fr)
- Nella teoria della computabilità un alacre castoro (in inglese "busy beaver", letteralmente "castoro indaffarato", dall'espressione colloquiale per indicare una persona industriosa) è una macchina di Turing che ottiene la massima "attività delle operazioni" (come misurato dal numero di passi eseguiti, o dal numero dei simboli non vuoti che essa stampa sul nastro) tra tutte quelle in una determinata categoria. Un alacre castoro deve rispettare dei vincoli sulla sua struttura, fra cui il requisito che esso deve terminare in un numero finito di passi nel caso parta su un nastro vuoto. (it)
- 이해하기 쉽게 설명하자면, 이론 컴퓨터 과학에서 바쁜 비버 게임(영어: busy beaver game)은 주어진 크기에서 가능한 최대치의 출력값을 구하는, 스스로 종결하는 프로그램을 구하는 것을 목표로 한다. 좀 더 정확하게는, 바쁜 비버 게임은 주어진 상태 모음만 사용하여 테이프에 제일 많은 1들을 기록하는 것을 목표로 하는, 정지하는 2진법 튜링 기계로 이루어진다. 이 게임의 규칙은 다음과 같다: 1.
* 기계는 정지 상태를 포함해 두 상태를 가져야 하고, 2.
* 테이프는 처음에는 0들만을 포함한다. 참여자는 기계가 결국 멈출 것을 전제로, 1들로 이루어진 제일 긴 출력을 목표로 하는 전이표를 가지고 있어야 한다. n번째 바쁜 비버(영어: nth busy beaver), BB-n, 단순히 바쁜 비버(영어: busy beaver)는 n 개의 상태를 지니는 바쁜 비버 게임을 수행하는 튜링 기계다. 즉, 이 기계는 존재할 수 있는 모든 n 개의 상태를 지니는 튜링 기계들 사이에서 제일 큰 개수의 1들을 출력한다. 예를 들자면 BB-2 튜링 머신은 네 개의 1들을 여섯 단계 동안 달성한다. (ko)
- Zajęty bóbr (ang. busy beaver) – maszyna Turinga o z góry zadanej liczbie stanów N, która zaczynając od pustej taśmy (same zera), generuje jak najdłuższy ciąg jedynek (lub też w innym sformułowaniu: wykonuje jak najwięcej kroków), po czym zatrzymuje się (maszyna, która nie zatrzymuje się jest dyskwalifikowana). Okazuje się, że zdefiniowana w ten sposób funkcja S(N) nie jest obliczalna, co więcej – rośnie ona szybciej niż każda funkcja obliczalna. Początkowe wartości są znane i łatwo je wyznaczyć (np. S(3)=21), ale już dla N>4 znane są tylko dolne oszacowania wartości funkcji. (pl)
- Em Teoria da Computação, o algoritmo do castor (busy beaver) é uma máquina de Turing que, após iniciada em uma fita vazia (todas as posições em branco ou com 0), executa o maior número de passos possível, mas eventualmente para. Esta máquina atinge o limite na quantidade de tempo e espaço que uma máquina de Turing com parada da mesma classe pode consumir. (pt)
|
| rdfs:label
|
- Fleißiger Biber (de)
- Busy beaver (en)
- Alacre castoro (it)
- Castor affairé (fr)
- 바쁜 비버 (ko)
- ビジービーバー (ja)
- Busy beaver (nl)
- Algoritmo do castor (pt)
- Pracowity bóbr (pl)
- 忙碌的海狸 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
