Hacker News new | past | comments | ask | show | jobs | submit login
Turing Drawings (wry.me)
154 points by nemo1618 on May 14, 2013 | hide | past | favorite | 119 comments



This is amazing. My favourites seem to always have only 2 states.

"sunset and nightfall":

http://wry.me/hacking/Turing-Drawings/#2,15,0,3,1,1,1,3,1,10...

"shoreline EQ"

http://wry.me/hacking/Turing-Drawings/#2,22,1,6,2,0,6,0,0,21...


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.






Is it even fully comprehensible why this particular configuration looks like sand?


Original author here. It only has 3 states and 6 symbols, so the transition table is not that big. If you visualized it slow enough, you might be able to understand the process behind it, so to speak. Although sometimes, simple rules can yield chaotic behavior. Someone told me they were working on a fork with utilities to visualize the transitions, that might be helpful.


That was me but so far it's just something I'd like to see. If anyone else would like to tackle it I'd be happy to watch theirs.

The general idea is a graph of the states and transitions (laid out by d3 or something?), labeled by color with little arrows for the next direction, with the current state and transition highlighted. Also a magnified 'fat bits' view of the head's neighborhood. You'd only see these at the slower speeds where you can conceivably follow, like the marker around the head in the current system.

Also you'd want single-stepping to go with this. I have added that but not pushed it to the webpage or the repo. (There was some little bug I haven't got to.)


at the fastest speed, this looks like accumulated rain on a side window of a car driving on the freeway, being blown off, from the vantage point of someone in the car


I found a glider! http://www.wry.me/hacking/Turing-Drawings/#4,3,2,2,1,3,2,2,3...

The glider appears after a few seconds of high speed.

Very nice implementation!


I got some bubbles wandering up the screen quite slowly: http://wry.me/hacking/Turing-Drawings/#4,3,1,2,2,0,1,3,2,1,2...

Not exactly a glider, but it looks like this does at the start, but reversed...sort of... (maybe)



The three distinct stages are fascinating. The third stage is like white caps on the ocean viewed from an airplane.


After revisiting the thread and viewing some of the other good finds, this is still the most astonishing one I've seen. The end state is very pretty, and the final evolution continues in what appears to be a perplexing nearly-stable chaotic pattern.


Holy shit. And now for something completely different. We interrupt tonight's broadcast of "Slowly Growing Purple Lines" to present you "Flowing Glitter".


Fascinating. It's like the Harlem Shake of Turing Drawings.


Wolframite here: these would make a good summer school project for our summer school (plug: the 2013 one is coming up, apply at https://www.wolframscience.com/summerschool/ if you're interested in this kind of stuff and want to do a 3-week project).

In fact I studied the space-filling behavior of precisely these 2D Turing machines in 2009. For low numbers of states and colors you can enumerate them exhaustively and calculate the distribution of space-filling efficiency (log-normal, if anyone is interested).

The full spectrum of behavior is quite fascinating to catalog. All these kinds of simple computational system have a character and 'zaniness' all their own.

Putting on a more scientific hat, it might be interesting to look at block-entropy measures and find interesting rulesets that way.

P.S. To the author: this is a great implementation! Really nice to play with. Check out http://reference.wolfram.com/mathematica/ref/TuringMachine.h... for the one built into the Wolfram Language.


This one takes a bit to get going, but then it does a gigantic phase transition into something like wind (play on max speed):

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

This one starts with a great wave effect:

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



This is actually very good compared to other findings; the pattern starts to disappear and then regenerates itself in different ways. Accompanying horizontal lines look like an ocean.


Wow, I finally got a neat one via random. 4 states, 13 symbols, yields an interesting illusion of depth as "blocks" start moving towards and away from the viewer. Recommended two notches down from default speed, three down if you're patient.

http://wry.me/hacking/Turing-Drawings/#4,13,3,1,0,0,5,1,2,1,...


My take: Mondrian scrolls. http://wry.me/hacking/Turing-Drawings/#3,3,2,1,1,0,1,2,1,1,1...

I really appreciate this art of randomness, and in particular the fact that it is theoretically equivalent to any computing machine (given much, much more memory and states).



This is great, but can't you only show me drawings which halt? I sit there waiting and I don't know if they'll stop...


I'm sure someone on rentacoder can figure it out:

http://blog.willbenton.com/2008/11/rent-a-coder-hilarity/


If it's a limited number of states in the automaton, and a limited amount of "tape" in the canvas, it's not a Turing machine, it's a Finite-State Automaton, which is easy to analyze for loops.


Here's one that halts very late: http://wry.me/hacking/Turing-Drawings/#3,3,1,2,0,1,1,0,0,2,3...

And here's an amazing one: it fills the canvas, getting slower and slower. It will probably take days to complete fill it: http://wry.me/hacking/Turing-Drawings/#10,3,9,2,1,5,2,3,8,1,...


The world is finite, so every drawing eventually loops.

However, the state space is something like k * 2^18 * n^(2^18), where k is the number of states and n the number of symbols. For the default (4, 3) this is 3.125 * 10^125080, so you could be waiting for a while :)


