This book constitutes the refereed proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007.The 67 revised full papers presented together with two plenary lectures were carefully reviewed and selected from over 500 submissions. It addresses all major areas in computer science; mathematics, especially logic; and the physical sciences, particularly with regard to computation and computability theory. The papers–-featuring this crossdisciplinary character-–particularly focus on algorithms, complexity and computability theory, giving the conference a special flavor and distinction.