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 with, connections, computer and/or science:
“Growing up human is uniquely a matter of social relations rather than biology. What we learn from connections within the family takes the place of instincts that program the behavior of animals; which raises the question, how good are these connections?”
—Elizabeth Janeway (b. 1913)
“The connections between and among women are the most feared, the most problematic, and the most potentially transforming force on the planet.”
—Adrienne Rich (b. 1929)
“The analogy between the mind and a computer fails for many reasons. The brain is constructed by principles that assure diversity and degeneracy. Unlike a computer, it has no replicative memory. It is historical and value driven. It forms categories by internal criteria and by constraints acting at many scales, not by means of a syntactically constructed program. The world with which the brain interacts is not unequivocally made up of classical categories.”
—Gerald M. Edelman (b. 1928)
“There are some things in science which should be brought to light. There are others, doctor, which should be left alone.”
—Griffin Jay, Maxwell Shane (1905–1983)