Double Helix

From Esolang
Jump to navigation Jump to search
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 - Append 0 to the main string
  • C - Append 1 to the main string
  • G - Reverse the main string
  • T - If the main string is empty, do nothing. Otherwise, remove the last bit and if the bit was 1, 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.

Interpreters

Interpreter