About: Busy beaver function

Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Busy beaver function Sponge Permalink

An Entity of Type : dbkwik:resource/4aznwUI91u-_lcyx_rD8kQ==, within Data Space : 134.155.108.49:8890 associated with source dataset(s)

The busy beaver function (a.k.a. BB function or Radó's sigma function, denoted \(\Sigma(n)\) or \( ext{BB}(n)\)), is a distinctive fast-growing function from computability theory. It is notable as being the most well-known of the uncomputable functions. It is defined as the maximum number of ones that can be written (in the finished tape) with an n-state, 2-color halting Turing machine starting from a blank tape before halting.

Attributes	Values
rdf:type	function
rdfs:label	Busy beaver function
rdfs:comment	The busy beaver function (a.k.a. BB function or Radó's sigma function, denoted \(\Sigma(n)\) or \( ext{BB}(n)\)), is a distinctive fast-growing function from computability theory. It is notable as being the most well-known of the uncomputable functions. It is defined as the maximum number of ones that can be written (in the finished tape) with an n-state, 2-color halting Turing machine starting from a blank tape before halting.
dcterms:subject	Functions Uncomputable Computers Zany Zoo
dbkwik:googology/p...iPageUsesTemplate	dbkwik:resource/6jJxc72T8ljy4GoTDBvHyA== dbkwik:resource/m4IUS3MgqLvoInU8ngS86g== dbkwik:resource/yT3JrwLDjx1EXiHBG5CO8g== dbkwik:resource/YAzP--k8u6mtp_rQtQuITQ==
Author	Tibor Radó
Names	BB, Radó's sigma function
Year	1961(xsd:integer)
notation	\, \
growthrate	>* all computable functions
abstract	The busy beaver function (a.k.a. BB function or Radó's sigma function, denoted \(\Sigma(n)\) or \( ext{BB}(n)\)), is a distinctive fast-growing function from computability theory. It is notable as being the most well-known of the uncomputable functions. It is defined as the maximum number of ones that can be written (in the finished tape) with an n-state, 2-color halting Turing machine starting from a blank tape before halting. Radó showed that this function eventually dominates all computable functions, and thus it is uncomputable. That is, no algorithm that terminates after a finite number of steps can compute \(\Sigma(n)\) for arbitrary \(n\). However, it is computable by an oracle Turing machine with an oracle for the halting problem. Turing machines that produce these numbers are called busy beavers. It is one of the fastest-growing functions ever arising out of professional mathematics. In googology, only a handful of significant functions surpass it — the xi function, the Rayo function, and the FOOT function.

OpenLink Virtuoso version 07.20.3217, on Linux (x86_64-pc-linux-gnu), Standard Edition
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2012 OpenLink Software