Question

What is the category of languages recognised by a Turing machine with two-dimensional tape? Imagine the tape as an infinite matrix: at each move the movement of the head belongs to the set {stop, north, east, south, west}.

Answer 1

Pictorial representation of the 2D- Turing machine will looks like this

v	v	v	v	v	v	v	. . .	. . .
h	1	2	6	7	15	16	. . .	. . .
h	3	5	8	14	17	26	. . .	. . .
h	4	9	13	18	25	. . .	. . .	. . .
h	10	12	19	24	. . .	. . .	. . .	. . .
h	11	20	23	. . .	. . .	. . .	. . .	. . .
h	21	22	. . .	. . .	. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .

The head of a two dimensional tape moves one square up, down, left or right.

There can be formulas formed for 1-D Turing machince which will act simillar that of move right- left and up-down operations in 2-D Turing machine.Thus Turing machines with 1-D can simulate each and every move of 2-D Turing machines.

Hence they are at least as powerful as Turing machines with a two dimensional tape .Since Turing machines with a two dimensional tape obviously can simulate Turing machines with a one dimensional tape, it can be said that they are equally powerful.

So, The category of languages recognised by 2-D Turing machine will be same as normal Turing machine which is RECURSIVELY ENUMERABLE CLASS Languages.