Misplaced Pages

#211788

66-399: However, Graham's number can be explicitly given by computable recursive formulas using Knuth's up-arrow notation or equivalent, as was done by Ronald Graham , the number's namesake. As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers, the latter of which grow faster than any computable sequence. Though too large to ever be computed in full,

132-460: A computable ordinal number of iterates of the Turing jump of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language of second order arithmetic and to some models of Hypercomputation . Even more general recursion theories have been studied, such as E-recursion theory in which any set can be used as an argument to an E-recursive function. Although

198-477: A partial function f : N k → N {\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} } can be calculated if and only if there exists a computer program with the following properties: The basic characteristic of a computable function is that there must be a finite procedure (an algorithm ) telling how to compute the function. The models of computation listed above give different interpretations of what

264-508: A degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977, writing that Graham had recently established, in an unpublished proof, "a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof." The 1980 Guinness Book of World Records repeated Gardner's claim, adding to

330-435: A formal procedure for the function in some model of computation. Given a function (or, similarly, a set), one may be interested not only if it is computable, but also whether this can be proven in a particular proof system (usually first order Peano arithmetic ). A function that can be proven to be computable is called provably total . The set of provably total functions is recursively enumerable : one can enumerate all

396-466: A general method that works for any number of points uses vector methods and the property that a plane is determined by two linearly independent vectors . In an n -dimensional space where n ≥ 3 , a set of k points { p 0 ,   p 1 ,   … ,   p k − 1 } {\displaystyle \{p_{0},\ p_{1},\ \dots ,\ p_{k-1}\}} are coplanar if and only if

462-533: A geometric plane that contains them all. For example, three points are always coplanar, and if the points are distinct and non-collinear , the plane they determine is unique. However, a set of four or more distinct points will, in general, not lie in a single plane. Two lines in three-dimensional space are coplanar if there is a plane that includes them both. This occurs if the lines are parallel , or if they intersect each other. Two lines that are not coplanar are called skew lines . Distance geometry provides

528-794: A power tower ( ↑ {\displaystyle \uparrow } ) according to the definition 3 ↑ ↑ X = 3 ↑ ( 3 ↑ ( 3 ↑ … ( 3 ↑ 3 ) … ) ) = 3 3 ⋅ ⋅ ⋅ 3 {\displaystyle 3\uparrow \uparrow X=3\uparrow (3\uparrow (3\uparrow \dots (3\uparrow 3)\dots ))=3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} where there are X 3s. Thus, g 1 = 3 ↑ ↑ ( 3 ↑ ↑ ( 3 ↑ ↑   …   ( 3 ↑ ↑ 3 ) … ) ) where

594-415: A procedure is and how it is used, but these interpretations share many properties. The fact that these models give equivalent classes of computable functions stems from the fact that each model is capable of reading and mimicking a procedure for any of the other models, much as a compiler is able to read instructions in one computer language and emit instructions in another language. Enderton [1977] gives

660-431: A single natural number (just as above). They are the smallest class of partial functions that includes the constant, successor, and projection functions, and is closed under composition , primitive recursion , and the μ operator . Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a Turing machine or a register machine . Formally speaking,

726-406: A solution technique for the problem of determining whether a set of points is coplanar, knowing only the distances between them. In three-dimensional space, two linearly independent vectors with the same initial point determine a plane through that point. Their cross product is a normal vector to that plane, and any vector orthogonal to this cross product through the initial point will lie in

SECTION 10

#1732859363212

792-455: A string of bits (the alphabet Σ = {0, 1 }). The real numbers are uncountable so most real numbers are not computable. See computable number . The set of finitary functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions are Busy beaver , Kolmogorov complexity , or any function that outputs the digits of a noncomputable number, such as Chaitin's constant . Similarly, most subsets of

858-677: A superscript on an up-arrow indicates how many arrows there are. In other words, G is calculated in 64 steps: the first step is to calculate g 1 with four up-arrows between 3s; the second step is to calculate g 2 with g 1 up-arrows between 3s; the third step is to calculate g 3 with g 2 up-arrows between 3s; and so on, until finally calculating G = g 64 with g 63 up-arrows between 3s. Equivalently, G = f 64 ( 4 ) ,  where  f ( n ) = 3 ↑ n 3 , {\displaystyle G=f^{64}(4),{\text{ where }}f(n)=3\uparrow ^{n}3,} and

