The busy beaver, the placid platypus and other alliterative amphibians

Associate Professor James Harland

School of Computer Science and IT

Date and time: 11.30am-12.30pm, Friday 13th May, 2005

Venue: 10.08.04

Abstract:

A common example of a non-computable function is the busy beaver, which is defined in terms of a particular class of Turing machines. For a given number of states, the busy beaver function is the largest number of 1s that can be printed by a machine that halts. This value is only known precisely for n <= 4, but the lower bounds known for n = 5 and n = 6 are already spectacularly large. In this talk we describe some variations on the busy beaver function, and a dual to it, which we call the placid platypus. We give a preliminary account of both theoretical and experimental results for this function.

About the speaker:

James Harland is an Associate Professor in the School of Computer Science and IT, RMIT University. His main research interest is centred around the applications of mathematical logic to computer science. In particular, this is concerned with automated reasoning techniques, which can be used as the basis for a class of programming languages known as logic programming languages. For further information, please click here.

Seminar Organisation

Seminars are free and open to the general public. No booking is necessary. If you are interested in giving a presentation in this seminar series, or to make suggestions for speakers, please contact Xiaodong Li, the seminar co-ordinator.