University of Cambridge > > Churchill CompSci Talks > The busy beaver game: a simple yet non-computable function

The busy beaver game: a simple yet non-computable function

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

Do you know any function that is even worse than the Ackermann function? The busy beaver game, first introduced by Tibor Radó in 1961, is a fun question related to computability theory, the halting problem as well as complexity theory. The goal of the game is to find the maximum number of 1s on your tape for your given Turing machine after it halts. Although the busy beaver game is quite easy to understand and implement, it can be shown to grow faster asymptotically than any computable function. In this talk, we will explore the simple instance of a non-computable function and give some simple proof on its non-computability.

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity