Hierarchies of turing machines with restricted tape alphabet size

✍ Scribed by Oscar H. Ibarra; Sartaj K. Sahni

• Publisher: Elsevier Science
• Year: 1975
• Tongue: English
• Weight: 480 KB
• Volume: 11
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(75)80049-3

✦ Synopsis

It is shown that for any real constants b > a ~ 0, multitape Turing machines operating in space Ll(n) = [bn'] can accept more sets than those operating in space Lo(n) = [an ~] provided the number of work tapes and tape alphabet size are held fixed.

It is also shown that Turing machines with k + 1 work tapes are more powerful than those with k work tapes if the tape alphabet size and the amount of work space are held constant.