Complexity Analysis

This Chapter advocates a structure-oriented approach to simplify and generalize complexity investigations. The DIAGONALIZATION and REDUCTION methods applied to structures simplify to prove various classical results: undecidability of predicate logic and NP-completeness of propositional logic, Kleene’s RECURSION and ENUMERATION Theorems, Turing’s concept of UNIVERSAL MACHINES. Look-Compute-Move algorithms are explained as characteristic example for COMPUTING OVER STRUCTURES (here: with complex topological environments).