Logic in Computation
Logic in computation applies the tools of mathematical logic to describe, specify, and reason about computational systems, and to characterize complexity classes by the logical resources needed to define their problems.
Definition
Logic in computation is the study of formal logical systems as languages for specifying and verifying computational behavior and as a measuring stick for computational complexity, treating computation and logical definability as two faces of the same phenomena.
Scope
This area covers temporal and modal logics for specifying the behavior of programs and reactive systems, descriptive complexity that equates complexity classes with logical definability, and the computational reading of Gödel's incompleteness theorems and their relationship to undecidability, drawing on the long interplay between logic and computer science.
Sub-topics
Core questions
- How can logical formulas specify the correct behavior of programs and systems?
- Can complexity classes be characterized purely by logical expressiveness?
- What is the computational content of Gödel's incompleteness theorems?
- How do logic and computation illuminate each other's limits?
Key theories
- Descriptive complexity
- Major complexity classes coincide with classes of problems definable in particular logics, so the resources of computation can be measured by logical expressive power rather than by machine time or space.
- Logics for program behavior
- Temporal, modal, and dynamic logics provide precise languages for specifying properties such as safety and liveness, forming the basis of formal verification of hardware and software.
Clinical relevance
The logical specification of system behavior underlies formal verification and model checking used to certify safety-critical hardware and software, while descriptive complexity offers a machine-independent perspective on tractability that informs database query languages and the foundations of complexity theory.
History
The bond between logic and computation runs from Gödel and Turing in the 1930s to the rise of computer science. Fagin's 1974 theorem launched descriptive complexity, Pnueli introduced temporal logic for programs in 1977, and model checking grew in the 1980s into a major verification technology, deepening the field's logical foundations.
Key figures
- Kurt Gödel
- Amir Pnueli
- Neil Immerman
- Ronald Fagin
Related topics
Seminal works
- immerman1999
- harel2000
Frequently asked questions
- How is logic used in computer science beyond pure mathematics?
- Logic supplies languages for stating exactly what a system should do and methods for proving it does. Temporal logics specify ongoing behavior, type systems and program logics certify code, and descriptive complexity recasts efficiency in terms of definability, making logic a practical engineering tool as well as a foundation.
- What does descriptive complexity reveal?
- It shows that complexity classes can be defined without reference to machines or time bounds, purely by which logic can express their problems. For example, the problems solvable in polynomial time on ordered structures are exactly those definable in a certain extension of first-order logic, linking computation to logical expressiveness.