924-437: A value which is a single natural number. As counterparts to this informal description, there exist multiple formal, mathematical definitions. The class of computable functions can be defined in many equivalent models of computation , including Although these models use different representations for the functions, their inputs, and their outputs, translations exist between any two models, and so every model describes essentially

990-428: Is unary , max( f , g ), min( f , g ), arg max { y ≤ f ( x )} and many more combinations. The following examples illustrate that a function may be computable though it is not known which algorithm computes it. The Church–Turing thesis states that any function computable from a procedure possessing the three properties listed above is a computable function. Because these three properties are not formally stated,

1056-421: Is a computable function f such that f ( w ) is defined if and only if the word w is in the language. The term enumerable has the same etymology as in computably enumerable sets of natural numbers. The following functions are computable: If f and g are computable, then so are: f + g , f * g , f ∘ g {\displaystyle \color {Blue}f\circ g} if f

1122-400: Is a computable function f such that for each number n , f ( n ) is defined if and only if n is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The word enumerable is used because the following are equivalent for a nonempty subset B of the natural numbers: If a set B is the range of a function f then

1188-428: Is a computable function f such that for each word w over the alphabet, f ( w ) = 1 if the word is in the language and f ( w ) = 0 if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language. A language is computably enumerable (synonyms: recursively enumerable , semidecidable ) if there

1254-400: Is a language over the binary alphabet. A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called computable (synonyms: recursive , decidable ) if there

1320-427: Is common to consider formal languages . An alphabet is an arbitrary set. A word on an alphabet is a finite sequence of symbols from the alphabet; the same symbol may be used more than once. For example, binary strings are exactly the words on the alphabet {0, 1} . A language is a subset of the collection of all words on a fixed alphabet. For example, the collection of all binary strings that contain exactly 3 ones

1386-435: Is computable if and only if there is an effective procedure that, given any k - tuple x {\displaystyle \mathbf {x} } of natural numbers, will produce the value f ( x ) {\displaystyle f(\mathbf {x} )} . In agreement with this definition, the remainder of this article presumes that computable functions take finitely many natural numbers as arguments and produce

SECTION 20

#1732859363212

1452-506: Is much larger than N : it is f 64 ( 4 ) {\displaystyle f^{64}(4)} , where f ( n ) = 3 ↑ n 3 {\displaystyle f(n)=3\uparrow ^{n}3} . This weaker upper bound for the problem, attributed to an unpublished work of Graham, was eventually published and named by Martin Gardner in Scientific American in November 1977. The number gained

1518-448: Is of rank 2 or less. For example, given four points if the matrix is of rank 2 or less, the four points are coplanar. In the special case of a plane that contains the origin, the property can be simplified in the following way: A set of k points and the origin are coplanar if and only if the matrix of the coordinates of the k points is of rank 2 or less. A skew polygon is a polygon whose vertices are not coplanar. Such

1584-463: Is reached. To illustrate just how fast this sequence grows, while g 1 is equal to 3 ↑ ↑ ↑ ↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow 3} with only four up arrows, the number of up arrows in g 2 is this incomprehensibly large number g 1 . Computable function Computable functions are the basic objects of study in computability theory . Computable functions are

1650-452: Is so large that it is practically incomprehensible, even though the above display is relatively easy to comprehend. Even n , the mere number of towers in this formula for g 1 , is far greater than the number of Planck volumes (roughly 10 of them) into which one can imagine subdividing the observable universe . And after this first term, still another 63 terms remain in the rapidly growing g sequence before Graham's number G = g 64

1716-451: Is the primitive recursive functions . Another example is the Ackermann function , which is recursively defined but not primitive recursive. For definitions of this type to avoid circularity or infinite regress, it is necessary that recursive calls to the same function within a definition be to arguments that are smaller in some well-partial-order on the function's domain. For instance, for

1782-565: The Graham–Rothschild theorem on the Ramsey theory of parameter words , a special case of which shows that this problem has a solution N* . They bounded the value of N* by 6 ≤ N* ≤ N , with N being a large but explicitly defined number where F ( n ) = 2 ↑ n 3 {\displaystyle F(n)=2\uparrow ^{n}3} in Knuth's up-arrow notation ;

1848-431: The unit vector in the direction of a . That is, the vector projections of c on a and c on b add to give the original c . Since three or fewer points are always coplanar, the problem of determining when a set of points are coplanar is generally of interest only when there are at least four points involved. In the case that there are exactly four points, several ad hoc methods can be employed, but

