Double Helix
Paradigm(s) | imperative |
---|---|
Designed by | Hakerh400 |
Appeared in | 2020 |
Computational class | Unknown |
Major implementations | Interpreter |
File extension(s) | .txt |
Double Helix is an esolang which operates on DNA. The computational class of this language is unknown.
Syntax
Source code consist of an arbitrary long double helix. Each helix can contain nucleotides A, C, G and T. There is no correlation between nucleotides (A does not need to be paired with T and C does not need to be paired with G).
For example:
G------------------T A------------------T A------------------T T----------------C A----------------T C--------------T G----------A T--------C A------C C--C AC A--G C------C T--------G T----------C T--------------T T----------------A T----------------A G------------------C C------------------C G------------------T C------------------T T------------------A A----------------C T----------------C A--------------G T----------C A--------C A------C T--A CG A--G T------C T--------C A----------A C--------------G T----------------A C----------------G T------------------G T------------------G T------------------A A------------------C T------------------C G----------------T T----------------C G--------------G A----------T G--------C G------T T--G TG G--T A------T G--------C T----------C C--------------C C----------------T T----------------T T------------------C A------------------T A------------------T C------------------G A------------------A G----------------G T----------------T T--------------G A----------C G--------C G------A A--A CA C--A C------C A--------T A----------A G--------------A T----------------T C----------------A A------------------C C------------------T T------------------T A------------------A A------------------A T----------------A C----------------G G--------------G T----------T A--------T G------C G--C CA G--G G------G A--------G A----------G A--------------T A----------------A T----------------A G------------------T T------------------A C------------------A C------------------C A------------------C G----------------T T----------------A C--------------A G----------C G--------G T------A T--T TG C--T A------T C--------T T----------A C--------------G C----------------G T----------------G T------------------T T------------------C A------------------C
It must be in that form (number of spaces and dashes must match). When there are no dashes between nucleotides, it represents the visual intersection of the double helix projection. After that point, the helices are switched.
Computation
Input and output are arrays of bits. There is a single string of bits called the main string.
When program starts, the main string is equal to the input string. We keep track of two values: helix index (either 0
or 1
) and nucleotide index (from 0
to the number of lines of the source code minus 1).
Both helix index and nucleotide index are initially 0
. The first nucleotide that appears in the source code belongs to the helix with index 0
.
Program state is uniquely defined by the main string, the helix index and the nucleotide index. Program halts when it reaches the same state two times.
We perform iterations until the program halts.
Iteration
We select the nucleotide determined by the helix index and the nucleotide index. Then we increment the nucleotide index modulo the DNA length.
Based on the nucleotide, do the following:
A
- Append0
to the main stringC
- Append1
to the main stringG
- Reverse the main stringT
- If the main string is empty, do nothing. Otherwise, remove the last bit and if the bit was1
, invert the helix index.
Simplified equivalent model
Any Double Helix program has an equivalent expression, with the same semantics, in the form:
AAAAAAAAAAAAAAAAAA... BBBBBBBBBBBBBBBBBB...
Where A is the helix which begins on the left (helix 0), and B is the helix which begins on the right (helix 1). An explicit labeling of helix 0 and helix 1:
0------------------1 0------------------1 0------------------1 0----------------1 0----------------1 0--------------1 0----------1 0--------1 0------1 0--1 01 1--0 1------0 1--------0 1----------0 1--------------0 1----------------0 1----------------0 1------------------0 1------------------0 1------------------0 1------------------0 1------------------0 1----------------0 1----------------0 1--------------0 1----------0 1--------0 1------0 1--0 10 0--1 0------1 0--------1 0----------1 0--------------1 0----------------1 0----------------1 0------------------1 0------------------1
Reasoning about the execution of the program is simpler in this form. For instance, the bit reverse program:
GCTT TATA
Execution starts at the top left and always proceeds to the right. We can give alternate names to the nucleotides, A = 0, C = 1, G = R, T = ?
R1?? ?0?0
It first executes R, reversing the main string. It then pushes a 1, then immediately pops it off and switches to the other helix, which is the lower line in this representation. Since the index increments no matter what, we are now on the final 0 of the second line, pushing a zero. Execution then wraps around back to the start of the second line/helix 1. The 0 is popped and the helix index remains the same, then another zero is pushed, it's then popped off. At this point the string has not changed, and we are back at the final 0 of helix 1, meaning we have repeated a state, execution halts with the string having been reversed.
Examples
Cat
A------------------A T------------------A
Reverse bits
G------------------T C------------------A T------------------T T----------------A
Computational class
It is probably equivalent to a push-down automaton, but it has not been proved.