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 quickness with which all the “stuff” from childhood can reduce adult siblings to kids again underscores the strong and complex connections between brothers and sisters.... It doesn’t seem to matter how much time has elapsed or how far we’ve traveled. Our brothers and sisters bring us face to face with our former selves and remind us how intricately bound up we are in each other’s lives.”
—Jane Mersky Leder (20th century)
“The computer takes up where psychoanalysis left off. It takes the ideas of a decentered self and makes it more concrete by modeling mind as a multiprocessing machine.”
—Sherry Turkle (b. 1948)
“The sweetest and most inoffensive path of life leads through the avenues of science and learning; and whoever can either remove any obstructions in this way, or open up any new prospect, ought so far to be esteemed a benefactor to mankind.”
—David Hume (1711–1776)