$$ new machine, the Mesquite, is like a $($deterministic$)$ Turing machine, but it uses a binary

tree of memory cells in place of a tape. Every memory cell has two child cells, a left child

and a right child. Except for the root, every cell has a parent cell. $$ transition causes a

move to the left child, the right child, or the parent. $($If you are at the root and try to move

to the parent, you stay at the root.$)$ The computation always starts at the root memory

cell.

$($a$)$ Give a formal definition of a Mesquite.

$($b$)$ The Church$-$Turing thesis indicates that the Mesquite cannot decide any languages

that cannot be decided by a Turing machine. Justify that conclusion in this case

by demonstrating that every Mesquite computation can be carried out on a Turing

machine. $($ formal proof is not needed; a convincing detailed argument is needed.$)$