Logic and Computations
Herman Ruge Jervell
Diese Publikation zitieren
Herman Ruge Jervell, Logic and Computations (2012), Logos Verlag, Berlin, ISBN: 9783832590017
34
Accesses
Accesses
Beschreibung / Abstract
This short book is a complete introduction to logic and computations. As computations we use finite state automata and turing machines. In logic we use sequent calculus and show its completeness. The interrelation between logic and computations is stressed by using predicate logic to simulate computations and seeing how undecidability phenomena on computations is transferred to incompleteness in logic. We end up with discussions of complexity both in logic and in computations.
A novel feature here is the use of AND-OR trees in describing alternating automata, in introducing sequent calculus, and in complexity.
A novel feature here is the use of AND-OR trees in describing alternating automata, in introducing sequent calculus, and in complexity.
Inhaltsverzeichnis
- BEGINN
- Introduction
- 1 Automata
- 1.1 DFA
- 1.2 NFA
- 1.3 AFA
- 1.4 Subsets of words
- 1.5 REG
- 1.6 Minimal DFA
- 1.7 Pumping lemma
- 1.8 PDA
- 1.9 Formal grammars
- 1.10 More automata
- 2 Descriptions
- 2.1 Logic as a description language
- 2.2 The language of words
- 2.3 Description †” using the term structure
- 2.4 Description †” finite chain
- 2.5 Description †” binary trees
- 2.6 Static descriptions †” data bases
- 2.7 Dynamic description †” abstract state machine .
- 3 Computations
- 3.1 Turings analysis
- 3.2 Five basic machines
- 3.3 Universal machine
- 3.4 Halting problem is undecidable
- 3.5 Busy beaver
- 3.6 Rice†™s theorem
- 4 Logic
- 4.1 Logic as language
- 4.2 Sequent calculus
- 4.3 Analysis and synthesis
- 4.4 Completeness
- 4.5 Equality
- 4.6 Variants
- 4.7 Logic for binary trees
- 4.8 Incompleteness
- 5 Complexity
- 5.1 Growth
- 5.2 Tiling a room
- 5.3 Computations in trees
- 5.4 Logarithms and exponentials
- 5.5 Notations
- 5.6 Indirect proofs and auxiliary notions
- 5.7 Large numbers and fast functions