CSci 301 Lecture Notes

Week Five, Tuesday: Variants of Turing Machines

Ashwin Rao, a former USC instructor for Theory of Computation, wrote from New York to extend his regards and to remind us that he has a Web page of fun computation theory topics.

Multitape Turing Machines

Theorem 3.8

Corollary 3.8

Nondeterministic Turing Machines

Theorem 3.10

Corollary 3.11

Corollary 3.12

Enumerators

Theorem 3.13

Equivalence with Other Models


Email: Richard dot J dot Wagner at gmail dot com

notes05a.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by Rick Wagner. Copyright © 1998-2011, all rights reserved.