Concept

Logic in computer science

Summary
Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas: Theoretical foundations and analysis Use of computer technology to aid logicians Use of concepts from logic for computer applications 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 . The theory of computation is based on concepts defined by logicians and mathematicians such as Alonzo Church and Alan Turing. Church first showed the existence of algorithmically unsolvable problems 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." 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 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 completeness and correctness of software. The frame problem is a basic problem that must be overcome when using first-order logic to represent the goals and state of an artificial intelligence agent. The Curry–Howard correspondence is a relation between logical systems and software. This theory established a precise correspondence between proofs and programs. In particular it showed that terms in the simply-typed lambda-calculus correspond to proofs of intuitionistic propositional logic. represents a view of mathematics that emphasizes the relations between structures. It is intimately tied to many aspects of computer science: type systems for programming languages, the theory of transition systems, models of programming languages and the theory of programming language semantics.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related lectures (1)
Ethics and Law of AI
Delves into different ethical theories and thought experiments in the context of AI, exploring the challenges of defining AI.
Related publications (6)

Optimizing Majority-Inverter Graphs with Functional Hashing

Giovanni De Micheli, Mathias Soeken, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

A Majority-Inverter Graph (MIG) is a recently introduced logic representation form whose algebraic and Boolean properties allow for efficient logic optimization. In particular, when considering logic depth reduction, MIG algorithms obtained signific ...
IEEE2016

A Sound and Complete Axiomatization of Majority-n Logic

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, Anupam Chattopadhyay

Manipulating logic functions via majority operators recently drew the attention of researchers in computer science. For example, circuit optimization based on majority operators enables superior results as compared to traditional logic systems. Also, the B ...
Institute of Electrical and Electronics Engineers2016

Surveying the Evolution of Computing in Architecture, Engineering, and Construction Education

Ian Smith

This paper includes the results of an online survey that was conducted by the American Society of Civil Engineers (ASCE) task committee on computing education to assess the evolution of computing in architecture, engineering, and construction (AEC) educati ...
American Society of Civil Engineers2015
Show more
Related concepts (1)
Automated reasoning
In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer programs that allow computers to reason completely, or nearly completely, automatically. Although automated reasoning is considered a sub-field of artificial intelligence, it also has connections with theoretical computer science and philosophy.