| TR#: | CS0076 |
| Class: | CS |
| Title: | w-Computations On Turing Machines |
| Authors: | Rina S. Cohen and Arie Y.Gold |
| CS0076.pdf | |
| Abstract: | The paper develops the theory of Turing machines as recognizers of infinite (w-type) input tapes. Various models of w-type Turing acceptors are considered, varying mainly in their mechanism for recognizing w-tapes. A comparative study of the models is made. It is shown that regardless of the w-recognition model considered, non-deterministic w-Turing acceptors are strictly more powerful than their deterministic counterparts. Canonical forms are obtained for each of the w-Turing acceptor models. The corresponding families of w-sets are studied; normal forms and algebraic characterizations are derived for each family. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1976/CS/CS0076), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1976
To the main CS technical reports page