Antigram is an esoteric programming language created by User:Quintopia in 2020. It was mainly designed because there had not yet been a language on this wiki named "Antigram," and that was a surprise and a shame. The design principle is that it should resemble particle annihilation in a supercollider and that effects produced by annihilation should be nonlocal and hard to describe. In this way, it becomes difficult to prove the language is Turing complete, even as it would seem to have the power to be.
The state of a running Antigram program is a finite unbounded-length string of symbols. Implementations may define what alphabet these symbols may be drawn from, though some subset of Unicode characters would seem to be the most useful. The program listing defines the initial state of this string as well as a production string. The production string must contain every symbol that appears in the initial state string, though it may contain others.
To run the program, an interpreter will repeatedly perform the following steps until there are no adjacent pairs of identical symbols in the state string:
- Locate in the state string the first match of the pattern ABBC, where A, B, and C each match a single symbol
- Delete the symbols that matched BB from the state string
- Locate the first occurrence of the symbol matching A in the production string
- Append all symbols that appear before the matched symbol in the production string to the state string
- Locate the last occurrence of the symbol matching C in the production string
- Prepend all symbols that appear after the matched symbol in the production string to the state string
May be defined however an implementer wishes.
Let the symbols be the characters a, b, and c.
Production string: babbccac Initial state string: bbbbb
The execution unfolds thusly:
bbbbb The first pair is preceded by b, thus appending nothing, and succeeded by b, thus prepending ccac ccacbbb The first pair is preceded by c, thus appending babb, and succeeded by b, thus prepending ccac ccacccacbbabb The first pair is preceded by a, thus appending b, and succeeded by c, thus prepending nothing ccacacbbabbb The first pair is preceded by c, thus appending babb, and succeeded by a, thus prepending c cccacacabbbbabb The first pair is preceded by c, thus appending babb, and succeeded by a, thus prepending c ccacacabbbbabbbabb The first pair is preceded by a, thus appending b, and succeeded by b, thus prepending ccac ccacccacacabbabbbabbb The first pair is preceded by a, thus appending b, and succeeded by c, thus prepending nothing ccacacacabbabbbabbbb The first pair is preceded by a, thus appending b, and succeeded by a, thus prepending c cccacacacaabbbabbbbb You get the idea ccacacacaabbbabbbbbbabb ccacccacacacbbbabbbbbbabbbabb ccacacacacbbbabbbbbbabbbabbb ccacccacacacacbabbbbbbabbbabbbbabb ccacacacacacbabbbbbbabbbabbbbabbb And so on. This sequence appears to grow forever, adding a growing string of "ca" near the front, while adding runs of "b" of varying and unpredictable length separated by "a" at the end.
Optional Output Semantics
Implementers may define a subset of symbols that, when a pair of any of those symbols is deleted from the state string, a single copy of that symbol is output.
- Is Antigram Turing complete? (Guess: yes)
- If so, what is the minimum number of symbols needed to achieve TCness? (The lower bound is 3 as 2 can be shown to be incapable of growing without bound.)
This does not use the output extension. Syntax is: first line of program is production string, second line is initial state. No unicode support.
import re import sys class Halt(Exception): def __init__(self,state): self.state = state class AntigramProgram: def __init__(self,prog): self.productions = prog self.state = prog def update(self): matches = re.search(r"(.)(.)\2(.)",self.state) if not matches: raise Halt(self.state) pre = matches.group(1) post = matches.group(3) self.state = self.state[:matches.start(2)]+self.state[matches.start(3):] self.state += self.productions[:self.productions.index(pre)] self.state = self.productions[len(self.productions)-self.productions[::-1].index(post):] + self.state raw_input(self.state) def run(self): while True: self.update() if __name__=="__main__": if len(sys.argv)<2: print "No filename to execute." else: try: openfile = open(sys.argv, "r") except IOError: print("File '"+sys.argv+"' not found.") sys.exit(1) else: listing = openfile.read() openfile.close() listing = re.split('[\r\n]+',listing) prog = AntigramProgram(listing) finalstate = prog.run() print finalstate