Category Archives: Fast-growing functions

Fast-growing functions revisited

Posted on July 24, 2020 by apgoucher

There have been many exciting results proved by members of the Googology wiki, a website concerned with fast-growing functions. Some of the highlights include: Wythagoras’s construction of an 18-state Turing machine which takes more than Graham’s number of steps to … Continue reading →

Posted in Fast-growing functions | 8 Comments

Graph minors

Posted on January 13, 2013 by apgoucher

This is now, at the time of writing, the longest article on cp4space. We’ll begin with a very well-known problem, which asks whether it’s possible for three houses on the plane to be connected to three utility suppliers without crossings. What appear … Continue reading →

Posted in Fast-growing functions, Uncategorized | 19 Comments

The Ξ function

Posted on January 6, 2013 by apgoucher

This is the final article on fast-growing functions. In the first two articles we looked at computable functions, up to and including Friedman’s TREE function. The third article described the Busy Beaver function, which eventually overtakes all computable functions. This … Continue reading →

Posted in Fast-growing functions | 50 Comments

Busy beavers

Posted on December 30, 2012 by apgoucher

This is the third out of a series of four articles on increasingly fast-growing functions. The first article described the Ackermann function (corresponding to ω) and the Goodstein function (corresponding to ε_0). The second article went into much more detail about a … Continue reading →

Posted in Fast-growing functions | Leave a comment

TREE(3) and impartial games

Posted on December 19, 2012 by apgoucher

This article was originally supposed to be about TREE(3) and the busy beaver function. However, I realised the potential of turning TREE(3) into a two-player finite game, which is surprisingly fun and means that I’ve ended up leaving uncomputable functions until a later post. … Continue reading →

Posted in Activities, Fast-growing functions | 33 Comments

Fast-growing functions

Posted on December 15, 2012 by apgoucher

This is the first of a projected two-part series of articles about fast-growing functions. The first part (‘fast-growing functions’) will introduce the concept of a fast-growing hierarchy of functions, use some notation for representing large numbers, make an IMO shortlist problem infinitely more … Continue reading →

Posted in Fast-growing functions | Leave a comment