Browse Prior Art Database

Hierarchies of Turing Machines with Restricted Tape Alphabet Site

IP.com Disclosure Number: IPCOM000128509D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 11 page(s) / 30K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

It is shown that for any real constants [Equation ommitted] multitape Turing machines operating in space [Equation ommitted] can accept more sets than those operating in space LZ(n) _ ~ nrj 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. * This work was supported in part by the National Science Foundation under Grant GJ-35614.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Hierarchies of Turing Machines with Restricted Tape Alphabet Site

by Oscar H. Ibarra and Sartaj K. Sahni

Computer, Information, and Control Sciences Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 "W A Technical Report 73-13 October, 1973 Cover. .design courtesy of Ruth and Jay Leavitl Hierarchies of Turing Machines with Restricted Tape Alphabet Size by Oscar H. Ibarra and Sartaj K. Sahni University of Minnesota

Abstract

It is shown that for any real constants

(Equation Omitted)

multitape Turing machines operating in space

(Equation Omitted)

can accept more sets than those operating in space LZ(n) _ ~ nrj 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. * This work was supported in part by the National Science Foundation under Grant GJ-35614. <> <> 2 Introduction Results on tape and time complexity of algorithms involving Turing machine models are usually derived with the assumption that the devices have finite but arbitrary work tape alphabets. A consequence of this is that constant factors on tape-bounds and most time-bounds do not affect the complexity classes they define [1 and 5J, nor does addition of more work tapes to tape-bounded Turing machines change their computing power [1 and 2J. It seems natural to study tape and time complexity measures with the restriction that the Turing machines operate with, the same work tape alphabet. A recent paper of Seiferas, Fischer, and Heyer [4) includes such a study. In particular, they prove that for tape bounds L~(n) satisfying certain properties, the class of sets,accepted by single-tape Turing machines with m work tape symbols operating in L(n) space is properly contained in the class of sets accepted by single-tape Turing machines with Mm; work tags symbols operating in L(n) space for some

(Equation Omitted)

. In [3] it is shown that for tape bounds of the form

(Equation Omitted)

is, in fact, equal to

(Equation Omitted)

This paper continues the study started in [3]. Section 1 introduces the notation we shall be using. A theorem in [3] is also restated here as tile proofs in Sections 2 aid 3s~ill rely heavily on

University of Minnesota Page 1 Dec 31, 1973

Page 2 of 11

Hierarchies of Turing Machines with Restricted Tape Alphabet Site

it. In ,Section 2, we study the effect of increasing the work space by a constant factor while holding the number of symbols and work tapes constant. We are able to prove the existence of a refined hierarchy for all L(n) for which Theorem 1.1 is true. The main result of this section is Theorem 2.3, which states that for polynomial tape, (anrl.tape complexity class is properly contained in fbnr~ tape complexity class for any real constants b > a > 4. The effect...