1903-1995 AD Alonzo Church [WN]

Wikipedia link

Church-Turing Thesis

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.