1914-513: The Ackermann function A {\displaystyle A} , whenever the definition of A ( x , y ) {\displaystyle A(x,y)} refers to A ( p , q ) {\displaystyle A(p,q)} , then ( p , q ) < ( x , y ) {\displaystyle (p,q)<(x,y)} w.r.t. the lexicographic order on pairs of natural numbers . In this case, and in

1980-461: The Church–Turing thesis cannot be proved. The following facts are often taken as evidence for the thesis: The Church–Turing thesis is sometimes used in proofs to justify that a particular function is computable by giving a concrete description of a procedure for the computation. This is permitted because it is believed that all such uses of the thesis can be removed by the tedious process of writing

2046-409: The Church–Turing thesis states that the computable functions include all functions with algorithms, it is possible to consider broader classes of functions that relax the requirements that algorithms must possess. The field of Hypercomputation studies models of computation that go beyond normal Turing computation. Coplanar In geometry , a set of points in space are coplanar if there exists

Graham's number - Misplaced Pages Continue

2112-468: The Church–Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations. The notion of computability of a function can be relativized to an arbitrary set of natural numbers A . A function f is defined to be computable in A (equivalently A -computable or computable relative to A ) when it satisfies the definition of a computable function with modifications allowing access to A as an oracle . As with

2178-505: The Turing machine that computes it according to the n-th proof. Such a Turing machine is guaranteed to halt if the proof system is sound. Every computable function has a finite procedure giving explicit, unambiguous instructions on how to compute it. Furthermore, this procedure has to be encoded in the finite alphabet used by the computational model, so there are only countably many computable functions. For example, functions may be encoded using

2244-412: The Turing machines that produces them, then the above statement can be shown, if the proof system is sound, by a similar diagonalization argument to that used above, using the enumeration of provably total functions given earlier. One uses a Turing machine that enumerates the relevant proofs, and for every input n calls f n ( n ) (where f n is n -th function by this enumeration) by invoking

2310-411: The assumption of well-ordering. In a sound proof system, every provably total function is indeed total, but the converse is not true: in every first-order proof system that is strong enough and sound (including Peano arithmetic), one can prove (in another proof system) the existence of total functions that cannot be proven total in the proof system. If the total computable functions are enumerated via

2376-471: The case of the primitive recursive functions, well-ordering is obvious, but some "refers-to" relations are nontrivial to prove as being well-orderings. Any function defined recursively in a well-ordered way is computable: each value can be computed by expanding a tree of recursive calls to the function, and this expansion must terminate after a finite number of calls, because otherwise Kőnig's lemma would lead to an infinite descending sequence of calls, violating

2442-464: The concept of a computable function relative computability can be given equivalent definitions in many different models of computation. This is commonly accomplished by supplementing the model of computation with an additional primitive operation which asks whether a given integer is a member of A . We can also talk about f being computable in g by identifying g with its graph. Hyperarithmetical theory studies those sets that can be computed from

2508-797: The first term ( g 1 ) of the rapidly growing 64-term sequence. First, in terms of tetration ( ↑ ↑ {\displaystyle \uparrow \uparrow } ) alone: g 1 = 3 ↑ ↑ ↑ ↑ 3 = 3 ↑ ↑ ↑ ( 3 ↑ ↑ ↑ 3 ) = 3 ↑ ↑ ( 3 ↑ ↑ ( 3 ↑ ↑   …   ( 3 ↑ ↑ 3 ) … ) ) {\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))} where

2574-452: The following bounds on G : 3 → 3 → 64 → 2 < G < 3 → 3 → 65 → 2. {\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.} To convey the difficulty of appreciating the enormous size of Graham's number, it may be helpful to express—in terms of exponentiation alone—just

2640-436: The following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing [1936], Rogers [1967], and others. Enderton goes on to list several clarifications of these 3 requirements of the procedure for a computable function: To summarise, based on this view a function is computable if: The field of computational complexity studies functions with prescribed bounds on

2706-533: The formalized analogue of the intuitive notion of algorithms , in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines . Any definition, however, must make reference to some specific model of computation but all valid definitions yield

Graham's number - Misplaced Pages Continue

2772-703: The function f is the particular sequence f ( n ) = H n + 2 ( 3 , 3 ) {\displaystyle f(n)={\text{H}}_{n+2}(3,3)} , which is a version of the rapidly growing Ackermann function A ( n , n ). (In fact, f ( n ) > A ( n , n ) {\displaystyle f(n)>A(n,n)} for all n .) The function f can also be expressed in Conway chained arrow notation as f ( n ) = 3 → 3 → n {\displaystyle f(n)=3\rightarrow 3\rightarrow n} , and this notation also provides

