Editing Logic in computer science (section)

== Theoretical foundations and analysis ==
Logic plays a fundamental role in computer science.  Some of the key areas of logic that are particularly significant are [[computability theory]] (formerly called recursion theory), [[modal logic]] and [[category theory]]. The [[theory of computation]] is based on concepts defined by logicians and mathematicians such as [[Alonzo Church]] and [[Alan Turing]].<ref>{{cite book|last=Lewis|first=Harry R.|url=https://archive.org/details/elementsoftheory00lewi|title=Elements of the Theory of Computation|publisher=[[Prentice Hall]]|year=1981|author-link=Harry R. Lewis}}</ref><ref>{{cite book|last=Davis|first=Martin|title=The Universal Turing Machine|publisher=Springer Verlag|chapter-url=https://books.google.com/books?id=YafIDVd1Z68C&pg=PA290|editor=Rolf Herken|access-date=26 December 2013|chapter=Influences of Mathematical Logic on Computer Science|date=11 May 1995|isbn=9783211826379|author-link=Martin Davis (mathematician)}}</ref>  Church first showed the existence of [[Undecidable problem|algorithmically unsolvable problem]]s using his notion of lambda-definability.  Turing gave the first compelling analysis of what can be called a mechanical procedure and [[Kurt Gödel]] asserted that he found Turing's analysis "perfect.".<ref>{{cite book|last=Kennedy|first=Juliette|authorlink = Juliette Kennedy|title=Interpreting Godel|publisher=Cambridge University Press|url=https://books.google.com/books?id=ulw3BAAAQBAJ&q=Godel+convinced+by+Turing%27s+analysis&pg=PA118|access-date= 17 August 2015|isbn=9781107002661|date=2014-08-21}}</ref> In addition some other major areas of theoretical overlap between logic and computer science are:
*[[Gödel's incompleteness theorem]] proves that any logical system powerful enough to characterize [[Peano axioms#Peano arithmetic as first-order theory|arithmetic]] will contain statements that can neither be proved nor disproved within that system.  This has direct application to theoretical issues relating to the feasibility of proving the [[formal verification|completeness and correctness]] of software.<ref>{{cite book|last=Hofstadter|first=Douglas R.|title=Gödel, Escher, Bach: An Eternal Golden Braid|publisher=Basic Books|isbn=978-0465026562|author-link=Douglas Hofstadter|url=https://archive.org/details/gdelescherbachet00hofs|date=1999-02-05}}</ref>  
*The [[frame problem]] is a basic problem that must be overcome when using [[first-order logic]] to represent the goals of an [[artificial intelligence]] agent and the state of its environment.<ref>{{cite journal|last=McCarthy|first=John|author2=P.J. Hayes |title=Some philosophical problems from the standpoint of artificial intelligence|journal=Machine Intelligence|year=1969|volume=4|pages=463–502|author-link1=John McCarthy (computer scientist)|url=http://www-formal.stanford.edu/jmc/mcchay69.pdf}}</ref> 
<!-- *[[Category theory]] is the formal analysis and transformation of [[Graph theory|directed graphs]], an area with some applications in computer science, most notably programming languages and compilers.<ref>{{cite journal|last=DeLoach|first=Scott|author2=Thomas Hartrum |title=A Theory Based Representation for Object-Oriented Domain Models|journal=IEEE Transactions on Software Engineering|date=June 2000|volume=25|issue=6|doi=10.1109/32.852740|pages=500–517}}</ref> -->
*The [[Curry–Howard correspondence]] is a relation between logical systems and programming languages. This theory established a precise correspondence between [[formal proof|proof]]s and programs.  In particular it showed that terms in the [[simply typed lambda calculus]] correspond to proofs of [[intuitionistic logic|intuitionistic propositional logic]].
*[[Category theory]] represents a view of mathematics that emphasizes the relations between structures.  It is intimately tied to many aspects of computer science: [[type system]]s for programming languages, the theory of [[transition system]]s, models of programming languages and the theory of [[programming language semantics]].<ref>{{cite book|first=Michael|last=Barr|title=Category Theory for Computing Science|year=1998|author2=Charles Wells|url=https://www.math.mcgill.ca/barr/papers/ctcs.pdf|publisher=[[Centre de Recherches Mathématiques]]}}</ref>
*[[Logic programming]] is a [[programming paradigm|programming]], [[database]] and [[knowledge representation]] paradigm that is based on formal [[logic]]. A logic program is a set of sentences about some problem domain. Computation is performed by applying logical reasoning to solve problems in the domain.  Major logic programming language families include [[Prolog]], [[answer set programming|Answer Set Programming]] (ASP) and [[Datalog]].