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:
“I have no connections here; only gusty collisions,
rootless seedlings forced into bloom, that collapse.
...
I am the Visiting Poet: a real unicorn,
a wind-up plush dodo, a wax museum of the Movement.
People want to push the buttons and see me glow.”
—Marge Piercy (b. 1936)
“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)
“Democracy is the art and science of running the circus from the monkey-cage.”
—H.L. (Henry Lewis)