1
$\begingroup$

This question is from a Computer Theory Course

What is the category of languages recognized by a MT with a two-dimensional tape? The Tape is an infinite matrix. For each move the head shift belongs to the set $S$ = {stop, north, east, south, west}

My approach

I know that TM recognize Recursively Enumerable or type $0$ languages, but how to show a proof for this answer?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ As with any such question, you show that one of these Turing machines can be simulated by an ordinary one. Have you, for example, seen proofs that multitape Turing machines have the same power as single-tape machines? I suggest you try the simulation and ask a more specific question if you have difficulties. In general, the benefit of this kind of exercise comes from solving it yourself, not from being told the answer. $\endgroup$
    – David Richerby
    Commented Nov 5, 2017 at 16:08

0

Reset to default

Browse other questions tagged or ask your own question.