Thanks for the awesome thought provoking game!

Besides being able to store 1's and 0's on the tape, a Turing Machine program can encode data by the state that it's in (which is kind of the whole point). I think that's what goldenkey is getting at when he said "you can use the code as memory". The fact that you're in this code or that code is how it remembers.

So to "pick up" a bit from the tape, move it somewhere else, and place it down, first you'd design a state machine to "move somewhere else" (whatever that means, let's say simply move 10 steps to the left), and then you'd duplicate it so you have twice as many states, one for "carrying a 1" and another for "carrying a 0".

When the read head sees the 1 or 0 on the tape (the source data), it branches to either the first state of the "carrying a 1" or the "carrying a 0" copy of the "move somewhere else" program, to move to the destination location on the tape. Each of those sub-programs would then have a final state that respectively writes a 1 or a 0 onto the tape, and then they can (but don't have to) merge back together into the same state (continuing the main "calling" program).

So the more bits you need to temporarily store in the imaginary Turing machine head that moves around (similar but not identical to a register), the more states you need (which can explode exponentially for complex programs)! So you could move two bits at a time by making four copies of the "move somewhere else" program for "carrying a 00 .. 11", and so on.

Instead of using a loop counter to loop four times, you could effectively just duplicate the states of your program four times, linking the end of one to the beginning of the next.

Making a conditional loop that loops a bounded number of times is a lot harder (and that's kind of what the game is about), requiring a whole lot more states, perhaps linked together in a switch structure like some sort of "Duff's device", or using some splice of tape for temporary storage.

It's easiest to simply represent numbers in unary (7 base 10 = 1111111 base 1) instead of binary, using 0 as a "stop bit", because memory efficiency isn't a concern (you have infinite tape, might as well use it!).

Manipulating binary numbers with Turing machines is a big deal since there is no direct support for it, so you have to implement it in "software". If you thought software floating point was slow, you haven't tried using a software binary library for Turing machines!

So to pick up and copy a unary number (as opposed to a single bit), bounded from 0 to n, you would have to make an initial state that looked at the first bit. If the first bit was 0 then it branches to the 0'th copy of the "move to somewhere else" program, which at the end branches to the "write the 0 stop bit" state. If the first bit was 1, then it would move right and test the next bit. If the second bit was 0, it would do the same as before, but the "move to somewhere else" program would be modified to account for having already moved one to the right, then it would write 1, move right, and merge back with the "write 0 stop bit" of the 0'th branch. And so on to n, so you have n modified copies of the "move to somewhere else" program, one for each possible value of the unary number, all merging back together into the final "write 0 stop bit" state...

Or you could encoded unary numbers as their value plus n consecutive 1's, then you could reserve patterns of fewer than n consecutive 1's as special control patterns or tags, which the "move somewhere else" functions could scan for, and not confuse them with unary numbers. Anything's possible, and you can use different encodings in different parts of the tape, just like normal computers. There is no one right way to program a Turing machine!

It's pretty tedious, and it would be easier to program with a macro assembler or vhdl-like tools (or FORTH, which was used for programming the CAM6 cellular automata rules). I wonder what high level Turing machine programming and debugging environments people have developed?

In the Philosophy of Computing course I took at UMD we used "PCOMP" TM simulator that ran on a PC, which was pretty good for its time but was like trying to construct a mnemonic memory circuit using stone knives and bearskins by today's standards.

http://terpconnect.umd.edu/~cherniak/philcomp/

The TM simulator in this Angelic Hierarchy game has an elegant interface, simple enough to make it an easily understandable and playable game, and it would be great to see how far it could go towards developing a full blown Turing machine visualization, experimentation, programming and debugging environment!

Thanks to hga's impeccable hoarding instincts, here is Marvin Minsky's enigmatic Universal Turing Machine written in TECO:

https://news.ycombinator.com/item?id=10161002

MSG: APL 1
DISTRIB: *BBOARD
EXPIRES: 03/17/81 23:08:54
MINSKY@MIT-MC 03/11/81 23:08:54 Re: too-short programs
APL is compact, I suppose. So is TECO. When I wrote the following
Universal Turing Machine, which works, I actually understood it.

i1Aul qq+^^0:iqm^[29iiq\356y0L1 00L1 11L2 A1L1
y0L1 0yR2 1AR2 AyR6 yyL3 00L0 1AL3 A1L4 yyL4 0yR5 11L7 A1L4
yyR5 0yL3 1AR5 A1R5 yyR6 0AL3 1AR6 A1R6 y0R7 0yR6 11R7 A0R2
^[j<sR^[;-d-2ciql-^^^[ci"ed^^^[cii^[ciuq'^[>
j<sL^[;-d-2ciql-^^^[ci"ed^^^[cii-2c^[ciuq'^[>jxblx1lx2lx3lx4lx5lx6lx7hk
iyyAyyAyy^[32<i0^[>ji110101110000010011011^[ 1uq<htmbqq=>

I do not advise attempting to understand this code, which is
almost as bad as that for the Universal Turing machine.