Function Computability and the Turing-Church Thesis

Tuesday, May 2, 2017 - 11:00am
312 MSB
Kevin Atherton (Advisor: Dr. Stephen Montgomery-Smith)

A function is effectively computable if there are definite, explicit rules by following which one could in principle compute its value for any given arguments. We will discuss methods that show certain classes of functions are computable and that these types of computability are equivalent, therefore Turing’s thesis (effectively computable functions are Turing computable) and Church’s thesis (effectively computable functions are recursive) are equivalent. This equivalence provides evidence that the theses are true.