1903-1995 AD Alonzo Church [WNTR]

Wikipedia link

Stanford Encyclopedia of Philosophy link on Church Turing Thesis

The above link states the thesis as I had concluded it must apply to real numbers. As I suspected, my idea was not new, but is not always understood by philosophers.

A Thought about Church’s Thesis

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 imitations 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). I have reviewed most of this January 17, 2018. Chapters 6-8 of Boolos & Jeffrey (3rd edition) give proofs that abacus computable functions are Turing computable, recursive functions are abacus computable and Turing computable functions are recursive.

Church’s Thesis can be stated equivalently as applying either to functions of natural numbers to natural numbers, or to 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 non-denumerable number of real numbers altogether. Remove any denumerable subset from a non-denumerable set and a non-denumerable set is left, so there must be a non-denumerable number of uncomputable real numbers. And hence a non-denumerable number of unrepresentable mathematical facts.

There is a sense, however, in which some non-computable functions (or real numbers) can be described. E.g. the one described in the Halting Problem. It makes sense to me, however, to think that the number of functions (or real numbers) that can be so described is also denumerable, and that, hence, the number of functions (or real numbers) that cannot be so described is non-denumerable. Also these non-computable but describable functions (or real numbers) are not described (I think) within the formalism – but rather outside it. So the facts X=X where X are such numbers have no corresponding statements in the formalism.