Turing Machine for $L$={$a^nb^m: m=n^2, n \geq 1$} The problem only requires a description of the machine. 
I was thinking for each a you need to find 1 + 2k b's where k is the a your on. (ie for the for the first a find 1 bs, the second find 3 bs, fourth find 5 bs, etc). Obviously this is not the way to do it since you need to have difference cycles for each number of a's. 
 A: Suppose that the input is indeed of the form $a^nb^m$ (without knowing that $n^2=m$). Let us take as alphabet for the machine $\Sigma = \{a,\overline a, b\}$. The following machine decides $L$, with the hypothesis that the input consists of a run of $a$'s followed by a run of $b$'s:


*

*If the machine reads $a$:

*

*Replace $a$ by $\overline a$,

*Go the beginning of the input,

*If we read $a$ or $\overline a$, write $b$ on the auxiliary tape and move to the right,

*as soon as we read a $b$ on the input tape, rewind the tape until we read a character that is not $\overline a$,

*start over.


*If the machine reads $b$: check that the number of $b$'s to the right of the current position on the input tape is equal to the number of $b$'s on the auxiliary tape.


Assuming the input is $a^nb^m$, the machine tapes will look like the following:


*

*$\overline aa^{n-1}b^m$ on the input tape, $b^n$ on the auxiliary tape,

*$\overline{aa}a^{n-2}b^m$ on the input tape, $b^nb^n$ on the auxiliary tape,

*...

*$\overline{a^{n-1}}ab^m$ on the input tape, $b^{n(n-1)}$ on the auxiliary tape,

*$\overline{a^n}b^m$ on the input tape, $b^{n^2}$ on the auxiliary tape.


When rewinding up to the first character that is not $\overline a$, we hit a $b$, so that the checking stage begins. At that point, the machine accepts iff the auxiliary tape and $b^m$ match, i.e., iff we have $m=n^2$.
So this machine works with the hypothesis that the input is indeed of the form $a^nb^m$. It remains to describe a machine that checks whether this is indeed the case, but this is clear enough (even a deterministic finite automaton can do it, no need to use the tapes). Once you have described this automaton, you can couple the two transition functions to obtain a machine that decides $L$.
