# AAAAAAAAAAAAAA!!!! Turing-completeness proof

Back to AAAAAAAAAAAAAA!!!!

This article proves AAAAAAAAAAAAAA!!!! is Turing-complete, by showing an example of translating a cyclic tag system program with input to A14!4 program.

## Assumptions

• Each cell is initialized with value 0
• The command `AAAA AAAA n!` acts as like ${\displaystyle [k]\leftarrow [k+n]}$ for each non-negative integer ${\displaystyle k}$
• The notation ${\displaystyle [k]\leftarrow [k']}$ means that you assign a value on index ${\displaystyle k'}$ to the memory indexed ${\displaystyle k}$.
• On #Program it is commented as `[k]=[k']`.
• The subroutine called by `AAAAAA n!` must not return a value with `AAA A AA AAAA n!`
• When reached to `AAAA A AAA!` in such subroutine, the subroutine ends.
• The subroutine may not use operators `AAAAA AA` nor `AAAAA AAA` for arguments of the commands.
• The subroutine called by the operator either `AAAAAA n, a b` or `AAAAA A n, a` must return a value.
• The interpreter must not reach to `AAAA A AAA!` in such subroutine before returning a value.
• Each command is represented with following POSIX ERE: /[A, ]+!/
• The comments, therefore, are not commands.

## Program

This program simulates a cyclic tag program (011,10,101) with input 1.

```@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@
@ Author: YamTokTpaFa
@ Published: 2020-04-24
@ License: Public Domain, I think
@
@ This program simulates a CT program (011,10,101) with input `1'.
@
@ Modified: 2020-04-29
@ Modified contents: put missing !'s
@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

@ subroutine 0: append0()
AAA A AAA AAAA!
@ [1]=0 (actually [1]-=1 if [1] else NOP)
AAAA AAA, AAA!
@ call subroutine 4 (append_([0],[1]))
AAAAAA AAA, A A!
AAAA A AAA!

@ subroutine 1: append1()
AAA A AAA AAA!
@ [1]=1 (actually [1]-=1; [1]+=1)
AAAA AAA, AAA!
AAAA AAA AAA!
@ call subroutine 4 (append_([0],[1]))
AAAAAA AAA, A A!
AAAA A AAA!

@ subroutine 2: move_tail()
AAA A AAA A!
@ [0]+=2
AAAA AAA AAAA!
AAAA AAA AAAA!
AAAA A AAA!

@ subroutine 3: shift()
AAA A AAA AA A!
@ [k]=[k+2] for each k
@@@ NOTE: I might have interpreted A14!4's specification incorrectly.
@@@ If so, please comment out `AAAA AAA, A!' in next line and
@@@ uncomment out `AAAA AAA A!'.
AAAA AAA, A! @ perhaps [k]=[k+2]
@ AAAA AAA A! @perhaps [k]=[k+2]
@ [0]=0, [1]=0
AAAA AAA, AAAA!
AAAA AAA, AAA!
@ move_tail()
AAAAAA A!
AAAA A AAA!

@ subroutine 4: append_([0],[1])
@ private subroutine
@ @[0]: where the tail of data string is
@ @[1]: what to append
AAA A AAA AAA, A A!
@ if [[0]]:
AAA AAAA AAA @ skip (arg) commands
AAA, @ times
AAA, A A @ times 2 2
AAAAA, AAAAA, AAAA! @ [[0]]
@ else:
@ [[0]]+=1
AAAA AAA AAAAA, AAAA!
@ if abs(1-[1]):
AAA AAAA AAA @ skip (arg) commands
AA AA, @ difference
AAA @ 1
AAAAA, AAA! @ [1]
@ else:
@ [[0]+1]+=1
AAAA AAA
AA A, @ plus
AAAAA AAAA @ [0]
AAA! @ 1
@ then: nothing
@ fi
@ return
AAA AAAA AAA A!
@ then:
@ [0]+=2 (actually move_tail())
AAAAAA A!
@ append_([0],[1])
AAAAAA AAA, A A!
@ fi
AAAA A AAA!

@@@ main routine
@ initialize [0] and [1]
AAAAAA AA A! @ move_tail()

@ set input
AAAAAA AAA! @ append1()

@ label 2:
AAAAA A!
@ if 1-[2]:
AAA AAAA AAA @ skip (arg) commands
AA AA, @ difference
AAA @ 1
AAAAA, A! @ [2]
@ else: quit
AA AAAA AA!
@ then: nothing
@ fi
@ if 1-[3]:
AAA AAA AAA @ skip (arg) commands
AAA, @ times
AA AA, @ difference
AAA @ 1
AAAAA, AA A @ [3]
AA A! @ 3
@ else:
@ append 011
AAAAAA AAAA! @ append0()
AAAAAA AAA! @ append1()
AAAAAA AAA! @ append1()
@ then: nothing
@ fi
@ shift()
AAAAAA AA A!
@ if 1-[2]:
AAA AAAA AAA @ skip (arg) commands
AA AA, @ difference
AAA @ 1
AAAAA, A! @ [2]
@ else: quit
AA AAAA AA!
@ then: nothing
@ fi
@ if 1-[3]:
AAA AAA AAA @ skip (arg) commands
AAA, @ times
AA AA, @ difference
AAA @ 1
AAAAA, AA A @ [3]
A! @ 2
@ else:
@ append 10
AAAAAA AAA! @ append1()
AAAAAA AAAA! @ append0()
@ then: nothing
@ fi
@ shift()
AAAAAA AA A!
@ if 1-[2]:
AAA AAAA AAA @ skip (arg) commands
AA AA, @ difference
AAA @ 1
AAAAA, A! @ [2]
@ else: quit
AA AAAA AA!
@ then: nothing
@ fi
@ if 1-[3]:
AAA AAA AAA @ skip (arg) commands
AAA, @ times
AA AA, @ difference
AAA @ 1
AAAAA, AA A @ [3]
AA A! @ 3
@ else:
@ append 101
AAAAAA AAA! @ append1()
AAAAAA AAAA! @ append0()
AAAAAA AAA! @ append1()
@ then: nothing
@ fi
@ shift()
AAAAAA AA A!
@ goto label2
AAA AA A!
```

### More explainations

• ${\displaystyle [k]~(k\geq 2)}$ represents data string.
• ${\displaystyle [2k]~(k\geq 1)}$ stands for if data string is continued:
• 0 means end of string while 1 stands for continuation.
• ${\displaystyle [2k+1]~(k\geq 1)}$ actually stores each bit of data string.
• Before the program tries to append a bit,
• the index to end of data string is stored to ${\displaystyle [0]}$, while
• the bit to append is stored to ${\displaystyle [1]}$.
• The command to shift indice stands for erasing the leftmost bit.