1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by David Richerby, Raphael Nov 5 '17 at 16:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 Nov 5 '17 at 16:08