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.
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.
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
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.
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.
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.
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.
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.)
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.
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.
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.
121 comments
[ 4.7 ms ] story [ 199 ms ] threadhttp://blog.willbenton.com/2008/11/rent-a-coder-hilarity/
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 :)
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,...
Nice implementation of it.
http://www.wry.me/hacking/Turing-Drawings/#3,6,2,2,3,2,4,0,0...
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.)
http://wry.me/hacking/Turing-Drawings/#4,3,1,2,2,0,1,0,3,1,0...
http://wry.me/hacking/Turing-Drawings/#4,3,0,1,1,1,1,3,2,2,2...
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...
The glider appears after a few seconds of high speed.
Very nice implementation!
Not exactly a glider, but it looks like this does at the start, but reversed...sort of... (maybe)
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.
"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...
http://wry.me/hacking/Turing-Drawings/#4,3,2,2,3,0,1,1,2,1,0...
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.
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.
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.
http://wry.me/hacking/Turing-Drawings/#4,4,2,1,2,1,1,1,2,3,3...
[ https://news.ycombinator.com/item?id=5709406 ]
Escher's hourglass: http://wry.me/hacking/Turing-Drawings/#5,3,3,1,3,0,1,2,1,2,0...
Zigzags (devolves): http://wry.me/hacking/Turing-Drawings/#5,4,3,3,0,3,1,2,1,1,1...
A big static one: Construction line: http://wry.me/h...
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...
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
Ice 9: http://wry.me/hacking/Turing-Drawings/#5,4,3,3,3,3,2,2,1,2,0...
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...
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.
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.
http://wry.me/hacking/Turing-Drawings/#4,3,0,1,3,1,1,2,0,2,3...
looks like there's a bifurcation diagram buried in there somehow: https://www.google.co.uk/search?q=bifurcation+diagram
even closer : http://www.wry.me/hacking/Turing-Drawings/#2,23,1,2,2,0,19,3...
Bonus animated brass rubbing: http://wry.me/hacking/Turing-Drawings/#4,3,1,1,2,2,1,1,3,1,0...