2838-445: The function can be viewed as an enumeration of B , because the list f (0), f (1), ... will include every element of B . Because each finitary relation on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions of computable relation and computably enumerable relation can be defined from their analogues for sets. In computability theory in computer science , it

2904-479: The matrix of their relative differences, that is, the matrix whose columns (or rows) are the vectors p 0 p 1 → ,   p 0 p 2 → ,   … ,   p 0 p k − 1 → {\overrightarrow {p_{0}p_{1}}},\ {\overrightarrow {p_{0}p_{2}}},\ \dots ,\ {\overrightarrow {p_{0}p_{k-1}}}

2970-403: The natural numbers are not computable. The halting problem was the first such set to be constructed. The Entscheidungsproblem , proposed by David Hilbert , asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed in the 1930s that this set of natural numbers is not computable. According to

3036-493: The number is between 4 → 2 → 8 → 2 and 2 → 3 → 9 → 2 in Conway chained arrow notation . This was reduced in 2014 via upper bounds on the Hales–Jewett number to which contains three tetrations . In 2019 this was further improved to: The lower bound of 6 was later improved to 11 by Geoffrey Exoo in 2003, and to 13 by Jerome Barkley in 2008. Thus, the best known bounds for N* are 13 ≤ N* ≤ N'' . Graham's number, G ,

3102-529: The number of arrows in each layer is specified by the value of the next layer below it; that is, G = g 64 , {\displaystyle G=g_{64},} where g 1 = 3 ↑ ↑ ↑ ↑ 3 , {\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,} g n = 3 ↑ g n − 1 3 , {\displaystyle g_{n}=3\uparrow ^{g_{n-1}}3,} and where

3168-421: The number of 3s in each tower, starting from the leftmost tower, is specified by the value of the next tower to the right. In other words, g 1 is computed by first calculating the number of towers, n = 3 ↑ ( 3 ↑ ( 3   …   ↑ 3 ) ) {\displaystyle n=3\uparrow (3\uparrow (3\ \dots \ \uparrow 3))} (where

3234-405: The number of 3s in the expression on the right is 3 ↑ ↑ ↑ 3 = 3 ↑ ↑ ( 3 ↑ ↑ 3 ) . {\displaystyle 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3).} Now each tetration ( ↑ ↑ {\displaystyle \uparrow \uparrow } ) operation reduces to

3300-464: The number of 3s is 3 ↑ ( 3 ↑ 3 ) = 7625597484987 {\displaystyle 3\uparrow (3\uparrow 3)=7625597484987} ), and then computing the n tower in the following sequence: where the number of 3s in each successive tower is given by the tower just before it. The result of calculating the third tower is the value of n , the number of towers for g 1 . The magnitude of this first term, g 1 ,

3366-1397: The number of 3s is 3 ↑ ↑ ( 3 ↑ ↑ 3 ) {\displaystyle g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad {\text{where the number of 3s is}}\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)} becomes, solely in terms of repeated "exponentiation towers", g 1 = 3 3 ⋅ ⋅ ⋅ ⋅ 3 } 3 3 ⋅ ⋅ ⋅ 3 } … 3 3 3 } 3 ⏟ 3 3 ⋅ ⋅ ⋅ 3 } 3 3 3 } 3 {\displaystyle g_{1}=\underbrace {\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3} _{\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3}} and where

SECTION 50

#1732859363212

