Andy's Math/CS page

Thursday, December 15, 2005


Hi, my name is Andrew Drucker; I'm currently a senior undergraduate at
Swarthmore College. I've set up this page to make my thesis available
to graduate schools and to the public.

It's called 'Rich but Useless Information', and it represents independent research in Computability Theory. I hope you like it.. and if you're considering making a joke about the title, please consider that I might have heard it already.

Here it is:

Andy's Thesis

Thanks for your interest! I welcome questions and comments at adrucke1 (at) Below, for quick reference, is a copy of the Abstract:

Abstract. We show the existence of an incomputable function f such that for any Turing machine M, when each input x to M is supplemented with 'advice' f(x), M cannot solve any incomputable decision problem. In fact, we strengthen this result in three ways: 1) the advice function can be constructed to have no recursive upper bound, 2) it can be made so as to hold fixed the class of recursively enumerable sets, 3) for any fixed recursive bound B(x), the advice function can be made so as to hold fixed the class of functions computable by machines with output bound B(x). We also examine the barriers (some methodological, some provable) to combining these results in a single construction.



  • This comment has been removed by a blog administrator.

    By Blogger Andy D, at 4:23 PM  

Post a Comment

<< Home