Church's Thesis (constructive Mathematics) - Relationship To Classical Logic

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:

    Sometimes in our relationship to another human being the proper balance of friendship is restored when we put a few grains of impropriety onto our own side of the scale.
    Friedrich Nietzsche (1844–1900)

    Harvey: Oh, you kids these days, I’m telling you. You think the only relationship a man and a woman can have is a romantic one.
    Gil: That sure is what we think. You got something better?
    Harvey: Oh, romance is very nice. A good thing for youngsters like you, but Helene and I have found something we think is more appropriate to our stage of life—companionship.
    Gil: Companionship? I’ve got a flea-bitten old hound at home who’ll give me that.
    Tom Waldman (d. 1985)

    Culture is a sham if it is only a sort of Gothic front put on an iron building—like Tower Bridge—or a classical front put on a steel frame—like the Daily Telegraph building in Fleet Street. Culture, if it is to be a real thing and a holy thing, must be the product of what we actually do for a living—not something added, like sugar on a pill.
    Eric Gill (1882–1940)

    Somebody who should have been born
    is gone.

    Yes, woman, such logic will lead
    to loss without death. Or say what you meant,
    you coward . . . this baby that I bleed.
    Anne Sexton (1928–1974)