In the article, there exists a crucially important hypothesis, referred to as the Church -Turing thesis, saying that every effective computation is mechanically performable by a procedure if and only if it is carried out by a Turing machine. Consequently, any computation beyond the power of Turing machines is also beyond the power of any computer. Therefore, these machines are central to the study of computation from a practical, mathematical, logical, as well as philosophical standpoint.

Chapter Contents:

• 8.1 Turing machines and their languages
• 8.2 Determinism
• 8.3 Universalness
• 8.3.1 Turing machine codes
• 8.3.2 Construction of universal Turing machines

Inspec keywords: Turing machines

Other keywords: Turing machine; Church-Turing thesis

Subjects: Automata theory