Interpreting Fish (no, not that Fish)

Non-deterministic Turing Machine, 20 states, 52 transitions (882 bytes maybe)

How do you convert this to bytes? I've written the files (absolutely not golfed) to execute this machine with Alex Vinokur's Simulator of a Turing Machine¹. wc -c outputs the following (excluding the description file and the input files):

 12 alphabet
 49 meta
740 rules
 81 states
882 total

Anyways, I was preparing for my Computer Science A-Levels, so I thought this would be a good exercise (I don't know what I was thinking). So here's the definition:

$$\begin{align*} M & = (Q, \Sigma, \iota, \sqcup, A, \delta) \\ Q & = \{q_{0},q_{1},q_{2},q_{3},q_{4},q_{5},q_{6},q_{7},q_{8},q_{9},q_{10},q_{11},q_{12},q_{13},q_{14},q_{15},q_{16},q_{17},q_{18},q_{19}\} \\ \Sigma & = \{< \: ; \: > \: ; \: , \: ; \: . \: ; \: X \: ; \: $\} \\ \iota & = q_0 \\ \sqcup & = $ \\ A & = \{q_0, q_5\} \end{align*}$$

^{(the transition function)}

Excuse the bad image, but I couldn't be bothered with redrawing this thing on a computer. If you actually want to decipher the transition rules, I recommend you read through the rules file I linked above.

---

I've used Xs instead of spaces because spaces are hard to visualize here and the simulator doesn't accept spaces in the alphabet.

The concept is fairly simple - q1 to q4 are used to catch right-facing fishes, q11 to q14 are used to catch left-facing fishes, q15 to q19 for crabs and the q5 to q10 blob is simply for inserting a space and moving all following characters one to the right.

If the string is interpretable, it accepts the string and the tape contains the string with spaces inserted. Otherwise it rejects the string (I guess this counts as no output - emptying the tape would be pretty easy but would require lots of transition rules and I don't think it would make the transition function prettier to look at).

---

_{¹ Note: It's difficult to compile. I had to edit the src/tape.cpp file and replace LONG_MAX with 1<<30 and then go to the demo directory, edit the Makefile to replace EXE_BASENAME with turing.exe and execute make. Then go to the directory with the files I've written and execute /path/to/turing/download/src/turing.exe meta.}

fish (yes, that fish), 437 bytes

This strikes me as one of those programming tasks where exactly one language is right.

#!/usr/bin/fish

set the_fishes "><>" "<><" ">><>" "<><<" "><>>" "<<><" "><<<>" "<>>><" ",<..>,"
set my_fishes

function startswith
        set -l c (echo -n $argv[2]|wc -c)
        echo $argv[1]|cut -c(math $c+1)-
        test $argv[2] = (echo $argv[1]|cut -c-$c)
end

function pickafish
        set -l fix 1
            while true
                if test $fix -gt (count $the_fishes); return 1; end

                if not set rest (startswith $argv[1] $the_fishes[$fix])
                            set fix (math $fix+1)
                        continue
                end    
                set my_fishes $my_fishes $the_fishes[$fix]
                    if test -z $rest
                        echo $my_fishes
                            exit
                    end
                    if not pickafish $rest
                    set my_fishes $my_fishes[(seq (math (count $my_fishes) - 1))]
                    set fix (math $fix+1)
                        continue
                end
        end
end

pickafish $argv[1]

The following version is still the longest answer to the challenge,

set t "><>" "<><" ">><>" "<><<" "><>>" "<<><" "><<<>" "<>>><" ",<..>,";set m;function p;set -l i 1;while true;test $i -gt 9; and return 1;if not set r (begin;set c (echo $t[$i]|wc -c);echo $argv[1]|cut -c$c-;test $t[$i] = (echo $argv[1]|cut -c-(math $c-1));end);set i (math $i+1);continue;end;set m $m $t[$i];if test -z $r;echo $m;exit;end;if not p $r;set m $m[(seq (math (count $m)-1))];set i (math $i+1);continue;end;end;end;p $argv[1]

but since this was done mostly for the pun (you'll excuse, I hope), better golfing is left as an exercise to the reader.

Pyth, 64 48 50 bytes

#jdhfqzsTsm^+msXtjCk2U2"<>""
\r.1"",<..>,"dlzB

Test case.

---

Version that doesn't take forever (O(9n/3)) here, in 52 bytes.

---

This is the brute force approach, generate all sequences and check whether any sum to the input. Fish diagrams compressed as characters, whose binary representations are the > and <. The whole thing is wrapped in a try-catch block so that no output occurs when no results are found.

This is an O(9n) solution.

Some characters are stripped above, because control characters are used. They are reproduced faithfully at the link above.

xxd output:

0000000: 236a 6468 6671 7a73 5473 6d5e 2b6d 7358  #jdhfqzsTsm^+msX
0000010: 746a 436b 3255 3222 3c3e 2222 0a5c 7212  tjCk2U2"<>"".\r.
0000020: 141b 1d2e 3122 222c 3c2e 2e3e 2c22 646c  ....1"",<..>,"dl
0000030: 7a42                                     zB