4.2 Complete Languages and Functions
192
4.3 Modification of Turing Machines
195
4.3.1 N-Track Turing Machine
195
4.3.2 Semi-infinite Tape/Offline/Multitape/
ND Turing Machines
196
4.3.3 Multidimensional/Two-state Turing Machine
196
4.4 Church-Turing’s Thesis
196
4.4.1 Counting
197
4.4.2 Recursive and Recursively Enumerable Language 197
4.4.3 Enumerating Strings in a Language
198
4.4.4 Non-recursively Enumerable Languages
199
4.5 Undecidability
199
4.5.1 Halting Problem
199
4.5.2 Implications of Halting Problem
201
4.5.3 Reduction to Halting Problem
201
4.5.4 Post’s Correspondence Problem
202
4.6 Rice’s Theorem
203
Glossary
203
Review Questions
204
Exercises
205
Short Questions and Answers
206
Chapter 5 Chomsky Hierarchy
210
5.1 Context Sensitive Grammars and Languages
210
5.2 Linear Bounded Automata
211
5.3 Relationship of other Grammars
211
5.4 The Chomsky Hierarchy
212
5.5 Extending the Chomsky Hierarchy
213
5.6 Unrestricted Grammar
213
5.7 Random-Access Machine
214
Glossary
214
Review Questions
215
Exercises
215
Short Questions and Answers
216
Chapter 6 Computability
218
6.1 Formal Systems
218
6.2 Recursive Function Theory
219
6.3 Primitive Recursive Functions
219
6.4 Composition and Recursion
222
6.5 Ackermann’s Function
229
xii
Con tents