On Non-Computable Functions

The purpose of this note is to present some very simple instances of non-computable functions. Beyond their simplicity, these examples throw light upon the following basic point. If a function/(.r) is to serve as an example of a non-computable function, then f(x) must be welldefined in some generally accepted sense; hence the efforts to construct examples of non-computable functions reveal the general conviction that over and beyond the class of computable (general recursive) functions there is a much wider class, the class of well-defined functions. The scope of this latter class is vague; in some quarters, there exists a belief that this class will be defined some day in precise terms acceptable to all. The examples of non-computable functions to be discussed below will be well defined in an extremely primitive sense; we shall use only the principle that a non-empty finite set of non-negative integers has a largest element. Furthermore, we shall use this principle only for exceptionally well-defined sets; and thus our construction will rest upon considerations which occur constantly in every area of mathematics. It may be of interest to note that we shall not use an enumeration of computable functions to show that our examples are non-computable functions. Thus, in this sense, we do not use the diagonal process.