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 A¹⁴!⁴ program.

Assumptions

• Each cell is initialized with value 0
• The command AAAA AAAA n! acts as like $[k]\leftarrow [k+n]$ for each non-negative integer $k$
  • The notation $[k]\leftarrow [k']$ means that you assign a value on index $k'$ to the memory indexed $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

• $[k]~(k\geq 2)$ represents data string.
• $[2k]~(k\geq 1)$ stands for if data string is continued:
  • 0 means end of string while 1 stands for continuation.
• $[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 $[0]$, while
  • the bit to append is stored to $[1]$.
• The command to shift indice stands for erasing the leftmost bit.