TrackSpan

TrackSpan is an OISC (technically, though its code is in form of ASCII art) esolang which is 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 is functionally complete.

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

Organizing data

We organize data in such pattern:

EnablePrev-
RegisterPrev-
0--
DataA--
0--
DataB--
0--
...
DataC--
0--
RegisterNext-
EnableNext-

0s are auxiliaries.

SetFalse

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

NOT

0+-0
a#!a

Duplicate

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

Swap

0 #--+---+-#- 0
a |-+##--|#|- b
0 ++#-|-+#+++ 0
b -|--+##---| a
0 -#---+----# 0

NOR

a + a
0 | 0
b # a nor b

Functionally complete

Now it's obvious that the chip is functionally complete.

Data transportation

There's only 1 bit per run can chips communicate, though we can construct a protocol to unlock their potential in multi-bits communication.

Since the language acts symmetrically, we may assume the previous chip is the sender side, and the next chip is the receiver side.

... (inf chips)
sender
receiver
... (inf chips)

Read Register

We need to withdraw the data in shared registers to our data structure that was proven to be functionally complete earlier.

E    E
R +- R
0 |+ 0
0 ## R

Kinda easy.

Write Register

E ----- E
R -##-- a
0 #+|-# 0
a |#+#| a
0 ++-++ 0

It overwrites Register.

Write Enable

E=0 --#-- a
R   --|-- R
0   +#+#+ 0
a   |+-|| a
0   #--+# 0

Now we've successfully docked Enables and Registers to the functionally complete system, and can do the simpliest data transfer.

Sender chip

We assume that both the sender and the receiver have initialized already and know their role.
We assume that the sender has decided who is going to receive and what is going to send.
We assume that the receiver has no idea about who's the sender.
We agree that k bits are sent continuously.

The sender first set its RegisterNext to 1, indicating where the data is from, and then enable the next chip.
Then the sender initializes a counter counting from 0 to k. Each time the sender is run, it send one data bit indexed by the counter.

Receiver chip

When the receiver is first enabled, it checks the two registers to check which of the neighbor is the sender.
Then the receiver initializes a counter counting grom 0 to k. Each time the receiver is run, it receive one data bit indexed by the counter.

Thus chips in correct modes can transfer as many data as they need.

Infinite chips

When all features are considered, the language is Turing_Complete.

Let's construct a Turing Machine.

Each chip should have a series of bits refering to its state, initialized as all 0, corresponding to state uninitialized.

When a chip is run, finding out that it's uninitialized, it checks its shared Registers. If the registers are 00, it can be inferred that the program was just started. The chip initializes itself as a Turing machine cell with the pointer at it. Otherwise, the chip initializes itself as a Turing machine cell without the pointer.

Each time a chip runs, it acts like a Turing machine head, overwriting the symbol, and trying to move the pointer. The movement are simulated by transfering the state of the machine to the neighbor chip and running it. The neighbor chip may do an initialization first, and then inherits the pointer's state.

Thus the program has successfully behaved like a Turing machine.