Category Archives: Fast-growing functions

Fast-growing functions revisited

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 | 7 Comments

Graph minors

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

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

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

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

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