Hacker News new | past | comments | ask | show | jobs | submit login

Well, if the machine has only two states, it has only a single bit of internal memory. This means (almost) all information is in the picture.

Brain dump:

A one-state TM has no hidden state -- this means that it has no way to look at the surroundings (only the current field), which makes them rather boring. (All you'll get is lines or planes of one color, they cannot sensibly navigate the second dimension.)

Two-state TMs are 'clever' enough to change the color after moving, which means they can draw corners and thereby use the whole 2d plane. They still have to put all information into the picture, meaning you get to see all the gory details of information flow. You don't have the transition table, but you can read most of it off the image. You'll see all paths or areas in which movement in a single direction can happen without changing the color. Everything else has to be left in the picture, which means it will constantly overwrite stuff. This, in turn, means that it'll likely use groups of colors for one purpose.

Example: http://wry.me/hacking/Turing-Drawings/#2,8,0,3,2,1,7,3,0,7,0...

The start is boring: red - turn green & go up, green - turn black & go down, black - turn pink & move right (so far this could be done by a 1-state TM.) Pink does some state changes and introduces cyan, shortly after you'll see it 'sewing' to the left, leaving a thick structured line across the image, which is then expanded into a yellow-green covering of the whole black area (see how black/pink move right and cyan/yellow give turning directions and create yellow/green?) and then... ah, well just look at it.

Three-state TMs can hide quite a lot of information. As an example, the extra state can be used as a movement state, allowing non-destructive movement in one direction. (On jump mark (say, white), change to state #3 and keep going until you hit the next jump mark.) It can also be used to non-destructively look in one direction (e.g. for testing what color the left neighbor has). Combinations thereof can do pretty crazy stuff.

Adding more states basically just allows 'compressing' the picture more, which makes it more likely that you'll only see noise - especially if the TMs are randomly generated.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: