Formulas for Computable and Noncomputable Functions

Authors

Samuel Alexander, University of ArizonaFollow

Abstract

We explore the problem of writing explicit formulas for integer functions. We demonstrate that this can be done using elementary machinery for a wide class of functions. Constructive methods are given for obtaining formulas for computable functions and for functions in the arithmetical hierarchy. We include a short background on computability theory.

Author Bio

My name is Samuel Alexander and I am pursuing a doctorate in mathematics.My dream is to follow a career as a pioneering researcher in pure mathematics.I'm in the final laps of my senior year as an undergraduate at the University ofArizona and this Summer I'll be a graduate student (although I don't yet knowwhere). I was born in Flagstaff, Arizona, but have spent most of my life inSan Diego, California and Los Angeles, California. My interest in mathematicswas initially inspired by the pretty pictures in Euclid's Elements. I beganthinking about the ideas in this paper for some years, but have been officiallyworking on it from Spring of 2005 to Spring of 2006; I am much indebted to Dr.Ksenija Simic for overseeing the research and offering great advice.

Faculty Sponsor

Simic

Recommended Citation

Alexander, Samuel (2006) "Formulas for Computable and Noncomputable Functions," Rose-Hulman Undergraduate Mathematics Journal: Vol. 7: Iss. 2, Article 2.
Available at: https://scholar.rose-hulman.edu/rhumj/vol7/iss2/2