Theory and Applications of Models of Computation

This book constitutes the refereed proceedings of the Third International Conference on Theory and Applications of Models of Computation, TAMC 2006, held in Beijing, China, in May 2006. The 75 revised full papers presented together with 7 plenary talks were carefully reviewed and selected from 319 submissions. All major areas in computer science, mathematics (especially logic) and the physical sciences particularly with regard to computation and computability theory are addressed. The papers are organized in topical sections on algorithm, computational complexity, learning theory, bioinformatics, security, formal methods, models of computation, computatability, and computable mathematics.