Please login using the form on menu list.|
It is required to login for Full-Text PDF.
Three-Dimensionally Fully Space Constructible Functions
IEICE TRANSACTIONS on Information and Systems Vol.E77-D No.6 pp.723-725
Publication Date: 1994/06/20
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Artificial Intelligence and Cognitive Science
multihead Turing machine,
three-dimensional Turing machine,
fully space constructible function,
Full Text: PDF
There have been several interesting investigations on the space functions constructed by one-dimensional or two-dimensional Turing machines. On the other hand, as far as we know, there is no investigation about the space functions constructed by three-dimensional Turing machines. In this paper, we investigate about space constructibility by three-dimensional deterministic Turing machines with cubic inputs, and show that the functions log*n and log(k)n, k1, are fully space constructible by these machines.