From Computability and Logic, Third Edition

by George S. Boolos and Richard C. Jeffrey

pages 19-20.

“No human being can write fast, or long enough, or small enough to list all members of an enumerably infinite set by writing out their names, one after another [e.g. digits of a real number], in some notation. But humans can do something equally useful, in the case of certain enumerably infinite sets: They can give explicit instructions for determining the nth member of the set, for

arbitrary finite n. Such instructions are to be given quite explicitly, in

a form in which they could be followed by a computing machine, or by

a human who is capable of carrying out only very elementary operations

on symbols. The problem will remain, that for all but a finite number of

values of n it will be physically impossible for any human or any machine

to actually carry out the computation, due to limitations on the time

available for computation, and on the speed with which single steps of

the computation can be carried out, and the amount of matter in the

universe which is available for forming symbols. But it will make for

clarity and simplicity if we ignore these limitations, thus working with a

notion of computability which goes beyond what actual men or machines

can be sure of doing. The essential requirement is that our notion of

computability not be too narrow, for shortly we shall use this notion to

prove that certain functions are not computable, and that certain enumerable

sets are not effectively (mechanically) enumerable – even if physical

limitations on time, speed, and amount of material could somehow be

overcome.

The notion of computation can be made precise in many different

ways, corresponding to different possible answers to such questions as

the following. ‘Is the computation to be carried out on a linear tape, or on

a rectangular grid, or what? If a linear tape is used, is the tape to have a

beginning but no end, or is it to be endless in both directions? Are the

squares into which the tape is divided to have addresses (like addresses

of houses on a street) or are we to keep track of where we are by writing

special symbols is suitable squares (as one might mark a trail in the woods

by marking trees). And so on. Depending on how such questions are

answered, computations will have one or another appearance, when examined

in detail. But our object is not to give a faithful representation of

the individual steps in the computation, and in fact, the very same set of

functions turns out to be computable, no matter how these questions are

answered. We shall now answer these and other questions in a certain way,

in order to get a characterization of the class of computable functions. A

moderate amount of experience with this notion of computability will

make it plausible that the net effect would have been the same, no matter

in what plausible way the questions have been answered. Indeed, given any

other plausible, precise characterization of computability that has been

offered, one can prove by careful, laborious reasoning that our notion

is equivalent to it in the sense that any function which is computable

according to one characterization is also computable according to the

other. But since there is no end to the possible variations in detailed

characterizations of the notions of computability and effectiveness, one

must finally accept or reject the thesis (which does not admit of mathematical

proof) that the set of functions computable in our sense is

identical with the set of functions that men or machines would be able to

compute by whatever effective method, if limitations on time, speed, and

material were overcome. Although this thesis (‘Church’s thesis) is unprovable,

it is refutable, if false. For if it is false, there will be some function which

is computable in the intuitive sense, but not in our sense.”

Note: I [the eclectic philosopher] studied and understood the proofs of the equal power of three three types of calculuses covered in the book (a few years ago).

There is a way to apply this to sequences digits in real numbers.

To apply to real numbers:

For any natural number in the range of the uncomputable function convert it to 2bbb2 where bbb is the binary (not necessarily 3 digits long) representation – the 2’s separate the represented numbers in the range.

Then 0.2bbba22bbb22bbb22bbb2…

can represent any function from 0, 1, 2, 3 … to a natural number in the range as digits of some real number from 0 to .999999…

The number of the domain obtained by counting the ’22’s from the left and the value of the function as the binary interpretation of the ‘bbb’s (there being always at least one ‘0’ or ‘1’. This way any function, including uncomputable ones can be represented as real numbers. Any uncomputable functions must correspond to uncomputable real numbers.

Any fact of the form X=X where X is a particular uncomputable real number cannot be represented in any known system of logic.

I believe it can also be inferred that since there are a denumerable number of computable real number for any method used and that they are the same in any method used, that altogether there are a denumerable number of computable real numbers. But there are a nondenumerable number of real numbers altogether. Remove any denumerable subset from a nondenumerable set and a nondenumerable set is left, so there must be a nondenumerable number of uncomputable real numbers.