Would every drawing have to loop? Pi doesn't. I personally don't actually know if there's something about this specifically that would force every drawing to loop, though.


that's a hard design decision.


Yeah, I'm undecided.




These are called Turmites: http://en.wikipedia.org/wiki/Turmite

Nice implementation of it.



Love how long this takes to evolve. Nice to watch fast or slow. http://www.wry.me/hacking/Turing-Drawings/#4,3,0,2,0,3,2,0,2...


The steady state at the end on a very slow setting is awesome.


I found one that looks like the ocean. (Try on max speed!)

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

This one's building something in the middle:

http://wry.me/hacking/Turing-Drawings/#4,3,3,2,2,3,1,3,3,2,1...

A very clear fractal with triangles:

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


This one has a kind of parallax effect going on:

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

You'll want to watch it about four notches down from "fastest".

This is a really cool project! It has a kind of AI feel to it. The website needs a way for users to vote on others' creations, and then they can be selectively "mutated" and evolved to produce really cool ones. The best ones will survive through upvotes. Who knows what you'd end up with?


Cool, I pressed random a few times from yours and got this. http://wry.me/hacking/Turing-Drawings/#4,3,3,2,3,2,1,2,0,1,2... I'm falling!!!


Fantastic. It's amazing how attached I become to the good ones, it's like I've discovered a precious truth.

So here's some driving rain: http://wry.me/hacking/Turing-Drawings/#4,3,1,2,2,0,2,0,3,1,2...


The sky above the port was the color of television, tuned to a dead channel.

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


I quite like this one, it's as though the environment deteriorates. Don't watch it to fast:

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

At one point, right before it goes over the "entropy cliff" it creates what looks like a lot of Sierpinski triangles:

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

I found it quite interesting that one as complex as this could stabilize:

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

This seems to end up like a frozen lightning bolt: http://wry.me/hacking/Turing-Drawings/#4,5,3,3,3,2,4,0,2,2,3...

This creates a pattern almost like hair in the wind: http://wry.me/hacking/Turing-Drawings/#4,5,2,3,0,2,4,3,0,3,1...

Seems as though it's many cats standing on each others heads: http://wry.me/hacking/Turing-Drawings/#4,5,0,3,1,0,3,1,2,1,0...

Like waves on a beach: http://wry.me/hacking/Turing-Drawings/#4,5,3,4,2,1,2,2,0,4,0...

Some otherworldly data wind: http://wry.me/hacking/Turing-Drawings/#4,5,0,3,3,3,3,1,0,3,2...

Eventually, all clouds fade away: http://wry.me/hacking/Turing-Drawings/#4,4,1,1,1,1,2,1,2,3,3...

In and out of phase: http://wry.me/hacking/Turing-Drawings/#4,4,2,2,0,3,1,2,3,1,0...

Like sand dunes moving: http://www.wry.me/hacking/Turing-Drawings/#4,3,1,1,3,3,1,0,2...

Saws on parade: http://www.wry.me/hacking/Turing-Drawings/#4,3,0,2,0,2,2,3,1...

Scooty lightning: http://www.wry.me/hacking/Turing-Drawings/#4,3,3,2,0,3,2,2,3...


Many of these are quite beautiful.

The NKS-style question to ask here is: what computations are these doing? Totally unique-unto-themselves computations? Potentially useful computations? Computations analogous to familiar human ones? How would we know? Can we know? Do we run into the limits of undecidability?

The cyclic boundary conditions somewhat 'spoil' things, though. Maybe a particular rule was "destined to multiply input by 5" or "calculate log-2 of input" or something (given suitable encoding of input on the tape), but the computation is foiled as soon as the machine wraps around and starts interfering with itself.

Then again, the self-interference is what makes many of these patterns do the cool things they do.


> Do we run into the limits of undecidability?

For this particular canvas, no, as the canvas is finite.

