Contents ~ vii
9.6 Techniques for TM Construction
289
9.6.1 Turing Machine with Stationary Head
289
9.6.2 Storage in the State
290
9.6.3 Multiple Track Turing Machine
290
9.6.4 Subroutines
290
9.7 Variants of Turing Machines
292
9.7.1 Multitape Turing Machines
292
9.7.2 Nondeterministic Turing Machines
295
9.8 The Model of Linear Bounded Automaton
297
9.8.1 Relation Between LBA and Context-sensitive
Languages
299
9.9 Turing Machines and Type 0 Grammars
299
9.9.1 Construction of a Grammar Corresponding to TM
299
9.10 Linear Bounded Automata and Languages
301
9.11 Supplementary Examples
303
Self-Test
307
Exercises
308
10. DECIDABILITY AJ\i'D RECURSIVELY El\TU1\fERABLE
LANGUAGES
309-321
10.1 The Definition of an Algorithm
309
10.2 Decidability
310
10.3 Decidable Languages
311
10.4 Undecidable Languages
313
10.5 Halting Problem of Turing Machine
314
10.6 The Post Correspondence Problem
315
10.7 Supplementary Examples
317
Self-Test
319
Exercises
319
322-345
332
325
327
333
11. COMPUTABILITY
11.1 Introduction and Basic Concepts
322
11.2 Primitive Recursive Functions
323
11.2.1 Initial Functions
323
11.2.2 Primitive Recursive Functions Over N
11.2.3 Primitive Recursive Functions Over {a. b}
11.3 Recursive Functions
329
11.4 Partial Recursive Functions and Turing Machines
11.4.1 Computability
332
11.4.2 A Turing Model for Computation
11.4.3 Turing-computable Functions
333
11.4.4 Construction of the Turing Machine That
Can Compute the Zero Function Z
334
11.4.5 Construction of the TUling Machine for ComputingThe Successor Function
335
http://engineeringbooks.net