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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

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

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Faculty of Education, 184 Hills Road, Cambridge, CB2 8PQ, DMB, Room GS4 WTCC, Hinxton, UK in person & via zoom

Other talks

Optimal metric and approximation of free boundary minimal surfaces Haematology and Palliative Care Using Light for Cancer Detection Tissue-scale communication in cancer development Online Causal Inference Seminar Afternoon Break
 

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