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, classical and/or logic:
“It was a real treat when he’d read me Daisy Miller out loud. But we’d reached the point in our relationship when, in a straight choice between him and Henry James, I’d have taken Henry James any day even if Henry James were dead and not much of a one for the girls when living, either.”
—Angela Carter (1940–1992)
“Compare the history of the novel to that of rock ‘n’ roll. Both started out a minority taste, became a mass taste, and then splintered into several subgenres. Both have been the typical cultural expressions of classes and epochs. Both started out aggressively fighting for their share of attention, novels attacking the drama, the tract, and the poem, rock attacking jazz and pop and rolling over classical music.”
—W. T. Lhamon, U.S. educator, critic. “Material Differences,” Deliberate Speed: The Origins of a Cultural Style in the American 1950s, Smithsonian (1990)
“You can no more bridle passions with logic than you can justify them in the law courts. Passions are facts and not dogmas.”
—Alexander Herzen (1812–1870)