TrackSpan

This is still a work in progress. It may be changed in the future.

TrackSpan is an OISC (technically, though its code is in form of ASCII art) esolang which seems to be Turing_Complete.

A TrackSpan program involves infinite chips with identical codes and individual memories.

Syntax

Chip

When considering only a single chip, the chip has k(k>=4) bits of memory, corresponding to k lines of the chip.
e.g.

----------
----------
----------
----------
----------
----------

This code indicates that each chip has 6 bits of memory.

Memory initialization happens in the following circumstances:

• When the program starts, all bits of all chips are set to 0.
• Each time the chip is about to run, the first and the last bits (corresponding to the first and the last line of the code) are set to 0.

Imagine that each line of the code is a track and, data flows from left to right. We have to add operators across the tracks to process data.

a-+---+-#--
b-#---|-|--
c---#-#-+--
d---+------

The code given above provides all 4 forms of our only operator NOR. From left to right (i.e. from first to last), the operation means:

• Set b to a nor b
• Set c to c nor d
• Set c to a nor c
• Set a to a nor c

Let's define the operation more precisely:

An operation includes a source, marked by + and a target, marked by #, drawn in the same column. The source and the target should be adjacent or be separated by exactly 1 track. In the latter case, use | to connect them. Operations the cross more than 1 track are illegal. Operations that cross each other are illegal. Here're some illegals:

-#-too--
-|-long-
-|-op---
-+------

-+--crossing-
-+-----------
-#-----------
-#-----------

The operations are executed from left to right, setting target to source nor target. Multiple operations at the same time are allowed as a syntactic sugar since their priorities have nothing to do with the result at all.

0--+0#0
0+0#1|-
0#1+1+1
0--#0--

All the characters except { +, #, | } are treated as comment, they're used for aligning operations. In the code above, 0 and 1 are used to hint the current value of the track, and - is used by default.

Since all the operations can be written in form of a = a nor b, and can further get abstracted into 2-tuples (a, b). TrackSpan is technically OISC.

Inter-chip cooperation

In order to make TrackSpan Turing-complete, we need to give it infinite memory and to enable it to run for as long as it wants. The simpliest(?) way to do this is to introduce infinite chips.

A program has infinite chips lined up. Each chip is able to communicate with its 2 neighbors.

When a program starts, all the bits in memory are set 0, and then a random chip is executed. (It's obvious that the choice of the chip doesn't affect the computation. )

Remember we have limited the minimum track amount at 4? That's because those 4 tracks are used for inter-chip communication.

Let's name the tracks:

--Enable---Prev--
--Register-Prev--
-----custom------
-----custom------
...
-----custom------
--Register-Next--
--Enable---Next--

• Each time before a chip runs, its 2 Enabling tracks are set to 0.
• All bits are preserved after running, and serve as the initial state for this chip's next run, except for Enabling tracks.
• Each time after a chip runs, the program checks 2 enabling tracks and takes actions.

Prev Next	Action
00	Run the current chip again
01	Run the next chip
10	Run the previous chip
11	Halt

Thus, it's possible for a TrackSpan program to run longer.

In order to let the chips communicate with their neighbors, Register tracks are introduced. Each chip's RegisterNext track is connected with its next chip's RegisterPrev track. Changing one automatically updates the other.

In summary, the program first randomly runs a chip, then the chip decides which chip is to run next, and can transfer 1 bit of data to it. The process of calling another chip keeps going.

Examples

Infinite loop

-
-
-
-

The Enable tracks keep 00, making the chip calling itself endlessly.

NOT operation

0-+--0
a-#-!a

SetFalse operation

1-+-1
a-#-0

Infinite loop No.2

#
+
-
-

This time chips keeps calling their previous chips, wasting more space.

Computational class

Single run of chip

When considering only 1 chip running once, it seems to be functionally complete.

To prove this, we need to construct ways to duplicate, move and process data.

Organizing data

We organize data in such pattern:

EP-
RP-
0--
a--
0--
b--
0--
...
c--
0--
RN-
EN-

where a, b, c... are actual data, and 0s are auxiliaries.

SetFalse

0+---+0
a|-#0|0
0#1+-#0

NOT

0+-0
a#!a
Duplicate
Swap
NOR
Now it's obvious that the chip is functionally complete.

Loop in single chip
When considering only 1 chip calling itself (i.e., looping), it seems to have the same ability of Bounded-storage machine.
Infinite chips
When all features are considered, the language seems to be Turing_Complete.