Spacefish

Spacefish

Note: This is merely an idea. Nothing concrete has been worked out yet. Spacefish is based on a 2-dimensional storage grid. Initially there's only one storage cell available but through use of that initial cell one can "expand space" to get more storage cells.

Storage

Once a storage cell contains an active value it expands the space in all 8 directions by log2 of the active cell's value. However, every active cell distorts the values in other cells (halfed for every cell).

* Are active cells
Numbers indicate how much is added to a cell if it were active. 

0 -> put 8 in it


22222
24442
24*42   * = 8. Surrounding Cells are distorted (log2)
24442
22222

So, if you happen to place 1 into the upper left Corner you get

111
1*3222  * = 1 + 2 = 3
135442
 24*42  * = 8
 24442
 22222

Instructions

Instruction Description
>           Move to the cell to the left
<           Move to the cell to the right
^           Move to the cell above
v           Move to the cell below
+           Increment value in the current cell
-           Decrement value in the current cell
*           Multiply value in the current cell by two
/           Divide value in the current cell by two
[ ... ]     Loop: While current cell value is not zero
I           Read character from stdin
O           Write character to stdout
( ... )     If: If current cell value is zero
{ ... }     If: If current cell value is not zero

A cell is 8bit (Values 0 .. 255). If a value would reach 256 (or bigger) it wraps around. If you would move to a non existing cell it also wraps around.

Computational Class

Spacefish is Turing-complete because it can be translated from Bitwise Cyclic Tag. Programs are wrapped in ++--<->>+--<->>+-->+-->+<-<<[program] to properly initialize them. The data string is initialized to a single 1.

BCT	Spacefish
0	{->>}
10	{>{<[>>]+>-->+-->+<-<-<+[<<]>>>}<}
11	{>{<[>>]+>-->+-->+<-<<+[<<]>>>}<}

This translation uses the 2d space like a tape, using only the x-axis to hold data. Pairs of 2 integers are used to represent one bit in the data string: the first integer represents whether the bit is in the data string and the second integer represents the bit. The tape also starts with 00 to allow for moving the pointer back to the beginning and ends with 021 to allow for moving the pointer to the end and then expanding the tape.

Spacefish 1D

Spacefish 1D is going to be a version of Spacefish with only 1D Storage.

Incomplete code to demonstrate "distortion" (Python):

import math

space = [0]*11
j = 0
while j < 11:
  space[j] = [0,0]
  j += 1

prog = "++++>++>>+"
p = 0
ptr = 5
while p < len(prog):
  c = prog[p]

  # Instruction handling
  if(c == '+'):
    space[ptr][0] += 1

    j = 0
    while j < len(space):
      space[j][1] = 0
      j += 1

    j = 0
    while j < len(space):
      i = space[j][0] / 2
      d = 1
      while i >= 1:
        space[j + d][1] += i
        space[j - d][1] += i
        d += 1
        i /= 2
      j += 1

  elif(c == '>'):
    ptr += 1
    ptr %= 10
    while( (ptr != 5) and (space[ptr][1] == 0)):
      ptr += 1
      ptr %= 10
  
  print space

  p += 1

print map(sum,space)