Three-Dimensionally Fully Space Constructible Functions

Makoto SAKAMOTO  Katsushi INOUE  Itsuo TAKANAMI 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E77-D  No.6  pp.723-725
Publication Date: 1994/06/20
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Artificial Intelligence and Cognitive Science
Keyword: 
multihead Turing machine,  three-dimensional Turing machine,  space complexity,  fully space constructible function, 

Full Text: PDF

Summary: 
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.