id: 03856412
dt: j
an: 03856412
au: Hemmerling, Armin
ti: D $\ne$ ND für mehrdimensionale Turing-Automaten mit sublogarithmischer
    Raumschranke.
so: Elektron. Inform.-verarb. Kybernetik 19, 85-94 (1983).
py: 1983
pu: Akademie-Verlag, Berlin
la: DE
cc: 
ut: determinism versus nondeterminism; sublogarithmic space; multi- dimensional
    Turing machines; space complexity
ci: 
li: 
ab: The main result says that nondeterminism is stronger than determinism in
    the scope of sublogarithmic space for multi-dimensional Turing
    machines. The author deals with the 2-dimensional case and claims that
    all the results can be transfered to higher dimensions. The machines
    under consideration are Turing machines with 2-dimensional input tape
    with one read-only head and with one 1-dimensional working tape again
    with one head. The space complexity is measured due to the working tape
    only. Inputs are finite 2-dimensional arrays. A set of such inputs is
    recognizable by a Turing machine with some space complexity iff this
    set is exactly the set of inputs for which there exists an accepting
    computation of the machine with the appropriate space bound. A set is
    decidable iff it and its complement are recognizable. Let $(D)Rec(f)$
    and $(D)Dec(f)$ be the (deterministically) recognizable and decidable
    sets with space complexity f. Let C be a constant function and R be a
    sublogarithmic function. Then $DRec(C)\backslash Dec(R)\ne \emptyset$
    and $Dec(C)\backslash DRec(R)\ne \emptyset.$
rv: A.Slisenko