High-level description of aTM
Perhaps the simplest way is to implement the following algorithm:


Initialize $y$ to 0
Initialize $n$ to 0
Compare $y$ to $x$; if $y = x$, accept; if $y &gt; x$, reject; otherwise, continue
Add $2n+1$ to $y$
Increment $n$ by 1
Jump to 3


The idea is that $y = n^2$ always. This is ensured using the formula $(n+1)^2 = n^2 + (2n+1)$.