Relationship To Classical Logic
The schema form of CT shown above, when added to constructive systems such as HA, implies the negation of the law of the excluded middle. As an example, it is a classical tautology that every Turing machine either halts or does not halt on a given input. Assuming this tautology, in sufficiently strong systems such as HA it is possible to form a function h that takes a code for a Turing machine and returns 1 if the machine halts and 0 if it does not halt. Then, from Church's Thesis one would conclude that this function is itself computable, but this is known to be false, because the Halting problem is not computably solvable. Thus HA and CT disproves some consequence of the law of the excluded middle.
The "single axiom" form of CT mentioned above,
- ,
quantifies over functions and says that every function f is computable (with an index e). This axiom is consistent with some weak classical systems that do not have the strength to form functions such as the function f of the previous paragraph. For example, the weak classical system is consistent with this single axiom, because has a model in which every function is computable. However, the single-axiom form becomes inconsistent with the law of the excluded middle in any system that has sufficient axioms to construct functions such as the function h in the previous paragraph.
Read more about this topic: Church's Thesis (constructive Mathematics)
Famous quotes containing the words relationship to, relationship, classical and/or logic:
“... the Wall became a magnet for citizens of every generation, class, race, and relationship to the war perhaps because it is the only great public monument that allows the anesthetized holes in the heart to fill with a truly national grief.”
—Adrienne Rich (b. 1929)
“Poetry is above all a concentration of the power of language, which is the power of our ultimate relationship to everything in the universe.”
—Adrienne Rich (b. 1929)
“The basic difference between classical music and jazz is that in the former the music is always greater than its performance—Beethoven’s Violin Concerto, for instance, is always greater than its performance—whereas the way jazz is performed is always more important than what is being performed.”
—André Previn (b. 1929)
“The logic of worldly success rests on a fallacy: the strange error that our perfection depends on the thoughts and opinions and applause of other men! A weird life it is, indeed, to be living always in somebody else’s imagination, as if that were the only place in which one could at last become real!”
—Thomas Merton (1915–1968)