Catshark
Catshark is a Joke language based on Deadfish, created by User:D.
The language is called Catshark because catsharks have two heads.
Commands
There are two accumulators, A and B.
The program is wrapped in an Infinite loop.
| Command | Behavior |
|---|---|
i |
Increment A.
|
d |
If A != 0, decrement A. Else, skip next instruction.
|
s |
Swap A and B.
|
o |
Print contents of both A and B.
|
The Python interpreter also supports h as a debugging instruction (to halt the program), but you don't need this instruction for Turing completeness.
Implementations
Python
It's not large, so I'll post the whole interpreter here:
import sys
prog = open(sys.argv[1]).read()
A, B = 0, 0
ptr = 0
while 1:
if prog[ptr] == 'i':
A += 1
elif prog[ptr] == 'd':
ptr += (A == 0)
A -= (A != 0)
elif prog[ptr] == 's':
A, B = B, A
elif prog[ptr] == 'o':
print(A, B)
elif prog[ptr] == 'h': # Debug instruction
break
ptr = (ptr+1) % len(prog)
C#
using System;
public class Catshark
{
public static void Main(string[] args)
{
int c;
int a = 0, b = 0;
string code = "";
bool ignored = false;
while ((c = Console.Read()) != -1)
{
code += Convert.ToChar(c);
}
while (true)
{
for (int i = 0; i < code.Length; i++)
{
if(ignored)
{
ignored = false;
continue;
}
c = code[i];
if (c == 'i')
{
a++;
}
if (c == 'd')
{
if (a != 0) a--;
else ignored=true;
}
if (c == 's')
{
int t = a;
a = b;
b = t;
}
if (c == 'o')
{
Console.Write(a);
Console.Write(' ');
Console.WriteLine(b);
}
if (c == 'h')
{
return;
}
}
}
}
}
Computational class
If d allowed skipping blocks of code (such as ( ... )), we can easily simulate two-counter machines.
With Gödel numbering, we can simulate however many "virtual registers" as we need to make it Turing-complete.
An example configuration of A:
2^a 3^b 5^c 7^d (simulate 4 virtual registers,
which can simulate two binary stacks,
and therefore a binary tape.)
11^e (A scratchpad for calculating the remainder)
13^f (Store current Instruction Counter)
17^g (A scratchpad for IC equality checks)
B is a scratchpad used to multiply A by a constant, divide A by a constant, or calculate remainders (i.e. checking if the counter is zero in the middle of a loop).
To multiply by a constant N, simply write a loop:
clr B
2:
dec A
inc B (write this N times)
jz A, 6, 2
6:
To divide by a constant A, do this:
clr B 2: dec A jz A, not_divisible, next (Write the above two instructions N times) next: inc B jz A, divisible, 2
Based on the structured program theorem, we can translate gotos to the following format:
PC = 1
while PC > 0:
if PC == 1: # Line 1
# Step 1 of algorithm
PC = ... # Goto next line
if PC == 2:
# Step 2
PC = ...
...
Unfortunately, d only lets you skip the next instruction. So I think it requires some kind of construction that I'm currently not aware of.