Abstract:

Generalized computation theories include algorithms,computational complexity theory,computability theory,automata theory,and formal language theory.This paper discusses several typical problems in computation theory (computability theory and complexity theory) and reveals the importance of computational thinking in practical teaching.We elaborate the relation between computation theory and computer science from different perspectives.And then we describe Turing machine model and reveals the essential relation between Turing machine model and computational thinking. In addition,we discuss time complexity and space complexity in computer science,explain approximation algorithm,using packing problem examples. Finally,we emphasize the importance of computation theory in computer science education.

Key words: computability；computational complexity；computational thinking；computer science