8 ms·
Way to steal my karma.... :) As the original author of this, I was going to put it into a much more presentable state before showing it off here. For those co
by elitheeli 16y ago
Way to steal my karma.... :)
As the original author of this, I was going to put it into a much more presentable state before showing it off here.
For those confused, here's a proper explanation. No real-world thing can actually be Turing complete (able to express basically any computation that we might want to perform of any size). That's because there are finitely many atoms in the universe, so we can only construct machines of finite size.
It's well known that Rule 110 (Google it) is Turing Compete.
What I've done is made an implementation of Rule 110 in HTML and CSS. Since CSS can't actually really manipulate state, some user interaction is required to "drive" it. In the one that bgruber linked to, it's clicking.
Here's a bigger version that doesn't require the user to know where to put his mouse. The tab-space combo is just as legitimate as requiring that you plug a computer into a wall to power it in order to run a Java program. http://elilies.com/rule110-full.html http://elilies.com/rule110-full.html
Also, I haven't tested it on anything besides the latest Chrome on Mac.
- Skalman 16y agoIt works fine on Firefox 4.0b12 on Linux too. :-) That version works much better than the one I tried on github! It's also much cooler.
- mrspeaker 16y agoThat's what happens when you put something on github! In fact, I bet you any money that someone has already taken the code and created a 16-bit logic unit INSIDE minecraft INSIDE your turing machine.
- nkassis 16y agoyou forgot to mention that the turing machine runs in a browser that runs in another turing machine which is inside a huge machine called the universe.
- riledhel 16y agoinside a dream, inside another dream!
- loup-vaillant 16y agoMay be more true than one might think: http://www.simulation-argument.com/ http://www.simulation-argument.com/
- doyoulikeworms 16y agoIt's Turing machines all the way down.
- apgwoz 16y agoWell, really, it's what happen when you make an impression at Hack and Tell (http://hackandtell.org http://hackandtell.org)! This was perhaps the highlight of last night's Meetup.
- jgv 16y agoIt's true. This was definitely the best presentation at last nights hack and tell. A pleasant surprise to see this on HN today.
- ghempton 16y agoThats a cool premise for a meetup. Wish there was one in Seattle.
- apgwoz 16y agostart one! and ping me if you do. i'll do ny best to help promote it.
- justinlilly 16y agoIf you start one, I'll attend.
- pvsnp 16y agoAll of this is running inside a VM inside another VM
- hasenj 16y ago> No real-world thing can actually be Turing complete But when you say Turing-complete, I assume something along the lines of "a programming language can be built on top of it and you can create interactive applications using such a programming language instead of javascript". It seems like that's not the case at all.
- jules 16y agoThen you assumed a falsehood. Turing completeness is a mathematical concept that has nothing to do with interactive applications.
- hasenj 16y agoNo, mathematically nothing is "Turing Complete". The only usefulness of saying that something is "Turing Complete" is in knowing that you can treat it as if it was a normal computer for all intents and purposes. So mathematically a laptop is not Turing Complete, but for all practical purposes, it is.
- jules 16y agoAlso incorrect. Counterexample: Turing machines are Turing complete. You are correct that a laptop is not Turing complete, though.
- jng 16y agoNope. The common usefulness is to determine whether a given computation-describing system reaches the threshold of universal computability. Modulo finite size is assumed, else there is no usefulness of the concept given finite resources. For example, SKI combinators are Turing-equivalent. Regular expressions aren't. The lambda-calculus is. Context-independent grammars probably are. Most data description languages are not. This is worthy of an HN post because a style-description language would not normally be expected to be Turing-equivalent. When it became widely known that the C++ template system was Turing-equivalent, it was a shock to many. These meant that the C++ compiler code itself could be exploited to compute arbitrary things such as factorials, or shortest-paths in graphs using A*. Actually, as the SKI system demonstrates, the threshold is quite low. The core needed components are just "constant" or "if" (they are often equivalent), and "repeat" (equivalent to both "iterate" and "recurse").
- Tichy 16y agoI always find the "finite number of atoms" argument a little misleading. Isn't it rather a question of how well we can measure things? If we could measure at infinite precision, one atom would be sufficient to encode all possible states we could dream of. I suppose quantum theory puts a lower limit on the attainable precision of measurements, but I don't know the details. I must admit that since HTML+CSS3 requires clicks (at least in this implementation), I don't consider it to be really proven to be touring complete.
- JonnieCache 16y agoWe simply do not have enough information on the nature of reality to decide who is right here. If space-time does turn out the be physically discrete at the planck length, and the limits of our measurements are actually reflecting the universe's true discontinuous nature, then this would imply that there would be a limit to how much state you could push into an atom. Any real physicists please feel free to shoot me down in flames here. This is just my (plainly) limited understanding of the situation.
- lmkg 16y agoThere are actually physical laws somewhere in thermodynamics that place an upper bound on the existence of information within a space. Oddly enough, the maximum information in a space is proportional to the surface area, not the volume[1]. Black holes attain this maximum, although I'm not sure if non-black-holes are capable of attaining it as well. In a related note, Bell's Theorem (along with a few experimental results) demonstrate that no theory of (local) hidden variables can account for quantum theory[2]. This means that the limit is not just on our ability to measure the information in an atom. It literally doesn't exist for us to measure. Quantum mechanics is confusing =P. [1] Specifically, the information measured in binary bits is bounded by the surface area divided by four. I'm not 100% sure what the unit of surface area is, but I believe it's Plank units. [2] http://en.wikipedia.org/wiki/Bells_Theorem http://en.wikipedia.org/wiki/Bells_Theorem
- soamv 16y agoone atom would be sufficient to encode all possible states http://en.wikipedia.org/wiki/Bekenstein_bound http://en.wikipedia.org/wiki/Bekenstein_bound
- kachnuv_ocasek 16y agosteal karma Seriously, what the fuck? This is just too much exaggerated.
- bgruber 16y agosorry eli, this was just too cool not to share.
- msarnoff 16y agoI've never been happy with the hand-wavy, almost circular definition of Turing completeness. We all know the "simulating a Turing machine/computing any function" bit, but what does that really mean? From a practical standpoint, what does a language need to be Turing complete? What key concept separates things like HTML and regular expressions from "real" programming languages? I believe Petzold said this concept was controlled repetition. Conditionals and loops/jumps/recursion. This example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping.
- sid0 16y agoThis example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping. That's like saying that my computer isn't a Turing machine (modulo finiteness of memory) because I need to plug it into a socket to run it. Turing machines are a very abstract notion of computation (and one of the most general ones we know of), and a lot of things can be used to simulate one. Turns out HTML+CSS3 is yet another such thing.
- eru 16y agoIf you don't like `Turing complete', use `Lambda-calculus isomorph', or `Post-correspondence-system isomorph'. Turing completeness is not hand-wavy, or circular. Or look up SKI-calculus (http://en.wikipedia.org/wiki/SKI_calculus http://en.wikipedia.org/wiki/SKI_calculus), if you want to be gob-smacked.
- johnzabroski 16y agoNeat! I posted it to Lambda the Ultimate front page. Been awhile since a cool/wacky hacker project got a front page item. Used to happen all the time 5 years ago.