Computational complexity/hw1

การบ้าน 1 มี xx ข้อ

1 (1.7) Define a two-dimensional Turing machine to be a TM where each of its tapes is an infinite grid (and the machine can move not only Left and Right, but also Up and Down). Show that for every (time-constructible) $T:N\rightarrow N$ and every Boolean function $f$, if $f$ can be computed in time $T(n)$ using a two-dimensional TM then $f\in DTIME(T(n)^{2})$.