a) The idea here is that a computer (with sufficiently large but finite memory) can compute the remainder of arbitrary large natural numbers when divided by $m$. The following describes a Machine for computing the remainder of a given number modulo $m$ in base $k$:

* Inputs: Set $\{0, 1, \dots, k-1\}$.
* States: A state exists for each pair $(i, j)$ of $\{0, 1, \dots, m-1\}$.
* Outputs: The output of state $(i, j)$ is $j$.
* Starting State: $(1, 0)$.
* Transition Function: When $r$ is entered, the state of the Machine changes from $(i, j)$ to $(i', j')$, where $i'$ and $j'$ are the remainders of $ki$ and $j + ri$ when divided by $m$, respectively.

b) Let $X$ be the Machine that computes $(a_n)$ in base $k$. To introduce a Machine that computes $(b_n)$, where $b_n = a_{n+1}$, in base $k$, first a Machine is designed that takes an $r$-digit number $n$ as input and gives $(a, b)$ as output, where $a$ and $b$ are the $r^{th}$ and $(r+1)^{th}$ digits of $n+1$ in base $k$ (from right). Note that $n+1$ has at most $r+1$ digits, and if it has only $r$ digits, then $b$ will be zero. The following Machine will perform this operation:

* Inputs: Set $\{0, 1, \dots, k-1\}$.
* States: A state exists for each pair $(a, b)$ of integers, where $0 \le a < k$ and $b \in \{0, 1\}$.
* Outputs: The output of state $(a, b)$ is $(a, b)$ itself.
* Starting State: $(1, 0)$.
* Transition Function: When $r$ is entered, the state of the Machine changes from $(a, b)$ to $(a', b')$, where $a'$ is the remainder of $r + b$ when divided by $m$, and $b'$ is 0 for $r + b < k$ and 1 elsewhere.

Call this Machine $B$. Now, make Machine $Y$ from $B$ and $X$ to compute $(b_n)$. Denote the set of states and the Starting State of $X$ by $S_X$ and $S_B$, respectively. $S_X$ and $S_B$ are defined similarly. The following Machine will perform the desired operation:

* Inputs: Set $\{0, 1, \dots, k-1\}$.
* States: $S_X \times S_B$.
* Outputs: The output of state $(x, y)$, where $x \in S_X$ and $y \in S_B$, is defined as follows: Let $(a, b)$ be the output of state $y$ in $B$. Now, if $b = 0$, define the output of $(x, y)$ (in $Y$) to be equal to the output of $x$ (in $X$); and if $b \neq 0$, define it to be the output of $X$ after entering $b$ when $X$ is in state $x$.
* Starting State: $(s_X, s_B)$.
* Transition Function: When $r$ is entered, the state of the Machine changes from $(x, y)$ to $(x', y')$, where $y'$ is the state of $B$ after entering $r$ when it is in state $y$. Now, if $(a, b)$ is the output of $y'$, $x'$ will be the state of $X$ after entering $a$ when it is in state $x$.

To compute $c_n = a_{2n}$, first define a Machine $C$ similar to $B$ for the purpose of multiplication by 2. Then use $C$ instead of $B$ in the definition of $Y$ above to get the desired result. The Machine $C$ is described as follows:

* Inputs: Set $\{0, 1, \dots, k-1\}$.
* States: A state exists for each pair $(a, b)$ of integers, where $0 \le a < k$ and $b \in \{0, 1\}$.
* Outputs: The output of state $(a, b)$ is $(a, b)$ itself.
* Starting State: $(0, 0)$.
* Transition Function: When $r$ is entered, the state of the Machine changes from $(a, b)$ to $(a', b')$, where $a'$ and $b'$ are the quotient and remainder of $2r + b$ when divided by $k$, respectively.

c) No! Assume to the contrary that $X$ is a Machine that computes $(a_n)$ in base 3. Let $N$ be the number of states of $X$. Note that for a sufficiently large natural number $m$, the number of $m$-digit perfect square numbers in base 3 is more than $N$. So there are two perfect squares $a$ and $b$ such that after entering digits of these two numbers to $X$ (from right) the same state is reached. Therefore, entering numbers of the form $a + 3^m n$ and $b + 3^m n$ results in the same output. Hence if $(a_n)$ is 3-Computable, then for each natural number $n$, $a + 3^m n$ is a perfect square if and only if $b + 3^m n$ is a perfect square. But this is impossible, because the difference of these numbers is $b - a$ (which is constant), whereas the difference of consecutive perfect square numbers approaches infinity.

d) Suppose that $X$ is a Machine with inputs from the set $\{0, 1, \dots, k-1\}$. It will be shown that each $k$-Computable sequence is $k$-Left Computable, the converse can be proved similarly. To do this, it suffices to introduce a Machine $Y$ with the same input set as $X$ such that the output of $Y$ after entering digits of a number from left to right equals to the output of $X$ after entering digits of that same number from right to left. Suppose that $\{s_1, s_2, \dots, s_m\}$ is the state set of $X$, $s_1$ its Starting State and $x_i$ the output of state $s_i$. The following Machine will perform the desired operation:

* Inputs: Set $\{0, 1, \dots, k-1\}$.
* States: All $m$-tuples $(A_1, A_2, \dots, A_m)$ of partitions of the set $\{s_1, s_2, \dots, s_m\}$.
* Outputs: The output of state $(A_1, A_2, \dots, A_m)$ will be $A_i$, where $s_1 \in A_i$.
* Starting State: $(\{s_1\}, \{s_2\}, \dots, \{s_m\})$.
* Transition Function: When $r$ is entered, the state of the Machine changes from $(A_1, A_2, \dots, A_m)$ to $(B_1, B_2, \dots, B_m)$, where $B_i$ is the set of all those states of $X$ that change to a state in $A_i$ after entering $r$ in $X$.