Connections With Computer Science
The study of computability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however. Computer scientists often focus on concrete programming languages and feasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability.
The theory of semantics of programming languages is related to model theory, as is program verification (in particular, model checking). The Curry–Howard isomorphism between proofs and programs relates to proof theory, especially intuitionistic logic. Formal calculi such as the lambda calculus and combinatory logic are now studied as idealized programming languages.
Computer science also contributes to mathematics by developing techniques for the automatic checking or even finding of proofs, such as automated theorem proving and logic programming.
Descriptive complexity theory relates logics to computational complexity. The first significant result in this area, Fagin's theorem (1974) established that NP is precisely the set of languages expressible by sentences of existential second-order logic.
Read more about this topic: Mathematical Logic
Famous quotes containing the words connections, computer and/or science:
“Imagination is an almost divine faculty which, without recourse to any philosophical method, immediately perceives everything: the secret and intimate connections between things, correspondences and analogies.”
—Charles Baudelaire (1821–1867)
“The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower.”
—Robert M. Pirsig (b. 1928)
“Nor has science sufficient humanity, so long as the naturalist overlooks the wonderful congruity which subsists between man and the world; of which he is lord, not because he is the most subtile inhabitant, but because he is its head and heart, and finds something of himself in every great and small thing, in every mountain stratum, in every new law of color, fact of astronomy, or atmospheric influence which observation or analysis lay open.”
—Ralph Waldo Emerson (1803–1882)