Table of Contents Fundamental Definitions and Results 1 1 The Priority Method 9 2 Hilbert's Tenth Problem 15 3 The Equivalence Problem for LOOP(1)- and LOOP(2)-Programs 25 4 The Second LBA Problem 37 5 LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences 41 6 Exponential Lower Bounds