Given enough time or space we can exhaust all states of the canvas and catch cycles. This applies to any finite canvas.

I would guess these are equivalent to regular languages because of the finite state. You can treat the different canvas states as states of a finite automaton. A finite automaton is a canvas turing machine by ignoring the canvas.


Yes, I'm quite aware of this. Not to be rude or anything, but it is kinda obvious if you've thought at all finite computational systems.


It is obvious, yeah. I wasn't implying you didn't know it was or anything, just explaining the first sentence to someone who might not have studied complexity theory.


You're right, that was actually a really good explanation. I'm sorry, I misinterpreted your comment! Retroactively upvoted, for what it is worth.




The second one really looks like Rule 30 (which someone else linked to here).


This one looks like the current from a stream : http://wry.me/hacking/Turing-Drawings/#4,3,3,2,0,0,2,1,0,1,1...





I used a (very distant, now) variant on Langton's ant to do some "Turing drawings" of my own over the years: http://demoseen.com/langton/#.FP$!!!!!!!!!!!!!!!!!!!!~

The command set is detailed at the bottom of the page -- feel free to make your own and share them. They can be a whole lot of fun.

Edit: A few more examples: http://demoseen.com/langton/#.FP$!~7 http://demoseen.com/langton/#+.7 http://demoseen.com/langton/#T+.gt



And its counterpart, Metropolis, Rising: http://wry.me/hacking/Turing-Drawings/#4,3,3,2,0,0,1,2,1,1,3...

Really cool how it just keeps on going, with the shadows of more towers appearing to stretch out from the city centers, and the lights of cars driving down the left and right sides. I've had it running at high speed for quite a while now and buildings keep rising up occasionally.




Here are some cool ones I found:

Traveling pyramid: http://wry.me/hacking/Turing-Drawings/#4,3,3,2,0,1,1,2,2,1,3...

Coral-like tendrils (turn up the speed a bit): http://wry.me/hacking/Turing-Drawings/#4,3,1,2,1,3,1,2,2,1,1...


This is the best one I found so far. Most of them either freeze, run in a loop or turn to noise. This one turns into chaos, but maintains structure. http://wry.me/hacking/Turing-Drawings/#4,3,3,2,3,0,1,1,2,2,2...

It's like a wave moving to the bottom left. It has been doing the same thing for a while now, but I have not yet found any repetitions.



Some of these could be quite useful for graphics algorithms. For example: http://wry.me/hacking/Turing-Drawings/#4,3,1,1,2,1,2,1,0,2,3...

Is a pretty amazing simulation of fire with wind (although rotated 90°).

And that 'Glider' one from the other post could work as water on a car wind shield while driving.


Lovely.

My findings:

Here is one with a curious counter-clockwise rotation phenomenon:

http://wry.me/hacking/Turing-Drawings/#6,5,5,2,0,2,1,0,4,4,2...

And a few that take a long time to stabilize and do some interesting things in the meantime:

http://www.wry.me/hacking/Turing-Drawings/#3,5,2,4,1,1,1,3,1...

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

http://www.wry.me/hacking/Turing-Drawings/#3,6,1,3,3,2,1,0,0...


Here is a very nice variation on "Rapids":

http://www.wry.me/hacking/Turing-Drawings/#3,6,2,2,3,2,4,0,0...




This one is lovely. Water falls from Sierpinski triangles. It's still running, will be interesting to see if this pattern is stable

http://www.wry.me/hacking/Turing-Drawings/#3,4,2,1,0,2,2,2,0...


This is great. Here's a bug report:

If your browser window is narrow, the "Fork Me on GitHub" link overlaps the "Pause" button. (But the overlapping part of the GitHub image is transparent, so it's not immediately obvious why "Pause" doesn't work.)

The page content fits just fine, so it seems silly to make the window larger; there's just this little bug.


Thanks, Scott! As a quick patch I just broke the line of buttons in two. (I didn't want to mess with the original code more than needed, but couldn't resist adding the new buttons.)





Here's a fun one, reminds me of some abstract art I've seen: http://www.wry.me/hacking/Turing-Drawings/#4,3,3,1,0,0,2,3,2...



Interestingly, that's quite similar to cookingrobot's.

