Constitutes the refereed proceedings of the 4th International Conference on Theory & Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. This book addresses major areas in computer science, mathematics (especially logic) & the physical sciences particularly with regard to computation & computability theory.