[next] [prev] [prev-tail] [tail] [up]
Our study of programs has so far concentrated on two subclasses, namely, the
finite-memory programs and the recursive finite-domain programs. In this chapter the
study is extended to the general class of programs. The first section introduces the
mathematical systems of Turing transducers as a generalization to pushdown transducers,
and offers the systems for characterizing the notion of computation. The second
section considers the relationship between the general class of programs and the
Turing transducers. Section 3 considers the relationship between determinism and
nondeterminism in Turing transducers. Section 4 shows the existence of a Turing
transducer, called a universal Turing transducer, that can be programmed to compute any
computable function. The fifth section deals with the limitations of Turing transducers and
proves the undecidability of some problems, and the sixth section shows that
Turing transducers accept exactly the class of Type 0 languages. The chapter
concludes with Section 7, which introduces the Post's correspondence problem,
demonstrates its undecidability, and exhibits its usefulness in exploring undecidable
problems.
4.1 Turing Transducers
4.2 Programs and Turing Transducers
4.3 Nondeterminism versus Determinism
4.4 Universal Turing Transducers
4.5 Undecidability
4.6 Turing Machines and Type 0 Languages
4.7 Post's Correspondence Problem
Exercises
Bibliographic Notes
[next] [prev] [prev-tail] [front] [up]