[ https://news.ycombinator.com/item?id=5709406 ]


After a while it looks like a parabola. Perhaps this is because the hypotenuse of a right triangle is the square root of 2?



The ascension of the lines: http://wry.me/hacking/Turing-Drawings/#10,3,0,1,2,7,2,3,3,2,...

Wavy lines slowly move upwards, some disappear over time.


What would happen if these were constrained to run inside irregularly shaped "skins" and bred for "fitness" against some criteria. For example, take a look at Marsaglia's die hard tests for statistical randomness. Any machine that terminates would have a very low random coefficient, and any that turns to noise would have a very high random coefficient. Similarly, ones that repeat quickly could also be selected against. All that remains is to restrict the number of critters, as specified by the number of "skins" and "breed" new critters from old ones which were successful (with a "pleasing" statistical randomness coefficient).





This one looks kinda cool:

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

Edit: This one takes very long and looks somewhat like rain in the end:

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


Watch this one fairly slow. http://wry.me/hacking/Turing-Drawings/#4,3,3,2,2,0,2,3,1,2,3... I like it because it seems to behave pretty well at first and decays only gradually.


Another experiment similar to this, but uses Biham–Middleton–Levine traffic model: http://htmlpreview.github.io/?http://github.com/MaciekBaron/...


This one stops after a pretty long time (put it on Fastest).

http://wry.me/hacking/Turing-Drawings/#5,3,4,1,3,2,1,2,4,2,3...

How usual is this?


This one is _counting_ to an incredibly large number -- slow it all the way down and watch what it's doing:

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


My favorite so far - there's something chemical about it: http://www.wry.me/hacking/Turing-Drawings/#2,5,0,4,0,0,3,1,1...


I wonder if one could construct a metric for how 'interesting' a drawing is- then throw it at a genetic algorithm? I'm guessing most likely the system is inherently unstable, so two 'interesting' parents don't necessarily create 'interesting' offspring


You don't have to use crossover, you can just make small mutations. That's much more likely to result in interesting offspring.




These really remind me of the old Core War game, where to competitive programs would try to annihilate each other:

http://www.corewars.org

It was played on a grid as well, and frequently made patterns similar to these.








How does anyone find these. I keep hitting "random" with various choices of states and colors and I get either white noise or an epileptic seizure.


Too many of either is unlikely to generate anything interesting, stick to very small numbers.


The "Fork me on Github" banner overlaps the controls invisibly. With a narrow-ish window, I can't click the "num symbols" box, or half the "restart" button or most of the "pause" button.


I don't like that banner. It uses "forking" in a sexual manner.




There's also Turing Tunes, based on the same idea: http://maximecb.github.io/Turing-Tunes/


Auto-IDM


Damn, I found one that made sierpinski triangles early on and didn't realize how rare those would turn out to be, haven't seen another one since.


I had the same experience. Not sure how they generate them but perhaps not as random as one would think?


this diagonal line repeats a few times and just "breaks" after a point.

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

I thought it was a bug at first, but it actually does it every time (speed up if you're impatient)


If you slow it way down after it 'freezes' you can get an idea how it's caught in a loop. (I wonder how many people have noticed you can slow it way down to see the head move.)





Here are some of my favorites. One of them (Counter) behaves strangely. It doesn't appear to be stable, but it takes a long, long time to change appreciably. Another one (Sewing Machine) seems semi-stable in that it seems to settle around the same kind of almost-but-not-quite-chaotic pattern.

Warpspeed http://wry.me/hacking/Turing-Drawings/#2,11,1,5,1,0,1,1,1,5,...

City Corner http://wry.me/hacking/Turing-Drawings/#2,11,1,10,0,1,5,2,0,8...

Coloring Inside the Lines http://wry.me/hacking/Turing-Drawings/#2,11,0,10,2,0,4,3,0,2...

Sewing Machine http://wry.me/hacking/Turing-Drawings/#2,11,1,7,3,0,2,0,0,3,... Seems semi-stable?

Folding Paper Trick http://wry.me/hacking/Turing-Drawings/#2,11,1,4,1,0,5,3,0,10...

Stable http://wry.me/hacking/Turing-Drawings/#5,3,3,1,0,3,1,0,3,1,0...

Counter: http://wry.me/hacking/Turing-Drawings/#5,3,1,1,0,3,1,3,2,1,2... This one seems to behave like some kind of adder. Even at the highest speed setting it takes a long time to see much change, but the black lines seem to grow and move similar to how a binary adder operates.

Spilled Drink http://wry.me/hacking/Turing-Drawings/#13,21,10,11,1,0,7,0,4...

Donkey Kong http://wry.me/hacking/Turing-Drawings/#13,21,0,17,3,11,4,0,0...


Very good idea!




Join us for AI Startup School this June 16-17 in San Francisco!

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

Search: