Stone: Section 1

From CSWiki

Part 1: Introduction to Recursive Function Theory

Abstract

A computer can be seen as the mapping of a mathematical function's input to its output. However, these questions remain: Can every mathematical function be handled by a computer? If not, how to tell which are not computable?

For our theory, we will deal with functions that take and produce only natural numbers (numbers in $\mathcal{N}$ , without loss of generality. Although computers rely on approximations for real values, it is simple to represent each approximation as a natural number. We can also encode functions as natural numbers, and decode natural numbers into mathematical functions, which will come in handy later.