3432-1324: The number which Graham described to Gardner is larger than the number in the paper itself, both are valid upper bounds for the solution to the problem studied by Graham and Rothschild. Using Knuth's up-arrow notation , Graham's number G (as defined in Gardner's Scientific American article) is G = 3 ↑ ↑ ⋯ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ 3 3 ↑ ↑ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ 3 ⋮ ⏟ 3 ↑ ↑ ⋯ ⋯ ↑ ⏟ 3 3 ↑ ↑ ↑ ↑ 3 } 64 layers {\displaystyle \left.{\begin{matrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\&&\underbrace {\qquad \quad \vdots \qquad \quad } \\&&3\underbrace {\uparrow \uparrow \cdots \cdots \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 layers}}} where

3498-452: The plane. This leads to the following coplanarity test using a scalar triple product : Four distinct points, x 1 , x 2 , x 3 , x 4 , are coplanar if and only if, which is also equivalent to If three vectors a , b , c are coplanar, then if a ⋅ b = 0 (i.e., a and b are orthogonal) then where ⁠ a ^ {\displaystyle \mathbf {\hat {a}} } ⁠ denotes

3564-450: The popular interest in this number. According to physicist John Baez , Graham invented the quantity now known as Graham's number in conversation with Gardner. While Graham was trying to explain a result in Ramsey theory which he had derived with his collaborator Bruce Lee Rothschild , Graham found that the said quantity was easier to explain than the actual number appearing in the proof. Because

3630-478: The precise definition of computable function, mathematicians often used the informal term effectively calculable . This term has since come to be identified with the computable functions. The effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in

3696-430: The problem of determining the complexity of a computable function is known as a function problem . Computability of a function is an informal notion. One way to describe it is to say that a function is computable if its value can be obtained by an effective procedure . With more rigor, a function f : N k → N {\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }

3762-438: The provably total functions by enumerating all their corresponding proofs, that prove their computability. This can be done by enumerating all the proofs of the proof system and ignoring irrelevant ones. In a function defined by a recursive definition , each value is defined by a fixed first-order formula of other, previously defined values of the same function or other functions, which might be simply constants. A subset of these

3828-470: The same class of functions, giving rise to the opinion that formal computability is both natural and not too narrow. These functions are sometimes referred to as "recursive", to contrast with the informal term "computable", a distinction stemming from a 1934 discussion between Kleene and Gödel. For example, one can formalize computable functions as μ-recursive functions , which are partial functions that take finite tuples of natural numbers and return

3894-868: The same class of functions. Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursive functions . According to the Church–Turing thesis , computable functions are exactly the functions that can be calculated using a mechanical (that is, automatic) calculation device given unlimited amounts of time and storage space. More precisely, every model of computation that has ever been imagined can compute only computable functions, and all computable functions can be computed by any of several models of computation that are apparently very different, such as Turing machines , register machines , lambda calculus and general recursive functions . Before

3960-415: The sense that the running time of the algorithm increases exponentially (or even superexponentially ) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently. The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory,

4026-751: The sequence of digits of Graham's number can be computed explicitly via simple algorithms; the last 13 digits are ...7262464195387. Using Knuth's up-arrow notation , Graham's number is g 64 {\displaystyle g_{64}} , where g n = { 3 ↑ ↑ ↑ ↑ 3 , if  n = 1  and 3 ↑ g n − 1 3 , if  n ≥ 2. {\displaystyle g_{n}={\begin{cases}3\uparrow \uparrow \uparrow \uparrow 3,&{\text{if }}n=1{\text{ and}}\\3\uparrow ^{g_{n-1}}3,&{\text{if }}n\geq 2.\end{cases}}} Graham's number

SECTION 60

#1732859363212

4092-478: The superscript on f indicates an iteration of the function , e.g., f 4 ( n ) = f ( f ( f ( f ( n ) ) ) ) {\displaystyle f^{4}(n)=f(f(f(f(n))))} . Expressed in terms of the family of hyperoperations H 0 , H 1 , H 2 , ⋯ {\displaystyle {\text{H}}_{0},{\text{H}}_{1},{\text{H}}_{2},\cdots } ,

4158-453: The time and/or space allowed in a successful computation. A set A of natural numbers is called computable (synonyms: recursive , decidable ) if there is a computable, total function f such that for any natural number n , f ( n ) = 1 if n is in A and f ( n ) = 0 if n is not in A . A set of natural numbers is called computably enumerable (synonyms: recursively enumerable , semidecidable ) if there

4224-497: Was derived have since been proven to be valid. Graham's number is connected to the following problem in Ramsey theory : Connect each pair of geometric vertices of an n -dimensional hypercube to obtain a complete graph on 2 vertices . Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices? In 1971, Graham and Rothschild proved

4290-426: Was described in the 1980 Guinness Book of World Records , adding to its popular interest. Other specific integers (such as TREE(3) ) known to be far larger than Graham's number have since appeared in many serious mathematical proofs, for example in connection with Harvey Friedman 's various finite forms of Kruskal's theorem . Additionally, smaller upper bounds on the Ramsey theory problem from which Graham's number

4356-417: Was used by Graham in conversations with popular science writer Martin Gardner as a simplified explanation of the upper bounds of the problem he was working on. In 1977, Gardner described the number in Scientific American , introducing it to the general public. At the time of its introduction, it was the largest specific positive integer ever to have been used in a published mathematical proof. The number

#211788