1
$\begingroup$

The group $(\mathbb{Z}, +)$ is automatic (ala Khoussainov) when using the "standard" representation in a decimal base. But if I want to use a different representation of Z, encoding my integers with the alphabet $\Sigma = \{y, z\}$
$0 = z$
$1 = yz$
$-1 = zy$
$2 = yyz$
$-2 = zyy$...

however the representation of each integer is not unique... $ z = yzy = yyzyy = yyyzyyy$ (the standard construction in set theory) This leads to problems later.

If we define
$a + b :=$ match $a$ with
$|z \rightarrow b$
$|y^nzy^m \rightarrow y^{n-1}zy^m + yb$
$|zy^n \rightarrow zy^{n-1} + by$

Now, by some convolution function, I can accept equations such as "$z + z = z$" or "$yyyz + zyy = yyyzyy$" but not equations such as "$z + z = yzy$" and "$yyyz + zyy = yz$"

Should this (unary integral addition) count as an automatic function?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.