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

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

• Yi Cai, Newnham College
• Wednesday 05 February 2020, 19:00-19:30
• Wolfson Hall, Churchill College.

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:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.