In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine which, when started on an empty tape, runs as long as possible, but eventually halts. This machine attains the limits on the amount of time and space that a halting Turing machine of the same class can consume. The busy beaver function quantifies those limits and is an example of a non-computable function. In fact, it can be shown to grow faster than any computable function.

PropertyValue
dbpprop:abstract
  • In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine which, when started on an empty tape, runs as long as possible, but eventually halts. This machine attains the limits on the amount of time and space that a halting Turing machine of the same class can consume. The busy beaver function quantifies those limits and is an example of a non-computable function. In fact, it can be shown to grow faster than any computable function. The concept was first introduced by Tibor Radó as the "busy beaver game" in his 1962 paper, "On Non-Computable Functions".
  • Fleißige Biber (auch engl. Busy Beaver) sind Turingmaschinen, die möglichst viele Einsen auf das Band schreiben, ohne in eine Endlosschleife zu geraten (d. h. die nach einer endlichen Anzahl Rechenschritte halten). 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.
  • Le castor affairé, dont le nom a été proposé par le mathématicien hongrois Tibor Radó, est l'un des premiers exemples de fonction non calculable. Un castor affairé est une machine de Turing à n états qui écrit un maximum de "1" sur son ruban avant de s'arrêter. Déterminer le « castor affairé » pour un nombre n donné est un problème insoluble algorithmiquement; en pratique on ne peut même pas espérer le résoudre pour un nombre n au-delà de 10. Ce problème abstrait a été, dès son origine, illustré par un jeu.
  • ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。 ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数は如何なる計算可能関数よりも急速に増大する、ということを証明できる。ビジービーバー関数の概念は、ティボール・ラドーによる1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。
  • Een Busy Beaver is een Turingmachine met alfabet {#,1} die de Busy Beaver functie berekent. De Busy Beaver functie <math>S:N\rightarrow N</math> berekent het maximum aantal stappen dat een Busy Beaver van (n+1) toestanden kan doen op de lege invoerband, zonder in een oneindige lus te gaan. We mogen veronderstellen dat een Turing machine n toestanden <math>q_1, q_2, \ldots,q_n</math> heeft en één aanvaardbare halttoestand h. Enkele waarden van S(n): S(1)=1 S(2)=6 S(3)=21 S(4)=107 S(5) > 47176870 S(6) > 10
  • Pracowity bóbr (ang. busy beaver) to 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 inna znana funkcja obliczalna. Początkowe wartości są znane i łatwo je wyznaczyć (np. S=6), 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.
dbpprop:hasPhotoCollection
dbpprop:reference
dbpprop:title
  • Busy Beaver
dbpprop:urlname
  • BusyBeaver
dbpprop:wikiPageUsesTemplate
rdfs:comment
  • In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine which, when started on an empty tape, runs as long as possible, but eventually halts. This machine attains the limits on the amount of time and space that a halting Turing machine of the same class can consume. The busy beaver function quantifies those limits and is an example of a non-computable function. In fact, it can be shown to grow faster than any computable function.
  • Fleißige Biber (auch engl. Busy Beaver) sind Turingmaschinen, die möglichst viele Einsen auf das Band schreiben, ohne in eine Endlosschleife zu geraten (d. h. die nach einer endlichen Anzahl Rechenschritte halten). 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.
  • Le castor affairé, dont le nom a été proposé par le mathématicien hongrois Tibor Radó, est l'un des premiers exemples de fonction non calculable. Un castor affairé est une machine de Turing à n états qui écrit un maximum de "1" sur son ruban avant de s'arrêter. Déterminer le « castor affairé » pour un nombre n donné est un problème insoluble algorithmiquement; en pratique on ne peut même pas espérer le résoudre pour un nombre n au-delà de 10.
  • Een Busy Beaver is een Turingmachine met alfabet {#,1} die de Busy Beaver functie berekent. De Busy Beaver functie <math>S:N\rightarrow N</math> berekent het maximum aantal stappen dat een Busy Beaver van (n+1) toestanden kan doen op de lege invoerband, zonder in een oneindige lus te gaan. We mogen veronderstellen dat een Turing machine n toestanden <math>q_1, q_2, \ldots,q_n</math> heeft en één aanvaardbare halttoestand h.
  • Pracowity bóbr (ang. busy beaver) to 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 inna znana funkcja obliczalna.
rdfs:label
  • Busy beaver
  • Fleißiger Biber
  • Castor affairé
  • ビジービーバー
  • Busy Beaver
  • Pracowity bóbr
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of