Semi_Thue Systems With an Inhibitor

Semi_Thue Systems With an Inhibitor Robert McNaughton Semi-Thue systems constitute a universal model of computation, in the sense that any decision problem about computations is reducible to a problem about semi-Thue systems. Every recursively enumerable language is the language of some semi-Thue system. (E.g., see Chapter 7 of [3].) Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-97-05

Semi_Thue Systems With an Inhibitor

Robert McNaughton

Semi-Thue systems constitute a universal model of computation, in the sense that any decision problem about computations is reducible to a problem about semi-Thue systems. Every recursively enumerable language is the language of some semi-Thue system. (E.g., see Chapter 7 of [3].)

Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY

cs-97-05