Loading...
Please wait, while we are loading the content...
On the Power of Real-Time Turing Machines: k Tapes Are More Powerful than k-1 Tapes (1999)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bruda, Stefan D. Akl, Selim G. |
| Abstract | We show that, for any integer k, there is at least one language which is accepted by a k-tape real-time Turing machine, but cannot be accepted by a (k-1)-tape real-time Turing machine. We show therefore that the languages accepted by real-time Turing machines form an infinite hierarchy with respect to the number of tapes used. |
| File Format | |
| Language | English |
| Publisher Date | 1999-01-01 |
| Access Restriction | Open |
| Subject Keyword | Real-time Turing Machine K-1 Tape K-tape Real-time Turing Machine Infinite Hierarchy Tape Real-time Turing Machine |
| Content Type | Text |
| Resource Type | Technical Report |
